二叉树的遍历教学文案.doc

《二叉树的遍历教学文案.doc》由会员分享，可在线阅读，更多相关《二叉树的遍历教学文案.doc（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、如有侵权，请联系网站删除，仅供学习与交流二叉树的遍历【精品文档】第 8 页目 录一、设计思想.01二、算法流程图.01三、源代码.04四、运行结果.08五、遇到的问题及解决.09六、心得体会.10一、 设计思想遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结束一层递归调用。直到递归全部结束。 下面重点来讲述非递归方法：首先介绍先序遍历：先序遍历的顺序是根 左 右，也就是说先访问根结点然后访问其左子再然后访问其右子。具体算法实现如下：如果结点的指针不为空，

2、结点指针入栈，输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问， 如此循环，直至结点指针和栈均为空时，遍历结束。 再次介绍中序遍历：中序遍历的顺序是左 根 右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。具体实现算法如下：如果结点指针不为空，结点入栈，指针指向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。如此循环直至结点指针和栈均为空，遍历结束。最后介绍后序遍历：后序遍历的顺序是左 右 根，后序遍历是比较难的一种，首先需要建立

3、两个栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点，如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈，并赋值0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子，父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。如果相应的标志位值为1，表示右子树已经访问完成，此时要输出相应结点的数据，同时将结点指针赋值为空，如此循环直至结点指针和栈均为空，遍历结束。二、 算法流程图下图是定义的二叉树的结构图AB

4、CDEGF图1 二叉树结构图下图是递归算法的流程图，首先的到当前根结点，判断结点指针是否空，如果非空，判断左子指针是否为空，非空则指向左子，左子作为当前根结点，空则判断右子指针是否为空，非空则指向右子，右子作为当前根结点，如果空，输出相应的数据，结束递归。图2 递归算法流程图下图是非递归算法先序遍历的算法流程图，首先对结点指针进行判断，如果指针不为空，结点指针入栈，输出数据，指针指向左子，访问左子树，如果结点指针为空，栈顶结点指针出栈，指针指向右子，访问右子树，直至遍历整个二叉树。图3 非递归先序遍历算法流程图下图是非递归中序遍历算法流程图，首先对结点指针进行判断，如果指针不为空，则指针入栈，

5、指针指向其左子，对左子树进行访问，如果结点指针为空，栈顶结点指针出栈，输出相应的数据，指针指向右子，对右子树进行访问，直至遍历整个二叉树。图4 非递归中序遍历算法流程图下图是非递归后序遍历二叉树算法流程图，首先对结点指针进行判断，如果指针不为空，结点指针和相应的标志位同时入栈，指针指向左子，对左子树进行遍历，如果指针为空，栈顶指针和相应的标志位同时出栈，如果标志位的值为0，则结点再次入栈，标志位置1，随之入栈，指针指向右子，访问右子树，如果标志位的值为1，输出相应结点的数据，并将结点指针置为NULL，直至遍历结束。图5 非递归后序遍历算法流程图三、 源代码#include#define MAX

6、 100 /表示栈的最大容量#define FULL 99/表示栈满#define EMPTY -1/表示栈空typedef struct Tnode /定义结点char data;/存储结点数据 struct Tnode *left;/定义结点左子指针struct Tnode *right;/定义右子指针Tnode,*Pnode;/声明Tnode类型的变量和指针typedef struct Stack/定义栈Pnode pnodeMAX;/存放数据int p;/栈顶指针Stack,*Pstack;/定义Stack类型的变量和指针void Push (Pstack pstack,Pnode p

7、node)/入栈pstack-p +;pstack-pnodepstack-p = pnode;/赋值Pnode Pop(Pstack pstack)/出栈return pstack-pnodepstack-p-;Pnode Top (Pstack pstack)/看栈顶元素return pstack-pnodepstack-p;int Isempty (Pstack pstack)/栈判空if(pstack-p=EMPTY)return 1;else return 0;int Isfull (Pstack pstack )/栈满if (pstack -p=FULL)return 1;else

8、 return 0;void Initstack (Pstack pstack)/初始化栈pstack-p=EMPTY;void Inittnode(Pnode root,Pnode left,Pnode right,char data)/初始化结点root-left=left;root-right = right;root-data = data;void PreorderR(Pnode proot)/递归先序遍历算法if(proot)printf(%2c,proot-data);PreorderR(proot-left);PreorderR(proot-right);void Inorde

