59二叉树中以广义表,(先序,中序后序)递归,中序非递归输出
上亿文档资料，等你来发现
59二叉树中以广义表,(先序,中序后序)递归,中序非递归输出
#include&stdio.h&；#include&stdlib.h&；#defineSTACK_INIT_SIZE10；#defineSTACKINCREMENT10；#defineOVERFLOW-2；#defineOK1；#defineERROR-1；#defineTRUE1；#defineFALSE0；typedefchar
#include&stdio.h&#include&stdlib.h& #define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OVERFLOW -2#define OK 1#define ERROR -1#define TRUE 1#define FALSE 0 typedef char TElemTtypedef int S typedef struct BiTNode{ // 二叉链表储存结构TElemTstruct BiTNode *lchild,*}BiTNode,*BiT Status CreateBiTree(BiTree &T){//先序序列建立二叉树scanf(&%c&,&ch); if(ch=='#') T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) return(OVERFLOW);T-&data=CreateBiTree(T-&lchild);CreateBiTree(T-&rchild);}return OK;} void PrintBiTree(BiTree &T){
//以广义表的形式输出if(T!= NULL){printf(&%c&, T-&data);if(T-&lchild != NULL || T-&rchild!=NULL){printf(&(&);PrintBiTree(T-&lchild);if(T-&rchild != NULL){printf(&,&);}PrintBiTree(T-&rchild);printf(&)&);}}} Status PrintElement(TElemType e){// 访问函数printf(&%c&,e);return OK;} Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){//先序遍历二叉树的递归算法
if(T){if(Visit(T-&data))// printf(&(&);if(PreOrderTraverse(T-&lchild,Visit))//
printf(&,&);if(PreOrderTraverse(T-&rchild,Visit))//
printf(&)&);return OK;return ERROR;}elsereturn OK;} Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType)) {//中序遍历二叉树的递归算法
if (T) {if (InOrderTraverse(T-&lchild, Visit))if (Visit(T-&data))if (InOrderTraverse(T-&rchild, Visit))return OK;return ERROR;}elsereturn OK;} Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType)) {//后序遍历二叉树的递归算法
if (T) {if (PostOrderTraverse(T-&lchild, Visit))if (PostOrderTraverse(T-&rchild, Visit))if (Visit(T-&data))return OK;return ERROR;}elsereturn OK;} //中序遍历二叉树的非递归算法typedef struct {
// 栈存储结构及操作BiTree *BiTree *}S Status InitStack(Stack &S) { //构造空栈S.base = (BiTree*)malloc(STACK_INIT_SIZE * sizeof(BiTree));if (!S.base) exit(OVERFLOW);S.top = S.S.stacksize = STACK_INIT_SIZE;return OK;} Status GetTop(Stack S, BiTree &e){
//读栈顶元素if (S.top == S.base) return ERROR;e = *(S.top - 1);
return OK;} Status Push(Stack &S, BiTree e){
//入栈if (S.top - S.base &= S.stacksize) {S.base = (BiTree*)realloc(S.base, (S.stacksize + STACKINCREMENT) sizeof(BiTree));if (!S.base) exit(OVERFLOW);S.top = S.base + S.S.stacksize += STACKINCREMENT;}*S.top++ =return OK;} Status Pop(Stack &S, BiTree &e){
//出栈if (S.top == S.base) return ERROR;e = *--S.return OK;}
*Status StackEmpty(Stack S){
//判栈空if (S.base == S.top) return TRUE;else return FALSE;} Status InOrderTraverse2(BiTree T, Status (*Visit)(TElemType)) {
//中序遍历二叉树的非递归算法Stack S;BiTInitStack(S);Push(S, T);while (!StackEmpty(S)) {while (GetTop(S, p) && p) Push(S, p-&lchild);Pop(S, p);if (!StackEmpty(S)) {Pop(S, p);if (!Visit(p-&data)) return ERROR;Push(S, p-&rchild);}}return OK;} int main(){BiTree T;printf(&请输入二叉树先序序列：&);CreateBiTree(T);printf(&\n&);printf(&以广义表的形式输出：&);PrintBiTree(T);printf(&\n\n&);printf(&先序递归遍历顺序：&);PreOrderTraverse(T, PrintElement);printf(&\n&);printf(&中序递归遍历顺序：&);InOrderTraverse(T, PrintElement);printf(&\n&);printf(&后序递归遍历顺序：&);PostOrderTraverse(T, PrintElement);printf(&\n\n&);printf(&中序非递归遍历顺序： &);}printf(&\n&);
return 0; 包含各类专业文献、专业论文、生活休闲娱乐、行业资料、幼儿教育、小学教育、中学教育、应用写作文书、各类资格考试、59二叉树中以广义表,(先序,中序后序)递归,中序非递归输出等内容。
　 二叉树先序、中序、后序遍历非递归算法_IT/计算机_专业资料。二叉树. 二叉树先序遍历非递归算法 void PreOrderUnrec(Bitree *t) { S StackInit(s); ... 　 二叉树的递归、非递归的先序、中序、后序遍历以及层次遍历和求叶子节点数 ...(&中序遍历输出为:&); //InOrderTraverse(t);//中序非递归遍历 Inorder(... 　2.实验主要内容 2.1 对二叉树进行先序、中序、后序递归遍历,中序非递归遍历...编写二叉树打印函数,可以通过递归算法将二叉树输出为广义表的 形式,以方便观察树... 　二叉树的遍历:前序,中序,后序,层序--包括递归和非递归实现后序遍历还没有明白,继续学习^_^,过几天写个 huffman 编码的例子来玩玩,不多说了,看 代码吧,... 　二叉树先序非递归遍历、 二叉树先序非递归遍历、中序和后序递归遍历源程序 #include&stdio.h& #include&malloc.h& #define maxsize 10 #define stackmaxsize ... 　欲实现任意二叉树的后序遍历的非递归算法而不必使用...任何一棵二叉树的叶子结点在先序、中序和后序遍历...假定一棵树的广义表表示为 A(B(E) ,C(F(H,I... 　 二叉树先序、中序、后序三种遍历的非递归算法,此三个算法可视为标准_电力/水利_工程科技_专业资料。二叉树先序、中序、后序三种遍历的非递归算法,此三个算法... 　 二叉树先序、中序、后序三种遍历的非递归算法,此三个算法可视为标准_互联网_IT/计算机_专业资料。急救知识_眼部烧伤急救要趁早二叉树先序、 中序、 后序三种... 　2.掌握如何用广义表表示二叉树 3.掌握链式二叉树的建立及递归和非递归遍历输出...调用中序遍历函数 preorder(head)调用先序遍历函数 postorder(head);调用后序...二叉树先序、中序、后序遍历的递归算法和非递归算法 - Andy Cheung - 推酷
二叉树先序、中序、后序遍历的递归算法和非递归算法 - Andy Cheung
先序遍历：
若二叉树为空，则空操作；否则访问根节点；先序遍历左子树；先序遍历右子树。
中序遍历：
若二叉树为空，则空操作；否则中序遍历左子树；访问根节点；中序遍历右子树。
后序遍历：
若二叉树为空，则空操作；否则后序遍历左子树；后序遍历右子树；访问根节点。
二叉链表：
链表中的结点包含三个域：数据域和左右指针域。
三叉链表：
在二叉链表的基础上增加指向双亲结点的指针域。
以下代码均使用二叉链表。
//二叉树的二叉链表存储表示
typedef char TElemT
typedef struct BiNode
struct BiNode *lchild, *
} BiNode , *BiT
生成二叉树
可以在遍历过程中生成结点，建立二叉树的存储结构。按先序序列建立二叉树的二叉链表的算法如下：
* 按先序次序输入二叉树中结点的值(一个字符)，空格字符表示空树，构造二叉链表表示的二叉树T。
Status CreatBiTree(BiTree *T)
scanf(&%c&, &ch);
//如果当前输入的字符为空格，则(*T)指向空树。
if (ch == ' ')
(*T) = NULL;
if (!((*T) = (BiTree)malloc(sizeof(BiNode))))
exit(OVERFLOW);
(*T)-&data =
//生成根结点
CreatBiTree(&((*T)-&lchild)); //构造左子树
CreatBiTree(&((*T)-&rchild)); //构造右子树
return OK;
假设输入字符依次为
ABC##DE#G##F###(#
，则生成的二叉树如下所示：
二叉树遍历递归算法
* 采用二叉链表存储结构，Visit是对数据元素操作的应用函数，
* 先序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。
Status PreOrderTraverse_Recursive(BiTree T, Status(*Visit)(TElemType e))
if (Visit(T-&data))
if (PreOrderTraverse_Recursive(T-&lchild, Visit))
if (PreOrderTraverse_Recursive(T-&rchild, Visit))
return OK;
return ERROR; //函数不会执行到这一步，不会返回Error。这样写只是为了没有编译警告。
return OK; //当T为空树时，停止递归。
Status InOrderTraverse_Recursive(BiTree T, Status(*Visit)(TElemType e))
if (InOrderTraverse_Recursive(T-&lchild, Visit))
if (Visit(T-&data))
if (InOrderTraverse_Recursive(T-&rchild, Visit))
return OK;
return ERROR;
return OK;
Status PostOrderTraverse_Recursive(BiTree T, Status(*Visit)(TElemType e))
if (PostOrderTraverse_Recursive(T-&lchild, Visit))
if (PostOrderTraverse_Recursive(T-&rchild, Visit))
if (Visit(T-&data))
return OK;
return ERROR;
return OK;
二叉树遍历非递归算法
* 先序遍历二叉树，非递归算法。
Status PreOrderTraverse_NonRecursive(BiTree T, Status(*Visit)(TElemType e))
Stack *S; //栈S中存储指向树结点的指针。
S = (Stack*)malloc(sizeof(Stack));
InitStack(S);
Push(S, T); //根指针进栈。
while (!StackEmpty(S))
//获取栈顶指针，如果栈顶指针不为空，访问该结点。并将该结点的左子树进栈。
if (GetTop(S, &p) && p)
if (!Visit(p-&data))
return ERROR;
Push(S, p-&lchild);
//栈顶指针为空，表明之前压入的左子树或者右子树为空。
Pop(S, &p); //空指针退栈
if (!StackEmpty(S))
Pop(S, &p); //已被访问过的根结点退栈。此时，该退栈结点的左子树已被全部访问过。
Push(S, p-&rchild); //右子树进栈。
return OK;
* 采用二叉链表存储结构，Visit是对数据元素进行操作的应用函数，
* 中序遍历二叉树的非递归算法，对每个数据元素调用函数Visit。
Status InOrderTraverse_NonRecursive(BiTree T, Status(*Visit)(TElemType e))
S = (Stack *)malloc(sizeof(Stack));
InitStack(S);
Push(S, T); //根指针进栈
while (!StackEmpty(S))
//向左走到尽头
while (GetTop(S, &p) && p)
Push(S, p-&lchild);
//空指针退栈
Pop(S, &p);
//访问节点，并向右一步
if (!StackEmpty(S))
Pop(S, &p);
if (!Visit(p-&data))
return ERROR;
Push(S, p-&rchild);
return OK;
* 采用二叉链表存储结构，Visit是对数据元素进行操作的应用函数，
* 中序遍历二叉树的非递归算法，对每个数据元素调用函数Visit。
Status InOrderTraverse_NonRecursive_2(BiTree T, Status(*Visit)(TElemType e))
BiTree p = T;
S = (Stack *)malloc(sizeof(Stack));
InitStack(S);
while (p || !StackEmpty(S))
//根指针进栈，遍历左子树
Push(S, p);
//根指针退栈，访问根结点，遍历右子树
Pop(S, &p);
if (!Visit(p-&data))
return ERROR;
return OK;
* 后序遍历二叉树，非递归算法
Status PostOrderTraverse_NonRecursive(BiTree T, Status(*Visit)(TElemType e))
BiTree p, pre=NULL;//pre指向已访问过的最后一个结点。
S = (Stack*)malloc(sizeof(Stack));
InitStack(S);
Push(S, T);//根指针进栈
while (!StackEmpty(S))
//获取栈顶指针，如果当前结点有左子树，并且左子树结点不是刚被访问的节点。如果当前结点有右子树，并且右子树结点不是刚被访问的结点。
//表明栈顶指针指向的树结点未被访问，且左子树和右子树均未被访问。此时，将结点的左子树进栈。
if (GetTop(S, &p) && p-&lchild && pre != p-&lchild && !(p-&rchild && pre == p-&rchild))
Push(S, p-&lchild);
//如果栈顶指针的右子树存在，且未被访问。则将右子树进栈
else if (p-&rchild && pre != p-&rchild)
Push(S, p-&rchild);
//如果左子树和右子树均被访问过，则结点退栈，并进行访问。更新pre。
Pop(S, &p);
if (!Visit(p-&data))
return ERROR;
return OK;
4.测试完整代码
* 假设输入字符为：ABC##DE#G##F###，实际输入时，#用空格代替。
#define _CRT_SECURE_NO_WARNINGS
#include &stdio.h&
#include &malloc.h&
#include &stdlib.h&
typedef int S
#define OK 1
#define ERROR 0
#define OVERFLOW -2
//二叉树的二叉链表存储表示
typedef char TElemT
typedef struct BiNode
struct BiNode *lchild, *
} BiNode , *BiT
//栈的顺序存储结构
#define STACK_INIT_SIZE 100
//存储空间初始分配量
#define STACKINCREMENT 10
//存储空间分配增量
typedef struct
//函数声明
Status InitStack(Stack *S);
Status Push(Stack *S, BiTree p);
Status Pop(Stack *S, BiTree *p);
Status GetTop(Stack *S, BiTree *p);
Status StackEmpty(Stack *S);
Status CreatBiTree(BiTree *T);
Status PreOrderTraverse_Recursive(BiTree T, Status(*Visit)(TElemType e));
Status InOrderTraverse_Recursive(BiTree T, Status(*Visit)(TElemType e));
Status PostOrderTraverse_Recursive(BiTree T, Status(*Visit)(TElemType e));
Status PreOrderTraverse_NonRecursive(BiTree T, Status(*Visit)(TElemType e));
Status InOrderTraverse_NonRecursive(BiTree T, Status(*Visit)(TElemType e));
Status InOrderTraverse_NonRecursive_2(BiTree T, Status(*Visit)(TElemType e));
Status PostOrderTraverse_NonRecursive(BiTree T, Status(*Visit)(TElemType e));
Status PrintElement(TElemType e);
int main()
CreatBiTree(&T);
PreOrderTraverse_Recursive(T, PrintElement); putchar('\n');
PreOrderTraverse_NonRecursive(T, PrintElement); putchar('\n');
InOrderTraverse_Recursive(T, PrintElement); putchar('\n');
InOrderTraverse_NonRecursive(T, PrintElement); putchar('\n');
InOrderTraverse_NonRecursive_2(T, PrintElement); putchar('\n');
PostOrderTraverse_Recursive(T, PrintElement); putchar('\n');
PostOrderTraverse_NonRecursive(T, PrintElement); putchar('\n');
* 按先序次序输入二叉树中结点的值(一个字符)，空格字符表示空树，构造二叉链表表示的二叉树T。
Status CreatBiTree(BiTree *T)
scanf(&%c&, &ch);
//如果当前输入的字符为空格，则(*T)指向空树。
if (ch == ' ')
(*T) = NULL;
if (!((*T) = (BiTree)malloc(sizeof(BiNode))))
exit(OVERFLOW);
(*T)-&data =
//生成根结点
CreatBiTree(&((*T)-&lchild)); //构造左子树
CreatBiTree(&((*T)-&rchild)); //构造右子树
return OK;
* 采用二叉链表存储结构，Visit是对数据元素操作的应用函数，
* 先序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。
Status PreOrderTraverse_Recursive(BiTree T, Status(*Visit)(TElemType e))
if (Visit(T-&data))
if (PreOrderTraverse_Recursive(T-&lchild, Visit))
if (PreOrderTraverse_Recursive(T-&rchild, Visit))
return OK;
return ERROR; //函数不会执行到这一步，不会返回Error。这样写只是为了没有编译警告。
return OK; //当T为空树时，停止递归。
Status InOrderTraverse_Recursive(BiTree T, Status(*Visit)(TElemType e))
if (InOrderTraverse_Recursive(T-&lchild, Visit))
if (Visit(T-&data))
if (InOrderTraverse_Recursive(T-&rchild, Visit))
return OK;
return ERROR;
return OK;
Status PostOrderTraverse_Recursive(BiTree T, Status(*Visit)(TElemType e))
if (PostOrderTraverse_Recursive(T-&lchild, Visit))
if (PostOrderTraverse_Recursive(T-&rchild, Visit))
if (Visit(T-&data))
return OK;
return ERROR;
return OK;
* 先序遍历二叉树，非递归算法。
Status PreOrderTraverse_NonRecursive(BiTree T, Status(*Visit)(TElemType e))
Stack *S; //栈S中存储指向树结点的指针。
S = (Stack*)malloc(sizeof(Stack));
InitStack(S);
Push(S, T); //根指针进栈。
while (!StackEmpty(S))
//获取栈顶指针，如果栈顶指针不为空，访问该结点。并将该结点的左子树进栈。
if (GetTop(S, &p) && p)
if (!Visit(p-&data))
return ERROR;
Push(S, p-&lchild);
//栈顶指针为空，表明之前压入的左子树或者右子树为空。
Pop(S, &p); //空指针退栈
if (!StackEmpty(S))
Pop(S, &p); //已被访问过的根结点退栈。此时，该退栈结点的左子树已被全部访问过。
Push(S, p-&rchild); //右子树进栈。
return OK;
* 采用二叉链表存储结构，Visit是对数据元素进行操作的应用函数，
* 中序遍历二叉树的非递归算法，对每个数据元素调用函数Visit。
Status InOrderTraverse_NonRecursive(BiTree T, Status(*Visit)(TElemType e))
S = (Stack *)malloc(sizeof(Stack));
InitStack(S);
Push(S, T); //根指针进栈
while (!StackEmpty(S))
//向左走到尽头
while (GetTop(S, &p) && p)
Push(S, p-&lchild);
//空指针退栈
Pop(S, &p);
//访问节点，并向右一步
if (!StackEmpty(S))
Pop(S, &p);
if (!Visit(p-&data))
return ERROR;
Push(S, p-&rchild);
return OK;
* 采用二叉链表存储结构，Visit是对数据元素进行操作的应用函数，
* 中序遍历二叉树的非递归算法，对每个数据元素调用函数Visit。
Status InOrderTraverse_NonRecursive_2(BiTree T, Status(*Visit)(TElemType e))
BiTree p = T;
S = (Stack *)malloc(sizeof(Stack));
InitStack(S);
while (p || !StackEmpty(S))
//根指针进栈，遍历左子树
Push(S, p);
//根指针退栈，访问根结点，遍历右子树
Pop(S, &p);
if (!Visit(p-&data))
return ERROR;
return OK;
* 后序遍历二叉树，非递归算法
Status PostOrderTraverse_NonRecursive(BiTree T, Status(*Visit)(TElemType e))
BiTree p, pre=NULL;//pre指向已访问过的最后一个结点。
S = (Stack*)malloc(sizeof(Stack));
InitStack(S);
Push(S, T);//根指针进栈
while (!StackEmpty(S))
//获取栈顶指针，如果当前结点有左子树，并且左子树结点不是刚被访问的节点。如果当前结点有右子树，并且右子树结点不是刚被访问的结点。
//表明栈顶指针指向的树结点未被访问，且左子树和右子树均未被访问。此时，将结点的左子树进栈。
if (GetTop(S, &p) && p-&lchild && pre != p-&lchild && !(p-&rchild && pre == p-&rchild))
Push(S, p-&lchild);
//如果栈顶指针的右子树存在，且未被访问。则将右子树进栈
else if (p-&rchild && pre != p-&rchild)
Push(S, p-&rchild);
//如果左子树和右子树均被访问过，则结点退栈，并进行访问。更新pre。
Pop(S, &p);
if (!Visit(p-&data))
return ERROR;
return OK;
//遍历数据元素时所调用函数
Status PrintElement(TElemType e)
putchar(e);
return OK;
//初始化栈
Status InitStack(Stack *s)
s-&base = (BiTree*)malloc(sizeof(BiTree)*STACK_INIT_SIZE);
s-&top = s-&
s-&stacksize = STACK_INIT_SIZE;
return OK;
//获得栈顶元素
Status GetTop(Stack *s, BiTree *c)
if (StackEmpty(s))
return ERROR;
*c = *(s-&top - 1);
return OK;
//判断栈是否为空
Status StackEmpty(Stack *s)
if (s-&base == s-&top)
return OK;
return ERROR;
Status Push(Stack *s, BiTree c)
//如果空间不够，增加空间的分配
if (s-&top - s-&base &= s-&stacksize)
s-&base = (BiTree*)realloc(s-&base, sizeof(BiTree)*(s-&stacksize + STACKINCREMENT));
s-&stacksize = s-&stacksize + STACKINCREMENT;
*(s-&top++) =
return OK;
Status Pop(Stack *s, BiTree *c)
if (StackEmpty(s))
return ERROR;
*c = *(--s-&top);
return OK;
5.测试结果
注：程序中生成的树为上图中的树
已发表评论数()
&&登&&&陆&&
已收藏到推刊！
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见树实验报告_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
19页免费23页免费8页免费6页免费13页免费4页免费6页免费35页7下载券10页免费3页免费
喜欢此文档的还喜欢1页免费3页1下载券14页免费30页免费16页1下载券
树实验报告|数​据​结​构​关​于​树​实​验​报​告
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
你可能喜欢6第六章 树和二叉树_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
文档贡献者贡献于
评价文档：
24页免费99页免费81页免费2页¥1.0039页免费116页免费90页1下载券72页1下载券63页1下载券9页免费
喜欢此文档的还喜欢1页免费2页7下载券5页1下载券6页7下载券1页7下载券
6第六章 树和二叉树|
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
大小：529.50KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