文档介绍：北京邮电大学电信工程学院第 1页数据结构实验报告实验名称: 实验三——二叉树学生姓名: XX 班级: 班内序号: 学号: 日期: 1 .实验要求实验目的通过选择下面两个题目之一进行实现,掌握如下内容: ?掌握二叉树基本操作的实现方法?了解赫夫曼树的思想和相关概念?学****使用二叉树解决实际问题的能力实验内容根据二叉树的抽象数据类型的定义,使用二叉链表实现一个二叉树。二叉树的基本功能: 1 、二叉树的建立 2 、前序遍历二叉树 3 、中序遍历二叉树 4 、后序遍历二叉树 5 、按层序遍历二叉树 6 、求二叉树的深度 7 、求指定结点到根的路径 8 、二叉树的销毁 9 、其他:自定义操作编写测试 main() 函数测试线性表的正确性北京邮电大学电信工程学院第 2页 2. 程序分析存储结构关键算法分析(1) 创建一个二叉树伪代码实现: 1. 定义根指针,输入节点储存的 data ,若输入“#”,则该节点为空; 2. 申请一个新节点, 判断它的父结点是否不为空, 如果不为空在判断其为左或者右孩子,并把地址付给父结点,把 data 写入。代码实现 void BiTree::create(BiNode* &R,int data[],int i,int n)// 创建二叉树{ lchild data rchild 二叉树的结点结构 A ∧B ∧∧∧∧∧∧∧ C DEF G 头指针 root 二叉树的二叉链表存储示意图北京邮电大学电信工程学院第 3页 if(i<=n) { R=new BiNode; R->data=data[i-1]; create(R->lch,data,2*i,n); create(R->rch,data,2*i+1,n); } else R=NULL; }(2 )前序遍历伪代码实现: 1. 设置递归边界条件: if root==null 则停止递归 2. 打印起始节点的值,并先后在左子数右子数上递归调用打印函数代码实现 void BiTree::preorder(BiNode* R)// 前序遍历{ if(R!=NULL) {cout<<R->data; preorder(R->lch); preorder(R->rch); }} 时间复杂度: O(n) (3 )中序遍历伪代码实现: 1. 设置递归边界条件: if root==null 则停止递归 2. 递归遍历左子树北京邮电大学电信工程学院第 4页 3. 打印根节点数据域内容 4. 递归遍历右子树代码实现 void BiTree::inorder(BiNode* R)// 中序遍历{ if(R!=NULL) {inorder(R->lch); cout<<R->data; inorder(R->rch); }} 时间复杂度: O(n) (4 )后序遍历伪代码实现: 1. 设置递归边界条件: if root==null 则停止递归 2. 递归遍历左子树 3. 递归遍历右子树 4. 访问根结点数据域代码实现 void BiTree::postorder(BiNode* R)// 后序遍历{ if(R!=NULL) 北京邮电大学电信工程学院第 5页{postorder(R->lch); postorder(R->rch); cout<<R->data; }} 时间复杂度: O(n) (5 )层序遍历伪代码实现 1. 队列 Q 及所需指针的定义和初始化 2. 如果二叉树非空,将根指针入队 3. 循环直到队列 Q 为空 q= 队列 Q 的队头元素出队访问节点 q 的数据域 cout<<q->data<<" "; 若节点 q 存在左孩子,则将左孩子指针入队若节点 q 存在右孩子,则将右孩子指针入队代码实现 void BiTree::levelordre(BiNode* R)// 层序遍历{ BiNode*queue[maxsize]; int f=0,r=0; if(R!=NULL) queue[++r]=R; 北京邮电大学电信工程学院第 6页 while(f!=r) {BiNode*p=queue[++f]; cout<<p->data; if(p->lch!=NULL) queue[++r]=p->lch; if(p->rch!=NULL) queue[++r]=p->rch; }} 时间复杂度: O(n) (6 )计算二叉树深度伪代码实现: 1. 定义和初始化计数深度的参数 2 .如果根节点为空, return0 3. 如果根节点为非空, 递归调用自身的到叶子节点到根的路径长度, 输出其中较大的作为树的深度代码实现 int BiTree::depth(BiNode* root)// 求二叉树深度{ i