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

北京邮电大学
数据结构试验报告
实验名称：实验三树
学生姓名：
班 级：
班内序号：
学 号： 日 期：2014年1月4日
1实验目的
掌握二叉树基本操作的实现方法
了解赫夫曼树的思想和相关概念
学习使用二叉树解决实际问h==NULL)) 〃已到底
return d+1;
else
(
int m = Depth(R->lch,d+1); 〃递归，求左子树深度
int n = Depth(R->rch,d+1 )； 〃递归，求右子树深度
return n>m? n:m; 〃输出较大值
}
}
时间复杂度：O (n)
求路径
void BiTree<T>::path(BiNode<T>* root,char n)//求指定结点到根的路径
(
BiNodevT>* stack[1000]; 〃创建栈
BiNodevT>* s;
inttag[1000]; 〃创建栈所存数据的标签,1表示访问其左孩子，2表示访问右孩子
int top=0;
s=root;
do 〃栈不为空，做此循环
while(s!=NULL)
〃如果当前结点不为空
{
stack[++top]=s;
〃当前节点进栈
tag[top]=l;
〃结点标签为1
s=s->lch;
〃当前结点改为其左孩子
while((top! =0)&&(tag[top] ==2))//如果栈不为空且栈顶元素标签为2则进行循环
if(stack[top] ->data==n) 〃判断栈顶元素是否为指定元素
{
cout« ”路径:”； 〃如果是则栈内元素依次出栈
for(int i=l;i <=top;i++) cout«stack[i]->data;
return;
top-；
}
〃如果不是则栈顶元素出栈
if((top! =0)&&tag[top]== 1)
〃如果栈不为空且栈顶元素标签为1
(
s=stack[top] ->rch;
〃当前结点改为栈顶元素的右孩子
tag[top]=2;
〃栈顶元素的标签置为2
}while(top!=0);
4程序运行结果
4. 1主函数流程图
中序遍历

5实验心得
问题及解决方法
前中后序等遍历方法均运用递归方法，创立二叉树等代码书上均已给出，加以理解后调 用较为轻松，层序遍历运用队列的入队和出队，非递归的算法实现较为复杂，结合书本和相 关资料写出正确代码。
心得体会
数据结构学习中有很多有用、有效而且高度优化的算法，理解原理后可以直接通过函数 或类等形式调用，更加方便和快捷。
下一步改进
对二叉树的操作上，求二叉树深度、前序遍历、中序遍历、后序遍历等函数采用了递归 算法。为了提高运算性能，可以将它们改为非递归算法来实现，对于比较复杂的算法，递归 和非递归的运算时间复杂度差别较大，从性能考虑，应当优先采用非递归算法。
完整源代码
#include<iostream>
using namespace std;
template<class T>
struct Binode 〃节点
{
T data;
Binode<T> *lch;
Binode<T> *rch;
}；
template<class T> 〃树
class Bitree
{
private:
void create(B inode<T> * &R,T data[],int i); void Destroy(Binode<T> *R);
public:
Binode<T>* root;
Bitree(T data[]);
void preorder(B inode<T>*R); 〃前序
void Inorder(Binode<T>*R); 〃中序 void Postorder(Binode<T>*R); 〃后序 void Levelorder(B inode<T>*R); 〃层序 int Depth(Binode<T> *R,int d); 〃深度 void path(Binode<T>* root,char); 〃路径
~Bitree(); 〃销毁
)；
tempi ate<cl ass T>
void Bitree<T>::create(Binode<T>*&R,T data[],int i) 〃递归建立二叉树
{
if(data[i-l]!=O)
{
R=new Binode<T>;
R->data=data[i-l];