《二叉树链表和孩子兄弟链表数据结构在计算机上的实现.docx》由会员分享，可在线阅读，更多相关《二叉树链表和孩子兄弟链表数据结构在计算机上的实现.docx（26页珍藏版）》请在三一办公上搜索。
1、洲*，、碧实验报告课程名称：数据结构指导老师：成绩：实验名称：实验六实验类型：同组学生姓名：一、实验目的和要求（必填）二、实验内容和原理（必填）三、主要仪器设备（必填）四、操作方法和实验步骤五、实验数据记录和处理六、实验结果与分析（必填）七、讨论、心得一、实验目的和要求1. 掌握编程工具的使用2. 掌握二叉树链表和孩子兄弟链表数据结构在计算机上的实现3. 掌握通过计算机编程解决问题的基本方法装二、实验内容和原理订 1.编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相 应的空间。线 2.编写算法完成下列操作：无重复地输出以孩子兄弟链表存储的树T中所有的边（这里的边
2、是指树T本身的分支，而不是孩子兄弟链表所形成的二叉树的分支）。输出的形式为（k1, k2）, ., （ki, kj）, .,其中，ki和kj为树结点中的结点标识。三、主要仪器设备计算机、VC+6.0三、操作方法和实验步骤（1）编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放 相应的空间。1. 打开 VC+6.02. 新建工程 随机字串dsw3. 新建C+源程序输入以下程序代码：#include #include enum MyStatus/用来记录我的程序的返回值情况OK=0,EXCEPTIONERROR,FORMATERROR,OVERFLOW；#define E
3、lemType charstruct BiTNode/定义二叉树的一个结点类型(ElemType data;struct BiTNode *lchild,*rchild;typedef BiTNode *BiTree; /定义二叉树类型(本质上其实是一个节点指针) char *tree=1234|x567|89|a|bc|d|;char *p=tree;int index=0;/*Author:WangBinFunction:构造二叉树T(先序&递归)Create Date：2011/12/12Parameters:BiTree 的指针Return:MyStatusRevise history
4、：*/MyStatus CreateBiTree(BiTree &T)MyStatus shStatus=OK;char ch;ch=*(p+index);index+;if(ch=|)(T=NULL;return OK;else(try(T=(BiTNode *)malloc(sizeof(BiTNode);if(T)(T-data=ch;else(return OVERFLOW;catch (.)(return OVERFLOW;shStatus二CreateBiTree(T-lchild);if (shStatus!=OK)(shStatus二CreateBiTree(T-rchild)
5、;if (shStatus!=OK)(return shStatus;return shStatus;/*Author:WangBinFunction:遍历二叉树（先序&递归）Create Date：2011/12/12Parameters:BiTree的指针Return:MyStatusRevise history：参见课本 p129*/MyStatus PreOrderTraverse(BiTree T)MyStatus shStatus=OK;if(T)(if (T-data)(printf(%3c,T-data);elsereturn EXCEPTIONERROR;shStatus二
6、PreOrderTraverse(T-lchild);if (shStatus!=OK)return shStatus;shStatus二 PreOrderTraverse(T-rchild);if (shStatus!=OK)return shStatus;elsereturn shStatus;/*Author:WangBinFunction:遍历二叉树（中序&递归）Create Date：2011/12/12Parameters:BiTree的指针Return:MyStatusRevise history：*/MyStatus InOrderTraverse(BiTree T)MySta
7、tus shStatus=OK;if(T)shStatus二 InOrderTraverse(T-lchild);if (shStatus!=OK)(return shStatus;if (T-data)(printf(%3c,T-data);else(return EXCEPTIONERROR;shStatus二 InOrderTraverse(T-rchild);if (shStatus!=OK)(return shStatus;else(return shStatus;*Author:WangWenlongFunction:删除二叉树(后序&递归)Create Date：2011/12/
8、19Parameters:BiTree 的指针Return:MyStatusRevise history：*/MyStatus PostOrderTraverseDelete(BiTree &T)(MyStatus shStatus=OK;if(T)(if(T-lchild)(shStatus= PostOrderTraverseDelete(T-lchild);if (shStatus!=OK)(return shStatus;if(T-rchild)(shStatus= PostOrderTraverseDelete(T-rchild);if (shStatus!=OK)(return s
9、hStatus;if (T-data)(delete T;T=NULL;return OK;else(return EXCEPTIONERROR;else(return shStatus;/*Author:WangBinFunction:遍历二叉树（先序&递归），并通过调用删除以x为结点的树Create Date：2011/12/12Parameters:BiTree的指针Return:MyStatusRevise history：*/MyStatus PreOrderDeleteX(BiTree &T)(BiTree *Temp;MyStatus shStatus=OK;if(T)(if (
10、T-data)(if(T-data=x)(PostOrderTraverseDelete(T);return OK;else(return EXCEPTIONERROR;if (T-lchild)(if (T-lchild-data=x)(PostOrderTraverseDelete(T-lchild);return OK;shStatus二 PreOrderDeleteX(T-lchild);if (shStatus!=OK)(return shStatus;else(return OK;if (T-rchild)(if (T-rchild-data=x)(PostOrderTravers
11、eDelete(T-rchild);return OK;shStatus二 PreOrderDeleteX(T-rchild);if (shStatus!=OK)(return shStatus;else(return OK;else(return shStatus;void main()printf( ttt*二叉树递归删除节点*n)printf( ttt*n);printf( ttt*说明：n）；printf( ttt*1.利用二叉链表储存树结构*n)printf( ttt*2.以递归方法遍历树并删除*n)printf( ttt*参照：n）；printf( ttt*数据结构（C语言版）*n
12、)printf(nttt*n)；printf( ttt *n)；BiTree T;MyStatus shStatus=OK;printf(step1.请按先序建立二叉树的结点序列(以|为空结点)：n);shStatus二CreateBiTree(T);if (shStatus=OK)(printf(创建成功！rn);else(printf(创建异常！rn);return ;printf(step2.以先序的方法输出二叉树：rn);shStatus二PreOrderTraverse(T);if (shStatus!=OK)(printf(先序遍历二叉树过程异常！rn);return ;shSta
13、tus二PreOrderDeleteX(T);if (shStatus!=OK)(printf(删除异常！rn);return ;printf(rnstep3.以先序的方法输出结果二叉树:rn);shStatus二PreOrderTraverse(T);while(1)(/main4.编译，运行程序得到结果:实现了用递归算法对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相 应的空间(黄色底标注的模块为我编写的核心模块)。(2)编写算法完成下列操作：无重复地输出以孩子兄弟链表存储的树T中所有的边(这里的 边是指树T本身的分支，而不是孩子兄弟链表所形成的二叉树的分支)。输出的形式为
14、k1, k2), ., (ki, kj), .,其中，ki和kj为树结点中的结点标识。1. 打开VC62. 新建工程 随机字串.dsw3. 新建C+源程序输入以下程序代码：#include #include enum MyStatus/用来记录我的程序的返回值情况(OK=0,EXCEPTIONERROR,FORMATERROR,OVERFLOW;#define ElemType charstruct BiTNode/定义二叉树的一个结点类型(ElemType data;struct BiTNode *lchild,*rchild;typedef BiTNode *BiTree; /定义二叉树类
15、型(本质上其实是一个节点指针) char *tree=ABE|F|CG|DH|I|J|;char *p=tree;int index=0;WangBin构造二叉树T (先序&递归) 2011/12/12BiTree的指针MyStatus/*Author:Function:Create Date：Parameters:Return:Revise history：*/MyStatus CreateBiTree(BiTree &T)(MyStatus shStatus=OK;char ch;ch=*(p+index);index+;if(ch=|)(T=NULL;return OK;else(try
16、(T=(BiTNode *)malloc(sizeof(BiTNode);if(T)(T-data=ch;else(return OVERFLOW;catch (.)(return OVERFLOW;shStatus二CreateBiTree(T-lchild);if (shStatus!=OK)(return shStatus;shStatus二CreateBiTree(T-rchild);if(shStatus!=OK)return shStatus;returnshStatus;/*Author:Function:Create Date：Parameters:Return:WangBin
17、遍历二叉树(先序&递归)2011/12/12BiTree的指针MyStatusRevise history：参见课本 p129*/MyStatus PreOrderTraverse(BiTree T)(MyStatus shStatus=OK;if(T)(if (T-data)(printf(%3c,T-data);else(return EXCEPTIONERROR;shStatus= PreOrderTraverse(T-lchild);if (shStatus!=OK)(return shStatus;shStatus= PreOrderTraverse(T-rchild);if (sh
18、Status!=OK)(return shStatus;else(return shStatus;/*WangBin遍历二叉树(中序&递归)2011/12/12BiTree的指针MyStatusAuthor:Function:Create Date：Parameters:Return:Revise history：*/MyStatus InOrderTraverse(BiTree T)(MyStatus shStatus=OK;if(T)(shStatus= InOrderTraverse(T-lchild);if (shStatus!=OK)(return shStatus;if (T-da
19、ta)(printf(%3c,T-data);else(return EXCEPTIONERROR;shStatus= InOrderTraverse(T-rchild);if (shStatus!=OK)(return shStatus;else(return shStatus; *WangBin遍历二叉树（后序&递归），并输出连接关系2011/12/19BiTree的指针MyStatusAuthor:Function:Create Date：Parameters:Return:Revise history：*/ElemType temp; 递归外变量，存储父节点MyStatus PostO
20、rderTraverse(BiTree T)(MyStatus shStatus=OK;if(T)(/先遍历右子树，很重要if(T-rchild)(printf(%2c,%2c)，temp,T-rchild-data);shStatus= PostOrderTraverse(T-rchild);if (shStatus!=OK)(return shStatus;if(T-lchild)(temp=T-data;/更新父节点printf(2c,%2c)，T-data,T-lchild-data);shStatus二 PostOrderTraverse(T-lchild);if (shStatus
21、!=OK)(return shStatus;if (T-data)(return OK;else(return EXCEPTIONERROR;else(return shStatus;void main()(ttt*说明：n）；ttt*1.利用二叉链表储存树结构*n);ttt*2.以递归方法遍历树并删除*n);ttt*参照：n）；ttt*数据结构（C语言版）*n)ttt*n)tttttt*n)；*二叉树递归删除节点*n);*n);printf(ntttprintf(printf(printf(printf(printf(printf(printf(printf( BiTree T;MyStat
22、us shStatus=OK;printf(step1.请按先序建立二叉树的结点序列(以|为空结点)：n);shStatus二CreateBiTree(T);if (shStatus=OK)(printf(创建成功!rn);else(printf(创建异常！rn)；return ;printf(step2.以先序的方法输出二叉树：rn);shStatus二PreOrderTraverse(T);if (shStatus!=OK)(printf(先序遍历二叉树过程异常！rn)； return ;printf(rn)；shStatus二PostOrderTraverse(T);if (shStatus!=OK)(printf(遍历异常！rn)； return ;while(1)(/main4.编译，运行程序得到结果：实现了用递归算法无重复地输出以孩子兄弟链表存储的树T中所有的边。
