实验3 二叉树的应用.docx

实验3 二叉树的应用.docx

《实验3 二叉树的应用.docx》由会员分享，可在线阅读，更多相关《实验3 二叉树的应用.docx（11页珍藏版）》请在冰点文库上搜索。

实验3二叉树的应用

实验五：

二叉树的应用

一、实验预备知识

1树是一种非线性的结构，它具有递归特点。

2二叉树有四种遍历方法，分别为：

先根，后根、中根和层次。

掌握四种遍历的规则。

（每个结点都访问，并且只访问一次）

二、实验目的

1掌握二叉树的逻辑结构特性，以及各种存储结构的特点及适用范围。

2掌握用指针类型描述、访问和处理二叉树的各种运算的实现算法。

三、实验内容

1编写采用二叉链表形式存储的二叉树的创建算法。

2编写二叉树的先序、中序、后序遍历的递归算法、先序和中序的非递归算法和按层遍历的算法。

2编写将一棵二叉树的所有左右子树进行交换的算法。

3编写统计二叉树中叶子结点的算法。

4编写一个主函数，将上面函数连在一起，构成一个完整的程序。

5将实验源程序调试并运行。

四、实验要求

建立的二叉树为：

#include

usingnamespacestd;

typedefchardatatype;

typedefstructnode

{

datatypedata;

structnode*lchild,*rchild;

}bintnode;

typedefbintnode*bintree;

typedefstructstack

{

bintreedata[100];

inttag[100];

inttop;

}seqstack;

创建二叉树算法：

voidCreateBinTree（bintree*t）

{

charch;

if（（ch=getchar（））=='0'）

（*t）=NULL;

else

{

*t=newbintnode;

（*t）->data=ch;

CreateBinTree（&（*t）->lchild）;

CreateBinTree（&（*t）->rchild）;

}

}

前序遍历递归算法：

voidPreorder（bintreet）

{

if（t）

{

cout<data<<"";

Preorder（t->lchild）;

Preorder（t->rchild）;

}

}

中序遍历递归算法：

voidInorder（bintreet）

{

if（t）

{

Inorder（t->lchild）;

cout<data<<"";

Inorder（t->rchild）;

}

}

后序遍历递归算法：

voidPostorder（bintreet）

{

if（t）

{

Postorder（t->lchild）;

Postorder（t->rchild）;

cout<data<<"";

}

}

voidPush（seqstack*s,bintreet）

{

s->data[++s->top]=t;

}

bintreePop（seqstack*s）

{

if（s->top!

=-1）

{

s->top--;

return（s->data[s->top+1]）;

}

else

returnNULL;

}

前序遍历非递归算法：

voidPreorder1（bintreet）

{

seqstacks;

=-1;

while（（t）||!

=-1））

{

while（t）

{

cout<data<<"";

++;

[]=t;

t=t->lchild;

}

if>-1）

{

t=Pop（&s）;

t=t->rchild;

}

}

}

中序遍历非递归算法：

voidInorder1（bintreet）

{

seqstacks;

=-1;

while（（t!

=NULL）||!

=-1））

{

while（t）

{

Push（&s,t）;

t=t->lchild;

}

if!

=-1）

{

t=Pop（&s）;

cout<data<<"";

t->rchild;

}

}

}

层次遍历算法：

voidLevelorder（bintreet）

{

bintreequeue[100];

intfront,rear;

if（t==NULL）

return;

front=-1;

rear=0;

queue[rear]=t;

while（front!

=rear）

{

front++;

cout<data<<"";

if（queue[front]->lchild!

=NULL）

{

rear++;

queue[rear]=queue[front]->lchild;

}

if（queue[front]->rchild!

=NULL）

{

rear++;

queue[rear]=queue[front]->rchild;

}

}

}

遍历叶子节点算法：

voidCountLeaf（bintreet）

{

if（!

t）

return;

if（!

（t->lchild||t->rchild））

cout<data<<"";

CountLeaf（t->lchild）;

CountLeaf（t->rchild）;

}

交换左右子树算法：

voidSwapBinTree（bintreet）

{

bintrees;

if（t）

{

SwapBinTree（t->lchild）;

SwapBinTree（t->rchild）;

s=t->lchild;

t->lchild=t->rchild;

t->rchild=s;

}

}

主函数实现：

voidmain（）

{

bintreeroot;

cout<<"***********************************************************"<

cout<<"请按前序遍历次序顺序读入所要生成的二叉树：

";

CreateBinTree（&root）;

cout<<"***********************************************************"<

cout<<"*******************************************"<

cout<<"递归实现前序遍历结果：

";

Preorder（root）;

cout<

cout<<"\n递归实现中序遍历结果：

";

Inorder（root）;

cout<

cout<<"\n递归实现后序遍历结果：

";

Postorder（root）;

cout<

cout<<"*******************************************"<

cout<<"*******************************************"<

cout<<"非递归实现前序遍历结果：

";

Preorder1（root）;

cout<

cout<<"\n非递归实现中序遍历结果：

";

Inorder（root）;

cout<

cout<<"\n层次遍历结果：

";

Levelorder（root）;

cout<

cout<<"\n叶子结点为：

";

CountLeaf（root）;

cout<

cout<<"*******************************************"<

cout<<"*******************************************"<

printf（"交换左右子树后遍历如下：

"）;

cout<

SwapBinTree（root）;

cout<<"\n递归实现前序遍历结果：

";

Preorder（root）;

cout<

cout<<"\n递归实现中序遍历结果：

";

Inorder（root）;

cout<

cout<<"\n递归实现后序遍历结果：

";

Postorder（root）;

cout<

cout<<"*******************************************"<

}

5、实验结果：