数据结构_二叉树_实验报告 北邮.docx

2011级数据结构实验报告实验名称：实验三二叉树学生姓名：班 级：班内序号：学 号：日 期：2012年12月3日1 .实验要求1.1实验目的通过选择下面两个题目之一进行实现，掌握如下内容：> 掌握二叉树基本操作的实现方法> 了解赫夫曼树的思想和相关概念> 学习使用二叉树解决实际问题的能力1.2实验内容根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。二叉树的基本功能：1、二叉树的建立2、前序遍历二叉树3、中序遍历二叉树4、后序遍历二叉树5、按层序遍历二叉树6、求二叉树的深度7、求指定结点到根的路径8、二叉树的销毁9、其他：自定义操作编写测试main()函数测试线性表的正确性2.程序分析2.1存储结构Ichild data rchild二叉树的结点结构二叉树的二叉链表存储示意图2.2关键算法分析(1) 创建一个二叉树通过构造函数创建一个二叉树，构造函数通过调用函数creat()创建二 叉树关于函数creat()的伪代码：1. 定义根指针，输入节点储存的data，若输入“#”，则该节点为空；2. 申请一个新节点，判断它的父结点是否不为空，如果不为空在判断其为左或 者右孩子，并把地址付给父结点，把data写入。char ch;BiNode<T> *Q100; int front,rear; BiNode<T> *root,*S; root=NULL; front=1;rear=0;cout<<("按层次输入二叉树虚结点输入'#'，以' '结束输入n)； cin>>ch;while(ch!='')S=NULL;if(ch!='#')S=new BiNode<T>S->data=ch;S->lchild=NULL;S->rchild=NULL;rear+;Qrear=S; /结点入队if(rear=1) root=S; else while(Qfront= NULL&&front<rear) / 如果父结点为空则跳过 front+;if (front=rear) break;if(rear%2=0)Qfront->lchild=S;/新结点为父结点的左孩子else Qfront->rchild=S; /新结点为父结点的右孩子 front+; cin>>ch;return root; （2）前序遍历伪代码：1. 设置递归边界条件：if root=null则停止递归2. 打印起始节点的值，并先后在左子数右子数上递归调用打印函数if(root=NULL) return;elsecout<<root->data<<""PreOrder(root->lchild);PreOrder(root->rchild);时间复杂度：O(n)(3) 中序遍历伪代码：1. 设置递归边界条件：if root=null则停止递归2. 递归遍历左子树3. 打印根节点数据域内容4. 递归遍历右子树if (root=NULL) return;/递归调用的结束条件 elseInOrder(root->lchild);/中序递归遍历root的左子树cout<<root->data<<""访问根结点的数据域InOrder(root->rchild);/中序递归遍历root的右子树时间复杂度：O(n)(4) 后序遍历伪代码:1. 设置递归边界条件：if root=null则停止递归2. 递归遍历左子树3. 递归遍历右子树4. 访问根结点数据域if (root=NULL) return;/递归调用的结束条件elsePostOrder(root->lchild);/后序递归遍历root的左子树PostOrder(root->rchild);/后序递归遍历root的右子树cout<<root->data<<""/访问根结点的数据域时间复杂度：O(n)(5) 层序遍历1. 队列Q及所需指针的定义和初始化2. 如果二叉树非空，将根指针入队3. 循环直到队列Q为空3.1 q二队列Q的队头元素出队3.2访问节点q的数据域 cout<<q->data<<""3.3若节点q存在左孩子，则将左孩子指针入队if (q->lchild != NULL)Qrear+ = q->lchild;3.4若节点q存在右孩子，则将右孩子指针入队if (q->rchild != NULL)时间复杂度：O(n)(6) 计算二叉树深度伪代码：1. 定义和初始化计数深度的参数2. 如果根节点为空，returnO3. 如果根节点为非空，递归调用自身的到叶子节点到根的路径长度，输出 其中较大的作为树的深度if(!root)return 0;if(ldeep > rdeep)/空二叉子树深度为0 /ldee p就是每个“二叉树”的左子树深度。return ldeep + 1;/rdeep就是每个“二叉树”的右子树深度。时间复杂度：O(n)(7) 计算树的叶结点数伪代码：1. 如果根节点是空的，则返回0；2. 如果有根节点，且左右结点均为空，则返回1；3. 其他情况则递归调用LeafNode函数遍历树，计算最左右支的结点和。（8）计算树的总结点数伪代码：1. 如果根节点是空的，则返回0；2. 其他情况则递归调用NodeCount函数，计算所有结点的和。（9）输出指定结点到根结点的路径伪代码：1. 建立一个存储路径结点结构，定义和初始化结构体的数组2. 当root不为空或top为0时，进入循环3. 当此时root所指的节点的数据不为指定数据时，将root指向它 的左孩子4. 当此时root所指的节点的数据为指定数据时，访问其数据域并 输出struct stack/创建结构来存储路径结点BiNode<T> *bt;int tag;root=root->lchild;/将指针root指向此时节点的左孩子for（int i=top;i>=1;i-）3.cout<<一”<<si.bt->data;/访问数据域并以与查找逆序的 方法输出到根节点的路径。程序运行结果3.1测试主函数流程图:调用构造函数创建一棵树口 一前序遍历并输出结果JZL中序遍历并输出结果后序遍历并输出结果口 一层序遍历并输出结果输出叶子结点的总数输出总结点数求树的深度并输出输入需要寻找路径的结点并输出路径3.2测试条件对如下二叉树:补全后的二叉树:按层序遍历的输入方法为：ABC#EFGH#I#J#3.3程序运行结果为:4.总结1. 本次实验内容相对基础，很多代码在书上都能找到，但是写程序的时候还是遇到了一 些问题，特别是在参数传递方面很容易出错，因为本次实验的很多算法都依靠递归来实现， 递归具有代码简洁但理解不易的特点，特别是在参数传递方面，要通过作图等方式才能搞清 楚整个递归过程。2. 由于单单靠前序、中序、后序或者层序，都无法唯一确定的建立一个二叉树，所以课 本上提供的算法是输入按一定规则补全后的二叉树，首先应该明白输入的规则，要不然程序 运行也很容易出错。3. 本程序多了两个计算结点的函数，本来最开始想编一个打印树的函数，可是发现定位 光标的位置实在非常有难度，而且采用本程序的存储结构好像很难实现，只好作罢，但是还 是很希望能有机会编出来。4. 开始的时候也是写了按前序遍历创树的，用了简单的递归调用，但是发现输入会有许 多不便。所以很希望可以按层输入，于是做了尝试，虽然代码可能写的不是很简单，但是终 于实现了按层输入。在c+语言的编写中就应该使其有更好的实用性，并敢于尝试，不断改 进。