用递归非递归两种方法遍历二叉树

1、实用文档数据结构（双语）项目文档报告用递归、非递归两种方法遍历二叉树专 业：计算机科学与技术班 级：指导教师：姓 名：号:一、设计思想 .03二、算法流程图 .04三、源代码 .06四、运行结果 .12五、遇到的问题及解决 .14六、心得体会 .15标准文案一、设计思想1 .递归：(1)主函数main ()主程序要包括：定义的二叉树 T、建树函数、先序遍 历函数、中序遍历函数、后序遍历函数。(2)建树函数定义一个输入的数是字符型的，当 ch为空时，T就为空值， 否则的话就分配空间给T, T就指向它的结点，然后左指针域指向左孩子，右指 针指向右孩子，若还有，继续调用，依次循环下去，直到ch遇到空

2、时，结束。最 后要返回建立的二叉树To(3)先序遍历函数根据先序遍历规则，当 T为非空时，先输出结点处的数 据，指针指向左、右孩子，依次进行下去。(4)中序遍历函数根据中序遍历规则，当T为非空时，先左指针指向左孩子 数据，然后输出结点处的数据，再右指针指向右孩子，依次进行下去。(5)后序遍历函数根据后序遍历规则，当T为非空时，先右指针指向右孩子， 然后左指针指向左孩子，最后输出结点处的数据，依次进行下去。2 .非递归：(1)跟递归遍历二叉树的前提一样， 首先应该创建一个二叉树，同样使用 先序递归的方式创建二叉树。(2)然后是中序，先序，后序非递归遍历二叉树。(3)中序非递归遍历二叉树的思想是：

3、 首先是根节点压栈，当根节点的左 子树不是空的时候，左子树压栈。直到左子树为空的时候，不再压栈。将栈顶元 素出栈，访问栈顶元素，并将栈顶的右子树进栈。当右子树的左子树不是空的时 候，左子树一直进栈，直到左子树为空，则不再进栈。重复上面的操作，直到栈 空的时候。(4)先序非递归遍历二叉树的思想是：首先是根节点进栈，然后当栈不为空 的时候，将栈顶元素出栈，然后访问。同时将出栈元素的右子树进栈，左子树进 栈。重复上面的操作，直到栈为空。(5)后序非递归遍历二叉树的思想：首先是根节点进栈，当根节点的左子 树不为空的时候，左子树进栈，直到左为空的时候，左子树不再进栈。指针指向 的是右子树，当右子树为空的

4、时候，直接访问根节点。当右子树不为空的时候， 则右子树的指针进栈，当右子树的左子树不为空的时候， 则左也进栈，直到左为 空。重复上面的操作，直到栈为空的时候，则遍历树完成。二、算法流程图i.递归I咕布在、4旃人校孙上 11M中悯历程2.非递归建。网TT.T收布 白当宜的懒用舟根丐息人山-|k利p盘口”的人 授元篇.并聘id中 的巾行点也挂，也 人君I技心中£ tt-' HTXTFhIL< U伍槽3的元典依次山林三、源代码1 .递归#include "stdio.h"#include "conio.h"#include <st

5、dlib.h>#include<stack>typedef struct nodechar data;struct node *lchild, *rchild;BinTnode;typedef BinTnode * BinTree; 定义二叉树类型的指针/*先序创建二叉树*/int CreateBinTree(BinTree *T)char ch;*T=(BinTree)malloc(sizeof(BinTnode);if(!*T) printf("overflow");doch=getchar();if(ch='') *T=NULL;re

6、turn 0;else(*T)->data=ch;CreateBinTree(&(*T)->lchild);CreateBinTree(&(*T)->rchild);return 1;while(ch!='0');/*中序递归遍历*/void InorderTransverse(BinTree s)ifInorderTransverse(s->lchild); printf("%c", s->data); InorderTransverse(s->rchild);/先序递归遍历二叉树void PreOrde

7、rTranverseTree(BinTree s)ifprintf("%c", s->data);PreOrderTranverseTree(s->lchild); PreOrderTranverseTree(s->rchild); /后序递归遍历二叉树 void PostOrderTranverseTree(BinTree s) if PreOrderTranverseTree(s->lchild); PreOrderTranverseTree(s->rchild); printf("%c", s->data);/*

8、主方法*/void main()BinTree T;printf("请按照先序的顺序输入要创建的树：n");CreateBinTree(&T); /*中序序列创建二叉树*/printf("中序递归遍历的序列是：")；InorderTransverse(T);printf("n");/先序递归遍历printf("先序递归遍历的序列是：")；PreOrderTranverseTree(T); printf("n");/后序递归遍历printf("后序递归遍历的序列是：")

