二叉树的遍历学习心得.doc

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

1、二叉树的遍历学习心得 数据结构程序设计报告 学院：班级：学号： 姓名： 实验名称：二叉树的建立与遍历 一、实验目的： 1.掌握二叉树的二叉链表存储结构； 2.掌握二叉树创建方法； 3.掌握二叉树的先序、中序、后序的递归实现方法。 二、实验内容和要求： 创建二叉树，分别对该二叉树进行先序、中序、后序遍历，并输出遍历结果。 三、叉树的建立与遍历代码如下： #include#includestructtnode/结点结构体 ;typedefstructtnodetnode; tnode*creat（void）tnode*root，*p;tnode*queue50;chardata;structtno

2、de*lchild，*rchild; intfront=0，rear=-1，counter=0;/初始队列中需要的变量front、rear和计数器countercharch;printf（”建立二叉树，请输入结点：（#表示虚节点，。表示结束）n”）; ch=getchar; while（ch。=。）if（ch。=#） p=（tnode*）malloc（sizeof（tnode）; p-data=ch; p-lchild=null; p-rchild=null;rear+; queuerear=p;/把非#的元素入队 if（rear=0）/如果是第一个元素，则作为根节点 else if（coun

3、ter%2=1）/奇数时与其双亲的左子树连接 if（counter%2=0）/偶数时与其双亲的右子树连接 queuefront-rchild=p;queuefront-lchild=p;root=p;counter+; front+; counter+; else/为#时，计数，但不连接结点 if（counter%2=0） front+;counter+; ch=getchar;returnroot;voidpreorder（tnode*bt）/先序遍历 if（bt。=null） printf（”%c “，bt-data）;preorder（bt-lchild）;preorder（bt-rch

4、ild）; voidinorder（tnode*bt）/中序遍历 if（bt。=null） inorder（bt-lchild）;printf（”%c “，bt-data）;inorder（bt-rchild）; voidpostorder（tnode*bt）/后序遍历 if（bt。=null） postorder（bt-lchild）;postorder（bt-rchild）;printf（”%c “，bt-data）; intmain tnode*root; root=creat;printf（”递归先序遍历是：”）; preorder（root）; printf（”n”）;printf（

5、”递归中序遍历是：”）;inorder（root）;printf（”n”）; printf（”递归后序遍历是：”）;postorder（root）;printf（”n”）;return0; 四、程序运行结果： 五、程序设计指导： 1.创建二叉树的算法。首先对一般的二叉树，添加若干个虚结点使其成为完全二叉树，然后依次输入结点信息，若输入的结点不是虚结点，则建立一个新结点，若是第一个，则令其为根结点，否则将新结点链接至它的双亲结点上。如此重复下去，直至遇到输入结束符（自定）为止。为了使新结点能够与双亲结点正确相连，并考虑到这种方法中先建立的结点其孩子结点也一定先建立的特点，可以设置一个指针类型的数

6、组构成的队列来保存已输入结点的地址，并使队尾（rear）指向当前输入的结点，队头（front）指向这个结点的双亲结点的前一个位置。由于根结点的地址放在队列的第一个单元里，所以当rear为奇数时，则rear所指的结点应作为左孩子与其双亲链接，否则rear所指的结点应作为右孩子与其双亲链接。若双亲结点或孩子结点为虚结点，则无须链接。若一个双亲结点与两个孩子链接完毕，则进行出队操作，使队头指针指向下一个待链接的双亲结点。 2.voidpreorder（tnode*bt）函数：利用递归的思想，不断嵌套循环，读取结点元素，在每个循环中每次先读取，再进行进入下一个递归循环中。 3.voidinorder（

7、tnode*bt）函数。利用递归的思想，不断嵌套循环，读取结点元素，在每个循环中每次先左子树，再读取结点元素，再进行进入下一个递归循环中。 4.voidpostorder（tnode*bt）函数：利用递归的思想，不断嵌套循环，读取结点元素，在每个循环中每次先分别进入左右子树，再进行读取，再进行进入下一个递归循环中。 六、心得体会： 本次数据结构程序设计对我有一定的帮助。通过这次的实践，使我对数据结构这门课程有了更深入地了解。在写程序的过程中，我重复地读课本上的知识，并且渐渐领悟到数据结构编程的方法。在编程中，虽然遇到了一些困难，但我并不气馁。当程序运行出来时，我感到了快乐。总之，通过自己地探索和努力，思维得到了锻炼，编程能力也有了较大地改善。 第 5 页 共 5 页免责声明：图文来源于网络搜集，版权归原作者所以若侵犯了您的合法权益，请作者与本上传人联系，我们将及时更正删除。