9、rR(Pnode proot)/递归中序遍历算法if(proot)InorderR(proot-left);printf(%2c,proot-data);InorderR(proot-right);void PostorderR(Pnode proot)/递归后序遍历算法if(proot)PostorderR(proot-left);PostorderR(proot-right);printf(%2c,proot-data);void PreorderI(Pnode proot,Pstack pstack)/非递归先序遍历算法Initstack(pstack);/初始化栈while(proot

10、|!Isempty(pstack)/如果栈空并且结点指针空，则结束循环if(proot)printf(%2c,proot-data);if(Isfull(pstack)/如果栈满不能执行入栈操作printf(栈满，不能执行入栈操作！);return;Push(pstack,proot);/入栈proot=proot-left;/指针指向左子else if(Isempty(pstack)/栈空时不能出栈printf(栈空，不能执行出栈操作！);return;proot = Pop(pstack);/执行出栈操作proot=proot-right;/指针指向右子void InorderI(Pnod

11、e proot,Pstack pstack)/非递归中序遍历算法Initstack(pstack);/初始化栈while(proot|!Isempty(pstack)/循环结束条件if(proot)if(Isfull(pstack)printf(栈满，不能执行入栈操作！);return;Push(pstack,proot);/执行入栈操作proot = proot-left;/指针指向左子else if(Isempty(pstack)printf(栈空，不能执行出栈操作！);return ;proot = Pop(pstack);/出栈printf(%2c,proot-data);/打印数据p

12、root=proot-right;/指针指向右子void PostorderI(Pnode proot,Pstack pstack)/非递归后续遍历算法int flagsMAX;/定义标志位栈int p =-1;/初始化标志位栈int flag;/存放标志位Initstack(pstack);/初始化栈while(proot|!Isempty(pstack)/循环结束条件if(proot)if(Isfull(pstack)printf(栈满，不能执行入栈操作！);return ;flags+p = 0;/标志位置0，并入栈Push(pstack,proot);/结点入栈proot=proot-

13、left;/指针指向左子elseproot = Pop(pstack);/指针出栈flag = flagsp-;/相应标志位出栈if(flag=0)/如果标志位为0表示右子还未访问过flag =1;/将标志位置1，右子已访问flags+p = flag;/标志位入栈Push(pstack,proot);/结点入栈 proot = proot-right;/指针指向右子else printf(%2c,proot-data);/打印数据proot = NULL;/将结点指针置空void main ()Tnode A,B,C,D,E,F,G;/声明结点变量Stack stack;/声明栈Inittn

14、ode(&A,&B,&C,A);/初始化结点Inittnode(&B,NULL,&D,B);Inittnode(&C,&E,&F,C);Inittnode(&D,NULL,NULL,D);Inittnode(&E,NULL,NULL,E);Inittnode(&F,&G,NULL,F);Inittnode(&G,NULL,NULL,G);printf(你定义的树的结构是：n); /*一下是调用相应的函数输出遍历结果*/printf(A(B(D)C(E F(G)n);printf(=下面是遍历结果=n);printf(=递归先序遍历：=n);PreorderR(&A);printf(n);pri

15、ntf(=非递归先序遍历：=n);PreorderI(&A,&stack);printf(n);printf(=递归中序遍历：=n);InorderR(&A);printf(n);printf(=非递归中序遍历：=n);InorderI(&A,&stack);printf(n);printf(=递归后序遍历：=n);PostorderR(&A);printf(n);printf(=非递归后序遍历：=n);PostorderI(&A,&stack);printf(n);四、 运行结果定义的树的结构为A(B(D)C(EF(G),遍历的结果：图6 程序运行结果五、 遇到的问题及解决这部分我主要遇到如

16、下两个问题，其内容和解决方法如下所列： 执行程序时程序停止运行，其效果如图：图7 问题一截图 解决方法：看到程序停止运行，推测可能的原因：遇到死循环、参数设置不合理或者结构体没有造好。首先对结构体进行了检查，各个成员声明正常无误，在对程序进行调试，程序正常跳出循环，因此最可能是自定义函数的参数设置的不合理，因此对调用的自定义函数进行相应的改动，将参数由具体类型改为指针类型后，程序正常运行。 程序不停的输出同一个结点的数据，其效果入图：图8 问题二截图解决方法：分析运行结果可知，第一不停的输出证明遇到了死循环，第二输出的是同一个结点的数据，表示指针没有按预期进行指向，首先对程序进行调试，发现程序

17、没有添加循环结束条件，添加循环结束条件后，只能输出树的部分结点的数据，对标志位进行修改后，程序运行正常，也能正确输出遍历结果。六、心得体会通过这次作业真的受益匪浅，感触良多：首先，要提高编程能力，必须多动手，多实践，而不是仅仅局限在书本上，更不能眼高手低。眼高手低，懒得动手，这就犯了编程人员的大忌。大一我们开始接触C语言，这是我们接触到的第一种编程语言，但是当时徒有对编程的兴趣，却没有付诸行动，动手少，结果考试险过，通过这次作业，我再次看了C语言课本，边看边写代码，理解快，印象深刻，思维也活跃许多，状态也好，真正的意识到，编程能力需要靠实践来提升。当自己写出意想的程序后，真的有些成就感。再者，在吴老师的指导和要求下，我们改掉了很多的编程坏习惯的同时也养成了良好的编程习惯，另一方面我们态度端正了很多，认真完成好每一项任务，这样无形中提高了对自己的要求，同时也增强了我们的动手能力和编程能力。