9、；PostOrderTranverseTree(T); printf("n");2 .非递归#include "stdio.h"#include "conio.h"#include <stack>#include <stdlib.h>typedef struct nodechar data;struct node *lchild, *rchild;BinTnode;typedef BinTnode * BinTree; 定义二叉树类型的指针typedef structBinTree data100;int to

10、p;SeqStack;void initStack(SeqStack *S)S->top =-1;void Push(SeqStack *S,BinTree x)if(S->top=100-1)printf("the stack is overflow");else S->top=S->top+1;S->dataS->top=x;int Pop(SeqStack *S,BinTree *p)if(S->top=-1)printf("the stack is underflow");return 0;else *p

11、=S->dataS->top;-S->top;return 1;int EmptyStack(SeqStack S)if(S.top=-1) return 1;else return 0; /*栈不空的情况*/int GetTop(SeqStack S,BinTree *p)if(S.top=-1)printf("the stack is empty");return 0;else *p=S.dataS.top;return 1;char visit(BinTree p) return (*p).data;/*创建二叉树*/int CreateBinTre

12、e(BinTree *T)char ch;叮=(BinTree)malloc(sizeof(BinTnode);if(!*T) printf("overflow");else doch=getchar();if(ch!='')q=NULL;return 0; else(*T)->data=ch;CreateBinTree(&(*T)->lchild);CreateBinTree(&(*T)->rchild); return 1;while(ch!='0');/*中序非递归遍历*/void InorderTra

13、nsverse(BinTree T)SeqStack S;BinTree p;initStack(&S);/ 初始化栈printf("中序非递归序列是：")；Push(&S,T); / 根指针进栈T为指向二叉树的指针while(!EmptyStack(S) /栈不是空的情况while(GetTop(S,&p) && p)Push(&S,p->lchild); /gettop得到的结果也必须是一棵子树才行,进栈应该进的是树根的指针Pop(&S,&p);if(!EmptyStack(S)printf(&quo

14、t;%c",visit(p);Pop(&S,&p);printf("%c",visit(p);Push(&S,p->rchild); /*先序非递归遍历*/ void PreorderTransverse(BinTree T)SeqStack S;BinTree p;initStack(&S);/ 初始化栈Push(&S,T); /根指针进栈Tprintf("先序非递归序列是：")；while(!EmptyStack(S)Pop(&S,&p);/if(p!=NULL) printf(

15、"%c",visit(p); Push(&S,p->rchild); Push(&S,p->lchild); /*后序非递归遍历*/ void PostorderTransverse(BinTree T)SeqStack S;BinTree p,q;initStack(&S);/ 初始化栈p=T;printf("后序非递归序列是：")；while(p |!EmptyStack(S) /为空了if(p!=q)while(p!=NULL)为指向二叉树的指针根节点出栈跳出while循环的原因是因为左子树或者右子树Push(&

16、amp;S,p);if(p->lchild!=NULL) p=p->lchild;elsep=p->rchild; if(EmptyStack(S) break;进栈的是右子树GetTop(S,&q); if(q->rchild=p)/Pop(&S,&p); printf("%c",visit(p); p=q; else p=q->rchild; /*主方法*/ void main()BinTree T;printf("请按照先序的顺序输入创建的树：n");/*创建树*/CreateBinTree(&

17、amp;T);/中序非递归遍历InorderTransverse(T); printf("n"); /先序非递归遍历 PreorderTransverse(T); printf("n"); /后序非递归遍历 PostorderTransverse(T); 四、运行结果1.递归 输入结果配"E:jST3Debug4exe 回 瓯2.非递归输入请按.照先序的顺 锦仄要刘郡嗣12 3 4 5 6 7中文-Q。拼音输入法全二结果。拼音输法gl：12345fc?I 5：1234567Hj|：2345671 continue五、遇到的问题及解决经过一个星期的写代码，我遇到了很多问题，并一一解决了，比如：1 .创建二叉树时：void createBiTree(BiTNode *T)和 void createBiTree(BiTNode *&T) 没分清楚区别。后来查找资料找到 void createBiTree(BiTNode *T)是将结点的指针(地址)传递到函数中进行处理void createBiTree(BiTNode *