数据结构-二叉树.doc

数据结构二叉树实验报告物理电信0904班邓广志1404090501一 实验目的1、掌握二叉树的结构特征和基本概念，以及各种存储结构的特点；2、.掌握线索二叉树的结构和构造方法；二 实验要求1、选择合适的存储结构，完成二叉树的建立；2、求解二叉树的深度；3、实现二叉树的后序遍历算法；4、实现二叉树中序遍历进行中序线索化；三.实验内容算法分析1.实验一采用链式储存结构构建二叉树，包括空结点的输入，完成输入后，程序自动依次读入各个结点，以空结点作为判断结点位置的主要依据，对每个结点申请一定的存放空间，然后依次存放各结点。二叉树的遍历选用后序遍历，因为三种遍历方法的区别只是将输出结点的位置调换一下就可以实现，所以在此只列举先序遍历方法的设计思想，该函数是用递归的方法依次遍历根结点、左子、右子，中序遍历则是左子、根结点、右子，后序遍历只需将根结点的访问放在最后面执行即可。求树的深度的算法也是用了递归的思想，通过对比左右子树的最大深度完成。2.实验二同样采用链式的存储结构构建二叉树，因为要把二叉树线索化，所以增加LTag和LTag这两个指针域，并初始为O。 由于线索化的实质是将二叉链表中的空指针改为指向遍历时得到的前驱或后继的线索，因此线索化的过程即为在遍历过程中修改空指针的过程，附设一个指针pre始终指向刚刚访问过的结点，若指针p指向当前结点，则pre指向他的前驱。具体算法如源程序所示。对于中序遍历线索化二叉树,结点的前驱应是遍历左子树时访问的第一个结点,既左子树最左下方的结点,结点的后继应是遍历右子树时访问的第一个结点,既右子树最左下方的结点。二叉树最左下方的结点没有前驱，最右下方的结点没有后继。四.实验结果输入abc de g f 实验结果如下，与理论值相等。实验一实验二五实验源程序 程序一#include #include typedef int Status;typedef struct BiTNode char data; struct BiTNode * lchild,* rchild; /定义左右孩子指针BiTNode, *BiTree;Status CreateBiTree(BiTree &T) /构造二叉链表表示的二叉树T char ch; ch=getchar(); /按先序次序输入二叉树中结点的值（一个字符） if(ch= )T=NULL; /空格字符表示空树 else if(!(T=(BiTNode *)malloc(sizeof(BiTNode) exit(0); /分配储存单元 T-data=ch; /生成根结点 CreateBiTree(T-lchild); /构造左子树 CreateBiTree(T-rchild); /构造右子树 return 1; Status PostOrderTraverse(BiTree T) /后序遍历二叉树的递归算法 if(T) if(PostOrderTraverse(T-lchild) /先向左走到尽头 if(PostOrderTraverse(T-rchild) /向右走到尽头 if(printf(%c,T-data) return 1; /输出结点数据与结点数目 return 0; else return 1; int Height(BiTree T) /求二叉树深度的递归算法 if(T=NULL) return 0; else int m,n; m=Height(T-lchild); /遍历左子树，并将其最大深度的值赋给m n=Height(T-rchild); /遍历右子树，并将其最大深度的值赋给n return(mn)? m+1:n+1; /选出树的深度的值 void main() printf(请输入表达式的二叉树的形式（先序）：); BiTree T; CreateBiTree(T); printf(后序是：); PostOrderTraverse(T); printf(n); printf(二叉树的深度是：%dn,Height(T);程序二#include #include typedef enum pointerTag Link, Thread ; / Link=0:指针，Thread=1:线索typedef struct BiThrNode char data; struct BiThrNode *lchild, *rchild; / 左右指针 int LTag, RTag; / 左右标志 BiThrNode, *BiThrTree;int CreateBiTree(BiTree &T) char ch; ch=getchar(); if(ch= )T=NULL; else if(!(T=(BiThrNode *)malloc(sizeof(BiThrNode) exit(0); T-data=ch; if (CreatBiTree(T-lchild) T-LTag=Link; if (CreatBiTree(T-rchild) T-RTag=Link; return 1; Status PreOrderTraverse(BiTree T) if(T) if(printf(%c,T-data) if(PreOrderTraverse(T-lchild) if(PreOrderTraverse(T-rchild) return 1; return 0; else return 1;void InThreading(BiThrTree p) / 对以p为根的非空二叉树进行线索化BiThrTree pre; if (p) InThreading(p-lchild); / 左子树线索化 if (!p-lchild) / 建前驱线索 p-LTag = Thread; p-lchild = pre; if (!pre-rchild) / 建后继线索 pre-RTag = Thread; pre-rchild = p; pre = p; / 保持 pre 指向 p 的前驱 InThreading(p-rchild); / 右子树线索化 int InOrderThreading(BiThrTree &Thrt,BiThrTree T) / 构建中序线索链表 BiThrTree pre; if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode) exit(OVERFLOW);Thrt-LTag=Link;/建头结点Thrt-RTag=Thread;Thrt-rchild=Thrt;/右指针回指if(!T)Thrt-lchild=Thrt;elseThrt-lchild=T;pre=Thrt;InThreading(T);/中序遍历进行中序线索化pre-rchild=Thrt;pre-RTag=Thread;/最后一个结点线索化Thrt-rchild=pre; return 1; void InOrderTraverse_Thr(BiThrTree T)/T指向结点，头结点的左链lchild指向根结点，中序遍历二叉线索树T的非递归算法 p = T-lchild; / p指向根结点 while (p != T) / 空树或遍历结束时，p=T while (p-LTag=Link) p = p-lchild; / 第一个结点 if (!printf(%c,p-data) return ERROR;/访问其左子树为空,输出结点 while (p-RTag=Thread & p-rchild!=T) p = p-rchild; (printf(%c,p-data); / 访问后继结点，输出结