数据结构实验二叉树的应用
二叉树应用
一、实验目的
1 掌握二叉树的逻辑结构特性,以及各种存储结构的特点及适用范围
2 掌握用指针来描述、访问和处理二叉树的各种运算的实现
二、实验内容
1 编写采用二叉链表形式存储的二叉树的创建、先序、中序、后序(递归和非递归算法)和按层遍历的算法。
创建的二叉树:
提示:
(1)创建二叉树算法可参考书P137中的6.8.4节。
(2)创建算法的键盘输入序列为:A B D # # E G # # H # # C # F # #
2 编写一个主函数,将上面函数连在一起,构成一个完整的程序。
3 调试并运行实验源程序。
三、实验结果:
#include
#include
#define StackMaxSize 100
typedef char Elemtype;
//定义二叉树的存储结构体
typedef struct Btnode
{
Elemtype data;
Btnode *lchild;
Btnode *rchild;
}*BtTree;
//定义栈
struct Stack
{
Btnode *stack[StackMaxSize];
int top;
};
//初始化栈
void Initstack(Stack *s)
{
s->top =-1;
}
//进栈
void Push(Stack *s,Btnode *elem)
{
if(s->top ==StackMaxSize-1)
{
cout
exit(1);
}
else
{
s->top++;
s->stack [s->top ]=elem;
}
}
//出栈
Btnode * Pop(Stack *s,BtTree &p)
{
if(s->top ==-1)
{
cout
exit(1);
}
else
{
p=s->stack[s->top ];
s->top --;
}
return p;
}
// 创建二叉树
void CreatBtTree(BtTree &BT)
{
char ch;
cin>>ch;
if (ch=='#')
BT=NULL;
else
{
BT=new Btnode;
BT->data=ch;
CreatBtTree(BT->lchild);
CreatBtTree(BT->rchild);
}
}
//先根遍历递归算法
void preOrdetBT(BtTree BT)
{
if(BT)
{
coutdata ;
preOrdetBT(BT->lchild);
preOrdetBT(BT->rchild);
}
}
//中根遍历递归算法
void InOrdetBT(BtTree BT)
{
if(BT)
{
InOrdetBT(BT->lchild);
coutdata;
InOrdetBT(BT->rchild);
}
}
//后根遍历递归算法
void PostOrdetBT(BtTree BT)
{
if(BT)
{
PostOrdetBT(BT->lchild);
PostOrdetBT(BT->rchild);
coutdata;
}
}
//先根遍历非递归算法
void Pre(BtTree BT)
{
BtTree p;
Stack *s;
s=new Stack;
Initstack(s);
p=BT;
while((p!=NULL)||(s->top >-1))
{
while (p!=NULL)
{
coutdata ;
Push(s,p);
p=p->lchild ;
}
Pop(s,p);
p=p->rchild ;
}
}
//中根遍历的非递归算法
void Midium(BtTree BT)
{
BtTree p;
Stack *s;
s=new Stack;
Initstack(s);
p=BT;
while((p!=NULL)||(s->top >-1))
{
while (p!=NULL)
{
Push(s,p);
p=p->lchild ;
}
Pop(s,p);
coutdata ;
p=p->rchild ;
}
}
//链表结点类型
struct Lnode
{
Btnode *data;
Lnode *next;
};
struct Linkqueue
{
Lnode *front;
Lnode *rear;
};
//队列的初始化
void Initqueue(Linkqueue &Q)
{
Q.front =Q.rear =new Lnode;
Q.front ->next =NULL;
}
//进队算法
void Enqueue(Btnode *elem,Linkqueue &Q)
{
Lnode *s;
s=new Lnode;
s->data =elem;
s->next =NULL;
Q.rear ->next =s;
Q.rear =s;
}
//出队算法
Btnode * Dlqueue(Linkqueue &Q)
{
Lnode *t;
Btnode *elem;
if(Q.front ==Q.rear )
{
cout
}
else
{
if(Q.front ->next ==Q.rear ) //只有一个结点时
{
t=Q.front ->next ;
Q.rear =Q.front ;
Q.front ->next =NULL;
}
else
{
t=Q.front ->next ;
Q.front ->next =t->next ;
}
elem=t->data ;
}
return elem;
}
//按层遍历
void LeverOrdetBT(BtTree BT)
{
Btnode *p=BT;
Linkqueue Q;
Initqueue(Q);
Enqueue(p,Q);
while(Q.front !=Q.rear )
{
p=Dlqueue(Q);
coutdata ;
if(p->lchild !=NULL) Enqueue(p->lchild ,Q);
if(p->rchild !=NULL) Enqueue(p->rchild ,Q);
}
}
void main()
{
BtTree BT=NULL;
CreatBtTree(BT);
cout
preOrdetBT(BT);
cout
cout
InOrdetBT(BT);
cout
cout
PostOrdetBT(BT);
cout
cout
Pre(BT);
cout
cout
Midium(BT);
cout
cout
LeverOrdetBT( BT);
cout
}
程序执行结果为如下图:
四、实验总结:
1. 在先根、中根以及后根的非递归算法中用到了栈来存储,在按层遍历中用到了队列来存储,则涉及到栈的初始化,进栈,出栈,队列的初始化,进队,出队等一系列操作。