数据结构实验三二叉树实验.doc
文本预览下载声明
数据结构实验报告
实验名称： 实验三——二叉树
学生姓名： XX
班 级：
班内序号：
学 号：
日 期：
1．实验要求
1.1实验目的
通过选择下面两个题目之一进行实现，掌握如下内容：
掌握二叉树基本操作的实现方法
了解赫夫曼树的思想和相关概念
学习使用二叉树解决实际问题的能力
1.2实验内容
根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。
二叉树的基本功能：
1、二叉树的建立
2、前序遍历二叉树
3、中序遍历二叉树
4、后序遍历二叉树
5、按层序遍历二叉树
6、求二叉树的深度
7、求指定结点到根的路径
8、二叉树的销毁
9、其他：自定义操作
编写测试main()函数测试线性表的正确性
2. 程序分析
2.1 存储结构
2.2 关键算法分析
创建一个二叉树
伪代码实现：
1.定义根指针，输入节点储存的data，若输入“#”，则该节点为空；
2.申请一个新节点，判断它的父结点是否不为空，如果不为空在判断其为左或者右孩子，并把地址付给父结点，把data写入。
代码实现
void BiTree::create(BiNode* R,int data[],int i,int n)//创建二叉树
{
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;
}
void BiTree::preorder(BiNode* R)//前序遍历
{
if(R!=NULL)
{coutR-data;
preorder(R-lch);
preorder(R-rch);
}
}
时间复杂度：O(n)
（3）中序遍历
伪代码实现：
设置递归边界条件：if root==null则停止递归
递归遍历左子树
打印根节点数据域内容
递归遍历右子树
代码实现
void BiTree::inorder(BiNode* R)//中序遍历
{
if(R!=NULL)
{inorder(R-lch);
coutR-data;
inorder(R-rch);
}
}
void BiTree::postorder(BiNode* R)//后序遍历
{
if(R!=NULL)
{postorder(R-lch);
postorder(R-rch);
coutR-data;
}
}
coutq-data ;
3.3 若节点q存在左孩子，则将左孩子指针入队
若节点q存在右孩子，则将右孩子指针入队
代码实现
void BiTree::levelordre(BiNode* R)//层序遍历
{
BiNode*queue[maxsize];
int f=0,r=0;
if(R!=NULL)
queue[++r]=R;
while(f!=r)
{BiNode*p=queue[++f];
coutp-data;
if(p-lch!=NULL)
queue[++r]=p-lch;
if(p-rch!=NULL)
queue[++r]=p-rch;
}
}
int BiTree::depth(BiNode* root)//求二叉树深度
{
int ld,rd;
if (root!=NULL)
{ld = 1+depth(root-lch);
rd = 1+depth(root-rch);
return ldrd?ld:rd;
}
else return 0;
}bool BiTree::printPath(BiNode* root, int data)//打印指定结
点到根节点的路径
{
if (root == NULL)
return false;
if (root-data == data || printPath(root-lch,data) ||
printPath(root-rch,data))
{
coutroot-data;
return true;
}
return false;
}
3. 程序运行结果
3.1测试主函数流程图：
3.2测试条件
对如下二叉树： 补全后的二叉树：
按层序遍历的输入方法为：ABC#EFGH###I###J###@
3.3程序运行结果为：
4. 总结
出现的问题及改进：刚开始编译正确但是输出结果异常，纪念馆仔细检查发现二叉树创建有问题，经过仔细修改，发现形参表示错误，*，指针的引用，作为输入时，
显示全部