数据结构-二叉树.doc

《数据结构-二叉树.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构二叉树实验报告物理电信0904班邓广志1404090501一．实验目的1、掌握二叉树的结构特征和基本概念，以及各种存储结构的特点；2、.掌握线索二叉树的结构和构造方法；二．实验要求1、选择合适的存储结构，完成二叉树的建立；2、求解二叉树的深度；3、实现二叉树的后序遍历算法；4、实现二叉树中序遍历进行中序线索化；三.实验内容算法分析1.实验一采用链式储存结构构建二叉树，包括空结点的输入，完成输入后，程序自动依次读入各个结点，以空结点作为判断结点位置的主要依据，对每个结点申请一定的存放空间，然后依次存放各结点。二叉树的遍历选用后序遍历，因为三种遍历方法的区别只是将输

2、出结点的位置调换一下就可以实现，所以在此只列举先序遍历方法的设计思想，该函数是用递归的方法依次遍历根结点、左子、右子，中序遍历则是左子、根结点、右子，后序遍历只需将根结点的访问放在最后面执行即可。求树的深度的算法也是用了递归的思想，通过对比左右子树的最大深度完成。2.实验二同样采用链式的存储结构构建二叉树，因为要把二叉树线索化，所以增加LTag和LTag这两个指针域，并初始为O。由于线索化的实质是将二叉链表中的空指针改为指向遍历时得到的前驱或后继的线索，因此线索化的过程即为在遍历过程中修改空指针的过程，附设一个指针pre始终指向刚刚访问过的结点，若指针p指向当前结点，则

3、pre指向他的前驱。具体算法如源程序所示。对于中序遍历线索化二叉树,结点的前驱应是遍历左子树时访问的第一个结点,既左子树最左下方的结点,结点的后继应是遍历右子树时访问的第一个结点,既右子树最左下方的结点。二叉树最左下方的结点没有前驱，最右下方的结点没有后继。四.实验结果输入abcdegf实验结果如下，与理论值相等。实验一实验二五．实验源程序———————————————程序一————————————————#include#includetypedefintStatus;typedefstructBiTNode{chardata;s

4、tructBiTNode*lchild,*rchild;//定义左右孩子指针}BiTNode,*BiTree;StatusCreateBiTree(BiTree&T)//构造二叉链表表示的二叉树T{charch;ch=getchar();//按先序次序输入二叉树中结点的值（一个字符）if(ch=='')T=NULL;//空格字符表示空树else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(0);//分配储存单元T->data=ch;//生成根结点CreateBiTree(T->lchild);//构造左子树CreateB

5、iTree(T->rchild);//构造右子树}return1;}StatusPostOrderTraverse(BiTreeT)//后序遍历二叉树的递归算法{if(T){if(PostOrderTraverse(T->lchild))//先向左走到尽头if(PostOrderTraverse(T->rchild))//向右走到尽头if(printf("%c",T->data))return1;//输出结点数据与结点数目return0;}elsereturn1;}intHeight(BiTreeT)//求二叉树深度的递归算法{if(T==NULL)return0;el

6、se{intm,n;m=Height(T->lchild);//遍历左子树，并将其最大深度的值赋给mn=Height(T->rchild);//遍历右子树，并将其最大深度的值赋给nreturn(m>n)?m+1:n+1;}//选出树的深度的值}voidmain(){printf("请输入表达式的二叉树的形式（先序）：");BiTreeT;CreateBiTree(T);printf("后序是：");PostOrderTraverse(T);printf("");printf("二叉树的深度是：%d",Height(T));}——————————————程序二——

7、———————————————#include#includetypedefenumpointerTag{Link,Thread};//Link==0:指针，Thread==1:线索typedefstructBiThrNode{chardata;structBiThrNode*lchild,*rchild;//左右指针intLTag,RTag;//左右标志}BiThrNode,*BiThrTree;intCreateBiTree(BiTree&T){charch;ch=getchar();if(ch=