北邮数据结构实验报告3二叉树含源码.docx

《北邮数据结构实验报告3二叉树含源码.docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构实验报告实验名称：实验三——树题目一学生姓名：申宇飞班级：班内序号：03学号：日期：2013年12月3日1．实验要求掌握二叉树基本操作的实现方法根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。二叉树的基本功能：1、二叉树的建立2、前序遍历二叉树3、中序遍历二叉树4、后序遍历二叉树5、按层序遍历二叉树6、求二叉树的深度7、求指定结点到根的路径8、二叉树的销毁9、其他：自定义操作编写测试main()函数测试线性表的正确性2.程序分析2.1存储结构采用二叉树的存储结构，其中每个二叉树的结点定义了一个结构

2、体，该结构体包含三个元素，分别是一个T类型的数据域data，一个指向T类型的指针左孩子，一个指向T类型的指针右孩子，示意图如图所示。采用了队列的存储结构。示意图如图所示：lchdatarchlchdatarchlchdatarchlchdatarchlchdatarchlchdatarch对于二叉树中每个结点的data域的赋值，我们事先把这些data储存在一个数组中，通过对数组元素的调用事先对二叉树中每个结点的data域的赋值。2.2关键算法分析一：二叉树的建立：A．自然语言描述：1首先判断调用的数组是否为空，如果为

3、空，直接将一个已经初始化好的根节点置为空。2如果该数组不为空，则把调用的数组的第一个元素的赋给根节点的data域。3采用递归的思想，分别将根节点的左右孩子作为根节点，递归调用该函数。完成对左右子树的赋值。B．代码详细分析：templatevoidBiTree::Create(Node*&R,T*buf,inti){if(buf[i-1]==0)R=NULL;else{R=newNode;R->data=buf[i-1];Create(R->lch,buf,2*i);Create(R-

4、>rch,buf,2*i+1);}lchdatarchlchdatarchlchdatarchA[2*i]A[2*i+1]重复上述赋值过程，实现递归调用二：前序遍历二叉树：A.自然语言描述：1：建立栈2：判断该栈是否为空并且根节点是否为空指针3：如果根节点不是空指针，则输出它的data域，并且是它入栈4：入栈后将根节点指针指向它的左孩子5：如果根节点是空指针6：则根节点出栈，并且指向根节点的指针指向它的右孩子B.代码详细分析：templatevoidBiTree::Preorder(Node

5、>*R){Stack*>S;while(!S.IsEmpty()

6、

7、(R!=NULL)){if(R!=NULL){Print(R->data);S.Push(R);R=R->lch;}else{R=S.Pop();R=R->rch;}}}三：中序遍历二叉树：A.自然语言描述：1：建立栈2：判断该栈是否为空并且根节点是否为空指针3：如果根节点不是空指针，将它入栈4：入栈后将根节点指针指向它的左孩子5：如果根节点是空指针6：则根节点出栈，输出该节点的data域，并且指向根节点的指针指向它的右孩子B.代码详

8、细分析：templatevoidBiTree::Inorder(Node*R){Stack*>S;while(!S.IsEmpty()

9、

10、(R!=NULL)){if(R!=NULL){S.Push(R);R=R->lch;}else{R=S.Pop();Print(R->data);R=R->rch;}}}四：后序遍历二叉树：A.自然语言描述：1：判断根节点是否为空2：如果根节点不为空3：递归调用后续遍历函数，函数的参数改为根节点的左孩子4：递归调用后续遍历函数，函数的参数

11、改为根节点的右孩子5：输出根节点的data域B.代码详细分析：templatevoidBiTree::Postorder(Node*R){if(R!=NULL){Postorder(R->lch);Postorder(R->rch);Print(R->data);}}}}123五：层序遍历二叉树：A.自然语言描述：1：判断根节点是否为空2：如果根节点不为空3：输出根节点的data域4：递归调用层续遍历函数，函数的参数改为根节点的左孩子5：递归调用层序遍历函数，函数的参数改为跟结点的右孩子B

12、.代码详细分析：templatevoidBiTree::Levelorder(Node*R){Queue*>Q;while(!Q.IsEmpty()

13、

14、(R!=NULL)){if(R!=NULL){Print(R->data);Q.EnQueue(R->lch);Q.EnQueue(R->rch);}