2022年用递归,非递归两种方法遍历二叉树 .pdf

《2022年用递归,非递归两种方法遍历二叉树 .pdf》由会员分享，可在线阅读，更多相关《2022年用递归,非递归两种方法遍历二叉树 .pdf（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

4、不为空的时候，则左也进栈，直到左为空。重复上面的操作，直到栈为空的时候，则遍历树完成。二、算法流程图递归方法遍历二叉树的流程图如图1名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 14 页 -用递归和非递归实现二叉树的遍历-2-图 1 递归方法遍历二叉树流程图非递归先序遍历二叉树流程图图 2：非递归先序遍历二叉树流程图开始创建二叉树输入要遍历的二叉树B!=NUll 访问根节点先序遍历(左子树)先序遍历(右子树)先序遍历中序遍历B!=N中序遍历(左子树)访问根节点中序遍历(右子树)后序遍历B!=NU后序遍历(左子树)后序遍历(右子树)访问根节点结束结束结束Y N N Y Y N 开

5、始输入遍历的二叉树创建二叉树根节点进栈栈不空出栈左进栈右进栈访问根Y结束N名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 14 页 -用递归和非递归实现二叉树的遍历-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输入要遍历的二叉树创建二叉树名师资料总结-精品

6、资料欢迎下载-名师精心整理-第 3 页，共 14 页 -用递归和非递归实现二叉树的遍历-4-中序非递归遍历二叉树流程图4图 4：中序非递归遍历二叉树流程三、源代码用递归的方式实现二叉树的遍历#include stdio.h#include conio.h#include /*定义二叉树*/typedef struct node char data;struct node*lchild,*rchild;BinTnode;开始输入遍历的二叉树创建二叉树根节点进栈栈不空左进栈取栈顶并不为空Y出栈栈不空出栈N右进栈N结束访问栈顶Y名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 14 页

