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

《用递归,非递归两种方法遍历二叉树》由会员分享，可在线阅读，更多相关《用递归,非递归两种方法遍历二叉树（14页珍藏版）》请在金锄头文库上搜索。

1、用递归和非递归实现二叉树的遍历- 1 - 一、设计思想递归实现二叉树遍历的思想: 1. 要遍历二叉树首先的问题是创建二叉树。二叉树的创建可以采用很多的方法。例如：先序， 中序，后序，还可以采用层次的方法创建二叉树。本程序采用的是先序递归的方式创建的二叉树。2. 然后是中序，先序，后序递归遍历二叉树。递归的思想是一直调用方法本身。3. 中序递归遍历二叉树的思想是先访问左子树，然后访问根节点， 最后访问右子树。当访问左子树或是右子树的时候，实际上调用的是函数本身。在这里就体现了递归的思想，当函数的返回值是0 的时候，则返回上一次的程序，继续执行下面的语句。4. 先序递归遍历二叉树的思想是先访问根节

2、点，然后访问左子树， 最后访问右子树。同样如步骤3 的方式相同， 当访问左子树或者是右子树的收，实际上调用的是函数本身，直到返回值是0 的时候，返回上一层的程序继续执行。5. 后序递归遍历二叉树的思想是先访问左子树，然后访问右子树，最后访问根节点。同样跟步骤3 的方式相同，当访问左子树或者右子树的时候实际上是调用的是方法本直到有返回值的时候才返回上一层的程序，继续执行. 非递归实现二叉树遍历的思想: 1. 跟递归遍历二叉树的前提一样，首先应该创建一个二叉树，同样使用先序递归的方式创建二叉树。2. 然后是中序，先序，后序非递归遍历二叉树。3. 中序非递归遍历二叉树的思想是：首先是根节点压栈，当根

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

4、空的时候，则右子树的指针进栈，当右子树的左子树不为空的时候，则左也进栈，直到左为空。重复上面的操作，直到栈为空的时候，则遍历树完成。二、算法流程图递归方法遍历二叉树的流程图如图1用递归和非递归实现二叉树的遍历- 2 - 图 1 递归方法遍历二叉树流程图非递归先序遍历二叉树流程图图 2：非递归先序遍历二叉树流程图开始创建二叉树输入要遍历的二叉树B!=NUll 访问根节点先序遍历 (左子树 ) 先序遍历 (右子树 ) 先序遍历中序遍历B!=N中序遍历 (左子树 ) 访问根节点中序遍历 (右子树 ) 后序遍历B!=NU后序遍历 (左子树 ) 后序遍历 (右子树 ) 访问根节点结束结束结束Y N N

5、Y Y N 开始输入遍历的二叉树创建二叉树根节点进栈栈不空出栈左进栈右进栈访问根Y结束N用递归和非递归实现二叉树的遍历- 3 - 后序非递归遍历二叉树流程图如图 3 图 3 后序非递归遍历二叉树流程图开始指针 P指向根节点*q = pp !=NUL LYP的左孩子 不为空Y将P 入栈并使 p=p-leftC hild输出 p-data, 并使 q=pNP不为空且 （ P的右孩子为空或 p-rightC hild = q)Y栈是否为空N结束p= S.top() 并弹出 栈顶元素YN将P入栈并使p=p-rightChildN输入要遍历的二叉树创建二叉树用递归和非递归实现二叉树的遍历- 4 - 中序

6、非递归遍历二叉树流程图4图 4：中序非递归遍历二叉树流程三、源代码用递归的方式实现二叉树的遍历#include “stdio.h“ #include “conio.h“ #include /*定义二叉树 */ typedef struct node char data; struct node *lchild, *rchild; BinTnode; 开始输入遍历的二叉树创建二叉树根节点进栈栈不空左进栈取栈顶并不为空Y出栈栈不空出栈N右进栈N结束访问栈顶Y用递归和非递归实现二叉树的遍历- 5 - typedef BinTnode * BinTree; /定义二叉树类型的指针/*先序创建二叉树 *

