《递归和非递归遍历二叉树》由会员分享，可在线阅读，更多相关《递归和非递归遍历二叉树（16页珍藏版）》请在金锄头文库上搜索。
1、数据结构（双语）项目文档报告递归、非递归两种算法遍历二叉树专 业： 计算机科学与技术 班 级： 指导教师： 苏亚光 姓 名： 学 号： 第 - 2 - 页 共 16 页目 录一、设计思想.3 页二、算法流程图4.页三、源代码10 页四、运行结果. 15 页五、遇到的问题及解决15 页六、心得体会16 页第 - 3 - 页 共 16 页一、设计思想1. 递归遍历二叉树算法思想:1先序遍历：首先判断根结点是否为空，为空则停止遍历，不为空则将左子作为新的根结点重新进行上述判断，左子遍历结束后，再将右子作为根结点判断，直至结束。到达每一个结点时，打印该结点数据，即得先序遍历结果。若二叉树非空，则依次进
2、行如下操作：（1）访问跟结点；（2）前序遍历左子树；（3）前序遍历右子树。2. 中序遍历：首先判断该结点是否为空，为空则结束，不为空则将左子作为根结点再进行判断，打印左子，然后打印二叉树的根结点，最后再将右子作为参数进行判断，打印右子，直至结束。若二叉树非空，则依次进行如下操作：（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。3. 后续遍历：指针到达一个结点时，判断该结点是否为空，为空则停止遍历，不为空则将左子作为新的结点参数进行判断，打印左子。左子判断完成后，将右子作为结点参数传入判断，打印右子。左右子判断完成后打印根结点。若二叉树非空，则依次进行如下操作：（1）后序遍历左子树
3、；（2）后序遍历右子树；（3）访问根结点。2. 非递归遍历二叉树算法思想:1. 先序遍历：建立一个栈，当指针到达根结点时，打印根结点，判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈，将左子作为新的根结点进行判断，方法同上。若当前结点没有左子，则直接将右子打印，同时将右子作为新的根结点判断。若当前结点没有右子，则打印左子，同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子，则当前结点为叶子结点，此时将从栈中出栈一个元素，作为当前的根结点，打印结点元素，同时将当前结点同样按上述方法判断，依次进行。直至当前结点的左右子都为空，且栈为空时，遍历结束。2. 中序遍历：建立
4、一个栈，当指针到达根结点时，把根结点压栈，判断根结点是否有左孩子。有左孩子的话将左孩子，将新结点入栈，然后再将指针指向当前结点的左子，直至左子为空，弹栈一个元素，作为当前结点，打印该栈顶元素，将指针指向当前结点右子，将右子作为新的结点，结点入栈，再次进行上面的判断，直至当前结点右子也为空，则再出栈一个元素作为当前结点，一直到结束，使得当前结点右子为空，且栈空，遍历结束。第 - 4 - 页 共 16 页3. 后续遍历：建立一个栈，然后定义一个 tag，取值为 0，1，0 代表右子没有去过，1 代表去过。初始时指针指向根结点，将根结点压栈，指针指向左子，则将左子作为当前结点，继续判断直至左孩子为
5、null，设 q=null，tag=1。然后取得栈顶元素，设为当前结点，判断当前结点的右孩子是否等于 q，如果相等，则打印当前结点，然后弹出当前结点，并且令 q=当前结点的值。然后继续判断，直至右孩子不等于 q，则将指针指向右孩子，把右孩子设为当前结点，令 tag=0，继续步骤，直到全部元素弹栈，栈为空时，遍历结束。二、 算法流程图开始判断结点是否为空null访问根结点结束先序方式遍历左子树先序方式遍历右子树是否图 1.先序递归流程图第 - 5 - 页 共 16 页开始判断结点是否空按中序方式遍历左子树结束访问根结点按中根遍历方式遍历右子树YN图 2. 中序递归流程图第 - 6 - 页 共 1
6、6 页开始判断结点是否空按后根遍历方式遍历左子树结束按后根遍历方式遍历右子树访问根结点YN图 3 .后序递归流程图第 - 7 - 页 共 16 页开始申请一个栈 stack判断结点是否空输出结点值，压栈，指针指向它的左孩子判断结点是否空弹出栈顶元素，指向结点的右孩子结束判断栈或结点是否空NYNYN图 4 . 先序非递归流程图第 - 8 - 页 共 16 页图 1. 流程图图 2. 流程图图 3. 流程图图 5. 中序非递归流程图开始申请一个 stack判断结点是否空把结点压栈，指针指向它的左孩子判断结点是否空弹栈，设为当前结点，打印结点值，指向右孩子结束判断栈或结点是否空NYYNN第 - 9
7、- 页 共 16 页开始申请一个栈 stack，用一个 bool 变量 tag 标记右孩子已被访问把当前结点压栈，p=p-lchildtop+判断标志 tag 是否为 1输出结点值p = s.pop()p= p-rchild结束NYYNNYYN判断结点是否空判断栈或结点是否为空判断结点是否空图 6. 后序非递归流程图第 - 10 - 页 共 16 页三 、源代码下面给出的是实现递归和非递归遍历二叉树的算法程序的源代码（合并在一起）：#include #include #define MAX 100 /定义堆栈最大容量enum BOOLFalse,True;enum RVISITRchildno
8、visit,Rchildvisit; /在后序遍历二叉树时用来指示是否已访问过右子树typedef struct BiTNode /定义二叉树节点结构char data; /数据域struct BiTNode *lchild,*rchild; /左右孩子指针域BiTNode,*BiTree;typedef struct /定义堆栈结构BiTree elemMAX; /栈区int top; /栈顶指针BiTreeStack;void Initial(BiTreeStack &); /初始化一个堆栈BOOL Push(BiTreeStack &,BiTree); /将一个元素入栈BOOL Pop(
9、BiTreeStack&,BiTree &); /将一个元素出栈BOOL Gettop(BiTreeStack ,BiTree &); /取得堆栈栈顶元素 BOOL StackEmpty(BiTreeStack); /判断堆栈是否已空void CreateBiTree(BiTree &); /生成一个二叉树void PreOrder(BiTree); /先序非递归遍历二叉树void InOrder(BiTree); /中序非递归遍历二叉树void PostOrder(BiTree); /后序非递归遍历二叉树void PreTravel(BiTree ); /先序递归遍历二叉树void MidT
10、ravel(BiTree ); /中序递归遍历二叉树void PostTravel(BiTree ); /后序递归遍历二叉树int main() BiTree T;int flag=1; /标记 BOOL temp;printf(二叉树的递归和非递归遍历n);CreateBiTree(T); /生成一棵二叉树printf (n);第 - 11 - 页 共 16 页printf(递归先序遍历二叉树: );PreTravel(T);printf(n);printf (n);printf(递归中序遍历二叉树: );MidTravel(T);printf(n);printf (n);printf(递归
11、后序遍历二叉树: );PostTravel(T);printf(nnn);if(T)printf (nn);printf(非递归先序遍历二叉树: );PreOrder(T);printf(n);else printf(二叉树为空n);if(T)printf(非递归中序遍历二叉树 : );InOrder(T);printf(n);else printf(二叉树为空n);if(T)printf(非递归后序遍历二叉树 : );PostOrder(T);printf(nnn);else printf(二叉树为空n);void Initial(BiTreeStack &S)S.top=-1; /栈顶指针
12、初始化为-1BOOL Push(BiTreeStack &S,BiTree ch) /将元素 ch 入栈，成功返回 True,失败返回 Falseif(S.top=MAX-1) return False; /判断是否栈满else S.top+; /栈顶指针 top 加一第 - 12 - 页 共 16 页S.elemS.top=ch; /入栈return True;BOOL Pop(BiTreeStack &S,BiTree &ch) /将栈顶元素出栈,成功返回 True，并用 ch 返回该元素值，失败返回 Falseif(S.topdata=ch;CreateBiTree(T-lchild);
13、 /生成左子树CreateBiTree(T-rchild); /生成右子树void PreTravel(BiTree T)/先序遍历if(T) printf(%c,T-data);PreTravel(T-lchild);第 - 13 - 页 共 16 页PreTravel(T-rchild);void MidTravel(BiTree T)/中序遍历if(T) MidTravel(T-lchild);printf(%c,T-data);MidTravel(T-rchild);void PostTravel(BiTree T)/后序遍历if(T) PostTravel(T-lchild);PostTravel(T-rchild);printf(%c,T-data);void PreOrder(BiTree T) /先序非递归遍历以 T 为根结点的二叉树BiTreeStack S;BiTree p;Initial(S);p=T;while(p|!StackEmpty(S) if(p) printf(%c,p-data);Push(S,p);p=p-lchild;else Pop(S,p); p=p-rchild;printf(n);void InOrder(BiTree T) /中序非递归遍历以 T 为根结点的二叉树BiTreeStack S;第 - 14 - 页 共 16 页