7、-用递归和非递归实现二叉树的遍历-5-typedef BinTnode*BinTree;/定义二叉树类型的指针/*先序创建二叉树*/int CreateBinTree(BinTree*T)/*BinTree 本身是一种类型，是一个指针，是指向结果体指针的类型*/这算是问题一/问题二是：关于栈的各种各样的操作，进栈，进的应该是指向树根的指针/问 题 三 是：为 什 么 要 定 义 一 个 指 向 指 针 的 指针？char ch;*T=(BinTree)malloc(sizeof(BinTnode);if(!*T)printf(overflow);do ch=getchar();if(ch=)*

8、T=NULL;return 0;else(*T)-data=ch;CreateBinTree(&(*T)-lchild);CreateBinTree(&(*T)-rchild);return 1;while(ch!=0);/*中序递归遍历*/void InorderTransverse(BinTree s)if(s)InorderTransverse(s-lchild);printf(%c,s-data);InorderTransverse(s-rchild);名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 14 页 -用递归和非递归实现二叉树的遍历-6-/先序递归遍历二叉树vo

9、id PreOrderTranverseTree(BinTree s)if(s)printf(%c,s-data);PreOrderTranverseTree(s-lchild);PreOrderTranverseTree(s-rchild);/后序递归遍历二叉树void PostOrderTranverseTree(BinTree s)if(s)PreOrderTranverseTree(s-lchild);PreOrderTranverseTree(s-rchild);printf(%c,s-data);/*主方法*/void main()BinTree T;printf(请按照先序的顺序

10、输入要创建的树:n);CreateBinTree(&T);/*中序序列创建二叉树*/printf(中序递归遍历的序列是:);InorderTransverse(T);printf(n);/先序递归遍历printf(先序递归遍历的序列是:);PreOrderTranverseTree(T);printf(n);/后序递归遍历printf(后序递归遍历的序列是:);PostOrderTranverseTree(T);printf(n);名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 14 页 -用递归和非递归实现二叉树的遍历-7-用非递归的方式实现二叉树的遍历#include std

11、io.h#include conio.h#include /*定义二叉树*/typedef struct node char data;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)/*无论是进栈还是取栈顶元素都应该是指向树的

12、指针*/if(S-top=100-1)printf(the stack is overflow);else S-top=S-top+1;S-dataS-top=x;名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 14 页 -用递归和非递归实现二叉树的遍历-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(

13、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;名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 14 页 -用递归和非递归实现二叉树的遍历-9-/访问结点char visit(BinTree p)return(*p).data;/*创

14、建二叉树*/int CreateBinTree(BinTree*T)/*BinTree 本身是一种类型，是一个指针，是指向结果体指针的类型*/这算是问题一/问题二是：关于栈的各种各样的操作，进栈，进的应该是指向树根的指针/问 题 三 是：为 什 么 要 定 义 一 个 指 向 指 针 的 指针？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(&(*T)-l

15、child);CreateBinTree(&(*T)-rchild);return 1;while(ch!=0);/*中序非递归遍历*/void InorderTransverse(BinTree T)SeqStack S;BinTree p;名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 14 页 -用递归和非递归实现二叉树的遍历-10-initStack(&S);/初始化栈printf(中序非递归序列是:);Push(&S,T);/根指针进栈T 为指向二叉树的指针while(!EmptyStack(S)/栈不是空的情况while(GetTop(S,&p)&p)Push(&S,

16、p-lchild);/gettop 得到的结果也必须是一棵子树才行,进栈应该进的是树根的指针Pop(&S,&p);if(!EmptyStack(S)/printf(%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);/根指针进栈T 为指向二叉树的指针printf(先序非递归序列是:);while(!EmptyStack(S)Pop(&S,

17、&p);/根节点出栈if(p!=NULL)printf(%c,visit(p);Push(&S,p-rchild);Push(&S,p-lchild);/*后序非递归遍历*/名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 14 页 -用递归和非递归实现二叉树的遍历-11-void PostorderTransverse(BinTree T)SeqStack S;BinTree p,q;initStack(&S);/初始化栈p=T;printf(后序非递归序列是:);while(p|!EmptyStack(S)/跳出 while 循环的原因是因为左子树或者右子树为空了if(p!=

18、q)while(p!=NULL)Push(&S,p);if(p-lchild!=NULL)p=p-lchild;else p=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(&T);/中序非递归遍历名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 14

19、页 -用递归和非递归实现二叉树的遍历-12-InorderTransverse(T);printf(n);/先序非递归遍历PreorderTransverse(T);printf(n);/后序非递归遍历PostorderTransverse(T);四、运行结果非递归方法遍历二叉树的运行结果如图5图 5 非递归方法遍历二叉树的结果图递归方法遍历二叉树的结果图如图6 名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 14 页 -用递归和非递归实现二叉树的遍历-13-图 6 递归遍历二叉树的结果图五、遇到的问题及解决?首先遇到的问题是指针的问题以及指向指针的问题。由于这个问题当时学的时

20、候就没怎么弄清楚，导致现在遇到了很大的问题，可以说是寸步难行吧。基本上就是写不下去了。虽然老师当时上课讲了一遍，但是还是没怎么弄懂。解决办法：重新复习了一遍C语言课本，向同学请教。现在已经弄明白了。例如*p 是给p 指向的变量赋值。&p是取变量P的地址。?当程序写到后序非递归遍历的时候，程序进入了死循环，程序一直不能访问跟节点。访问完右节点之后就进入了死循环。原因是访问根节点的条件没有判断清楚。解决方法是：应该设置一个标志位，当访问完根节点之后，应该继续访问根节点。具体代码的实现如下：while(p|!EmptyStack(S)/跳出 while循环的原因是因为左子树或者右子树为空了 if(p

21、!=q)while(p!=NULL)Push(&S,p);if(p-lchild!=NULL)p=p-lchild;else p=p-rchild;p=q;名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 14 页 -用递归和非递归实现二叉树的遍历-14-else p=q-rchild;?创建树的时候，根节点的左右子树可能有为空的时候，遇到的问题是编程时候，当遇到空子树的时候没有做任何的操作。导致遍历树的时候出错。解决问题的方法是：当遇到空子树的时候，将节点=NULL 具体代码细线如下：if(ch=)*T=NULL;/?return 0;六、心得体会编写程序的时候，首先要做的是知

22、道程序要实现什么功能。不能还没弄清楚题目的要求时就开始编写。这样的话只会让自己走弯路。当明白程序的目的之后，首先找到解决问题的一般思路，解决大部分的功能。然后再考虑极端的情况，也就是很有可能出现的情况，即按照从一般到特殊的思路解决程序。当程序编写完之后。如果还是不能正确的解决问题，就要考虑程序的逻辑有没有错误。找逻辑错误的时候不能根据人的大脑的思路找逻辑错误。应该看程序怎么执行，看电脑的逻辑。把程序写出来并不是代表着程序的结束，调试程序才是最重要的。尤其是当程序出现错误的时候，调试程序变得更加重要。调试程序的目的是找出程序的逻辑错误，当逻辑错误找出来之后，根据单步调试工程，看错误出现在哪一步，改正，即得正确的结果。当程序调试成功之后，要善于总结编写程序中出现的一些常见错误并将他们总结下来，为以后再次变成遇到相同错误的时候提供一种除错的思路。名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 14 页 -