7、/ int CreateBinTree(BinTree *T) /*BinTree 本身是一种类型，是一个指针，是指向结果体指针的类型 */ /这算是问题一/问题二是：关于栈的各种各样的操作，进栈，进的应该是指向树根的指针/ 问 题 三 是 ： 为 什 么 要 定 义 一 个 指 向 指 针 的 指针？char ch; *T=(BinTree)malloc(sizeof(BinTnode); if(!*T) printf(“overflow“); do ch=getchar(); if(ch= ) *T=NULL; return 0; else (*T)-data=ch; CreateBinT

8、ree( CreateBinTree( return 1; while(ch!=0); /*中序递归遍历 */ void InorderTransverse(BinTree s) if (s) InorderTransverse(s-lchild); printf(“%c“, s-data); InorderTransverse(s-rchild); 用递归和非递归实现二叉树的遍历- 6 - /先序递归遍历二叉树void PreOrderTranverseTree(BinTree s) if (s) printf(“%c“, s-data); PreOrderTranverseTree(s-l

9、child); PreOrderTranverseTree(s-rchild); /后序递归遍历二叉树void PostOrderTranverseTree(BinTree s) if (s) PreOrderTranverseTree(s-lchild); PreOrderTranverseTree(s-rchild); printf(“%c“, s-data); /*主方法 */ void main() BinTree T; printf(“ 请按照先序的顺序输入要创建的树:n“); CreateBinTree( /*中序序列创建二叉树*/ printf(“ 中序递归遍历的序列是:“);

10、InorderTransverse(T); printf(“n“); /先序递归遍历printf(“ 先序递归遍历的序列是:“); PreOrderTranverseTree(T); printf(“n“); /后序递归遍历printf(“ 后序递归遍历的序列是:“); PostOrderTranverseTree(T); printf(“n“); 用递归和非递归实现二叉树的遍历- 7 - 用非递归的方式实现二叉树的遍历#include “stdio.h“ #include “conio.h“ #include /*定义二叉树 */ typedef struct node char data;

11、 struct node *lchild, *rchild; BinTnode; typedef BinTnode * BinTree; /定义二叉树类型的指针/*栈的相关操作 */ typedef struct BinTree data100; int top; SeqStack; /*初始化栈 */ void initStack(SeqStack *S) S-top =-1; /*进栈 */ void Push(SeqStack *S,BinTree x) /* 无论是进栈还是取栈顶元素都应该是指向树的指针*/ if(S-top=100-1) printf(“the stack is ov

12、erflow“); else S-top=S-top+1; S-dataS-top=x; 用递归和非递归实现二叉树的遍历- 8 - /*出栈 */ int Pop(SeqStack *S,BinTree *p) if(S-top=-1) printf(“the stack is underflow“); return 0; else *p=S-dataS-top; -S-top; return 1; /*判断栈是不是空*/ int EmptyStack(SeqStack S) if(S.top=-1) return 1; else return 0; /* 栈不空的情况 */ /*取出栈顶元素

13、 */ int GetTop(SeqStack S,BinTree *p) /如果栈顶元素取到的是一颗子树的话，那应该返回的是。 。 。 。 ，栈顶取到的到底应该是什么哈if(S.top=-1) printf(“the stack is empty“); return 0; else *p=S.dataS.top; return 1; 用递归和非递归实现二叉树的遍历- 9 - /访问结点char visit(BinTree p) return (*p).data; /*创建二叉树 */ int CreateBinTree(BinTree *T) /*BinTree 本身是一种类型，是一个指针，

14、是指向结果体指针的类型 */ /这算是问题一/问题二是：关于栈的各种各样的操作，进栈，进的应该是指向树根的指针/ 问 题 三 是 ： 为 什 么 要 定 义 一 个 指 向 指 针 的 指针？char ch; *T=(BinTree)malloc(sizeof(BinTnode); if(!*T) printf(“overflow“); else do ch=getchar(); if(ch!= )*T=NULL; return 0; else (*T)-data=ch; CreateBinTree( CreateBinTree( return 1; while(ch!=0); /*中序非递归

15、遍历*/ void InorderTransverse(BinTree T) SeqStack S; BinTree p; 用递归和非递归实现二叉树的遍历- 10 - initStack(/ 初始化栈printf(“ 中序非递归序列是:“); Push( /根指针进栈T 为指向二叉树的指针while(!EmptyStack(S) /栈不是空的情况while(GetTop(S, /gettop 得到的结果也必须是一棵子树才行,进栈应该进的是树根的指针Pop( if(!EmptyStack(S) /printf(“%c“,visit(p); Pop( printf(“%c“,visit(p); Push( /*先序非递归遍历*/ void PreorderTransverse(BinTree T) SeqStack S; BinTree p; initStack(/ 初始化栈Push( /根指针进栈T 为指向二叉树的指针printf(“ 先序非递归序列是:“); while(!EmptyStack(S) Pop( /根节点出栈if(p!=NULL) printf(“%c“,visit(p); Push( Push( /*后序非递归遍历*/ 用递归和非递归实现二叉树的遍历- 11 - void Post