实验报告 实验二 二叉树的建立和遍历

实验二二叉树的建立和遍历一、实验目的1．掌握二叉树的建立算法2．掌握二叉树的前序、中序和后序遍历算法。二、实验环境操作系统和C语言系统三、预习要求复习二叉树的生成及遍历算法，编写完整的程序。四、实验内容要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。具体实现要求：分别利用前序遍历、中序遍历、后序遍历所建二叉树。五、参考算法二叉树的建立算法思路：主要利用二叉树的性质：在编号的完全二叉树中，编号为i的结点如果存在左孩子，则其编号为2i；若其存在右孩子，则其编号为2i+1；若存在父结点，则其编号为i/2取整。对任意二叉树，先按满二叉树对其进行编号，算法中使用一个辅助向量s来存放指向树结点的指针。如s[i]中存放编号为i的结点的指针，即为该结点的地址。当结点编号i=1时，所产生的结点为根结点，同时将指向该结点的指针存入s[1]。当结点编号i1时，产生一个新的结点后，也要将指向该结点的指针存入s[i]，由上述性质可知：j=i/2为它的双亲结点编号。如果i为偶数，则它是双亲结点的左孩子，即让s[j]-lch=s[i]；若i为奇数，则它是双亲结点的右孩子，即让s[j]-rch=s[i]。这样就将新输入的结点逐一与其双亲结点相连，生成二叉树。二叉树的建立也可使用递归算法实现。DEGFABCDEGF可以按如下次序依次输入给定二叉树及左右子树中的各结点值：（1）输入根结点值。（2）若左子树不空，则输入左子树，否则输入一个空格（或其它特殊字符）。（3）若右子树不空，则输入右子树，否则输入一个空格（或其它特殊字符）。如图所示二叉树，按先序遍历次序输入：ABCDEGF(/n)二叉树的遍历算法可以使用递归算法实现，也可采用非递归算法实现，可参考教材上算法实现。参考算法：#includestdio.h#includestring.h#includemalloc.h#includestdlib.h#defineNULL0typedefcharDataType;typedefstructBinTNode{DataTypedata;structBinTNode*rchild,*lchild;}BinTNode,*BinTree;//创建二叉树voidCreate(BinTree*T){charch;if((ch=getchar())=='*')//输入'*'时该节点为空*T=NULL;else{*T=(BinTree)malloc(sizeof(BinTNode));(*T)-data=ch;Create(&(*T)-lchild);Create(&(*T)-rchild);}}//先序遍历二叉树voidPreOrder(BinTreeT){if(T){printf(%c,T-data);PreOrder(T-lchild);PreOrder(T-rchild);}}//中序遍历二叉树voidInOrder(BinTreeT){if(T){InOrder(T-lchild);printf(%c,T-data);InOrder(T-rchild);}}//后序遍历二叉树voidPostOrder(BinTreeT){if(T){PostOrder(T-lchild);PostOrder(T-rchild);printf(%c,T-data);}}voidmain(){BinTreeT;printf(输入先序序列:);Create(&T);printf(输出先序遍历:);PreOrder(T);printf(\n);printf(输出中序遍历:);InOrder(T);printf(\n);printf(输出后序遍历:);PostOrder(T);printf(\n);}六、实验中出现的问题及对问题的解决方案有语法错误和打程序时的拼写错误，主要就是根据出错的地方进行单方面的调试。在算法实现上，从算法的效率看，非递归方法具有较好的时间效率，递归方法书写形式较为简捷，更为直观，一般具有较好的空间效率。在按要求访问树中某些结点的数据元素时，选择一种合适的访问顺序是有必要的。利用树对不同数据元素进行组合，在排序和某些特殊应用情景下是一种不错的选择。七、实验总结通过这个实验加深了我对单链表的认识，学会了简单单链表的建立，查找，插入和删除等基本运算，并对运用C语言上机调试单链表的基本方法有了初步了解。通过这个实验也使我认识到自己编程能力较差，在以后的学习中，应该加强编程方面的学习。