树应用问题.docx

树应用问题.docx

《树应用问题.docx》由会员分享，可在线阅读，更多相关《树应用问题.docx（16页珍藏版）》请在冰点文库上搜索。

树应用问题

（树的应用问题）

●需求分析：

1.树的应用（难度**）

要求：

实现任意形状的树（使用广义表的方式从键盘输入）与二叉树的相互转换的实现。

转换成为二叉树后，请输入该二叉树的前序、中序、后序遍历的序列

●概要设计：

在数据结构的表示中，树（tree）和2叉树之间可以一一对应。

（1）树的节点表示为（数据，第一个孩子，第一个兄弟）

（2）2叉树的数据表示为（数据，左孩子，右孩子）

（3）虽然含义不一样，存储结构却相同，可以一一映射。

注意，树的根节点是没有兄弟的，所以变成2叉树以后，根没有右节点。

（4）若干棵树构成的森林可以转化为一棵2叉树。

第一棵树初始化2叉树，以后每次增加一棵树，都是递归查找2叉树根节点的右子树是否为空，为空的话挂上这棵树，不为空查找它的右子树，直到有孩子为空，把要增加的树变成2叉树，把这棵子树的根节点作为刚才位置的右孩子。

下面这个程序表述了树->2叉树以及，森林->2叉树的转化过程

首先tree->btree有一个转换，然后btree可以addTree（另一个btree）来从森林构造2叉树。

这里我有两棵树，如图（a）,（b）所示，他们构造btree如图（c）所示

   [20]                         [20]

  /| \                       /   \

 [1][2][4]                  [1]  [19]

 /                           / \  /

[3]                        [3] [2][11]

  图（a）                         \   \

                                 [4] [12]

  [19]                               / \

 / | \                           [14] [13]

[11][12][13]                 图（c）

    |

分析：

二叉树的先序遍历是：

若二叉树为空，则空操作；否则，访问根结点，先序遍历左子树，先序遍历右子树。

二叉树的中序遍历是：

若二叉树为空，则空操作；否则，中序遍历左子树，访问根结点，中序遍历右子树。

二叉树的后序遍历是：

若二叉树为空，则空操作；否则，后序遍历左子树，后序遍历右子树；访问个结点。

二叉树的层序遍历是：

在访问二叉树的结点时按照自上而下，从左至右的顺序。

根作为第一层，根的孩子作为第二层，以此类推。

先序遍历二叉树递归算法

StatusPreOrderTraverse（BiTreeT,Status（*Visit）（TElemTypee））{

//采用二叉链表存储结构，Visit是对数据元素操作的应用函数，

//先序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。

//一旦visit（）失败，则操作失败。

if（T）{

  if（Visit（T->data））

　if（PreOrderTraverse（T->lchild,Visit））

if（PreOrderTraverse（T->rchild，Visit）） returnOK;

returnERROR;

}else returnOK;

}//PreOrderTraverse

中序遍历的递归算法

StatusInOrderTraverse（BiTreeT,Status（*Visit）（TElemTypee））{

if（T）{

if（InOrderTraverse（T->rchild，Visit））

if（Visit（T->data））

if（InOrderTraverse（T->rchild，Visit））returnOK;

returnERROR;

}else returnOK;

}//InOrderTraverse

后序遍历递归算法

StatusPostOrderTraverse（BiTreeT,Status（*Visit）（TElemTypee））{

if（T）{

if（PostOrderTraverse（T->lchild,Visst））

if（PostOrderTraverse（T->rchild，Visit）） 

if（Visit（T->data））returnOK;

returnERROR;

}else returnOK;

}//PreOrderTraverse

层次遍历二叉树的非递归算法

StatusLevelOrder（BiTreeT）{

 //按层次遍历二叉树T，Q为队列

 InitQueue（Q）;

 If（T!

=NULL）{//若树非空

EnQueue（Q,T）;//根结点入队列

     While（!

QueueEmpty（Q））{

       DeQueue（Q,b）;    //队首元素出队列

     Visit（b->data）;  //访问结点

       If（b->lchild!

=NULL）EnQueue（Q,b->lchild）;//左子树非空，则入队列

       If（b->rchold!

=Null）EnQueue（Q,b->rchild）;//右子树非空，则入队列

     }//while

 }//if

}LevelOrder

●详细设计

（详细设计见附录）

●调试分析

//遍历二叉树的非递归算法

//编写的方法：

根据树中结点的遍历规律及顺序直接写出其非递归算法。

//先序非递归算法

//【思路】

//假设：

T是要遍历树的根指针，若T!

=NULL

//对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。

//问题：

如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取T的右子树的根指针？

//方法1：

访问T->data（根节点）后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。

//方法2：

访问T->data后，将T->rchild入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T->rchild，出栈，遍历以该指针为根的子树。

//进一步考虑：

对于处理流程中的循环体的直到型、当型+直到型的实现。

//中序非递归算法

//【思路】

//T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。

//问题：

如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取T指针？

//方法：

先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。

//进一步考虑：

对于处理流程中的循环体的直到型、当型+直到型的实现。

//后序非递归算法

//【思路】

//T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。

需要判断根结点的左右子树是否均遍历过。

//可采用标记法，结点入栈时，配一个标志flag一同入栈（0：

遍历左子树前的现场保护，1：

遍历右子树前的现场保护）。

//同时top（初始值为-1）作为栈顶指针，遍历完左子树，top值增加为0，遍历完右子树，top值增加为1。

//首先将T和flag（为0）入栈，遍历左子树；而返回后，修改栈顶flag为1，栈顶元素应为T，遍历右子树；最后访问根结点.

●用户使用说明

1）本程序用于WINDOWSXP系统所编

2）本程序可用VC++编程软件实现

3）本程序可实现二叉树的前序、中序、后序遍历

●测试结果

●附录：

#include

#include

//教材P10

#defineOK1

#defineOVERFLOW-2

#defineERROR0

#defineNULL0

//Status是函数的类型，其值是函数结果状态代码

typedefintStatus;

//本实验中，二叉树的结点中存储的信息为单字母

typedefcharTElemType;

//教材p127二叉树的二叉链存储表示

typedefstructBiTNode{

TElemTypedata;

BiTNode*lchild,*rchild;//左右孩子指针

}BiTNode,*BiTree;

typedefstructstack{//二叉树结点栈

BiTreedata[100];

intflag[100];//标志（0：

遍历左子树前的现场保护，1：

遍历右子树前的现场保护）。

inttop;//栈顶指针

}stack;

typedefstructSqStack{//顺序栈

BiTree*base;//在栈构造之前和销毁之后，base的值为NULL

BiTree*top;//栈顶指针

intstacksize;//当前已分配的存储空间，以元素为单位

}SqStack;

typedefstructqueue{//二叉树结点队列

BiTreedata[100];

intfront;//队头指针

intrear;//队尾指针

}queue;

voidInitStack（SqStack&S）{

//构造一个空栈S

S.base=（BiTree*）malloc（100*sizeof（BiTree））;

if（!

S.base）exit（OVERFLOW）;//存储分配失败

S.top=S.base;

S.stacksize=100;

}

voidPush（SqStack&S,BiTreee）{

//插入元素e为新的栈顶元素

*S.top++=e;//赋值为e并向上移动栈顶指针

}

intPop（SqStack&S,BiTree&e）{//&表引用

//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK;否则返回ERROR

if（S.top==S.base）returnERROR;

e=*（--S.top）;

returnOK;

}

intStackEmpty（SqStackS）{

//若栈为空栈，则返回1，否则返回0

if（S.top==S.base）

return1;

return0;

}

//教材p131算法6.4用（补全的）先序序列建立二叉树

//也就是说，通过添加空结点后，使每个结点全部为2度结点

//例如ABC##DE#G##F###!

StatusCreateBiTree（BiTree&T）

{

charch;

scanf（"%ch",&ch）;//从键盘上输入，'#'字符代表空树

if（ch=='#'）T=NULL;

elseif（ch=='!

'）//使用一个特殊字符，标志输入的结束。

returnOK;

else

{

if（!

（T=（BiTNode*）malloc（sizeof（BiTNode））））

exit（OVERFLOW）;//存储分配失败

T->data=ch;//生成根节点

CreateBiTree（T->lchild）;//构造左子树

CreateBiTree（T->rchild）;//构造右子树

}

returnOK;

}

//访问每个节点的函数，可以完成自己需要的操作，在此仅仅是输出结点

voidVisit（TElemTypee）

{

printf（"%c",e）;

}

//教材p129,算法6.1，前序递归遍历

voidPreOrderTraverse（BiTreeT）

{

if（T）{

Visit（T->data）;

PreOrderTraverse（T->lchild）;

PreOrderTraverse（T->rchild）;

}

}

//中序递归遍历

voidInOrderTraverse（BiTreeT）

{

if（T）{

InOrderTraverse（T->lchild）;

Visit（T->data）;

InOrderTraverse（T->rchild）;

}

}

//后续遍历

voidPostOrderTraverse（BiTreeT）

{

if（T）{

PostOrderTraverse（T->lchild）;

PostOrderTraverse（T->rchild）;

Visit（T->data）;

}

}

//遍历二叉树的非递归算法

//编写的方法：

根据树中结点的遍历规律及顺序直接写出其非递归算法。

//先序非递归算法

//【思路】

//假设：

T是要遍历树的根指针，若T!

=NULL

//对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。

//问题：

如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取T的右子树的根指针？

//方法1：

访问T->data（根节点）后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。

//方法2：

访问T->data后，将T->rchild入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T->rchild，出栈，遍历以该指针为根的子树。

//【算法1】

voidPreOrder（BiTreeT）

{//基于方法一,当型循环

SqStackS;

InitStack（S）;

while（T!

=NULL||!

StackEmpty（S））{

while（T!

=NULL）{

Visit（T->data）;

Push（S,T）;

T=T->lchild;

}

if（!

StackEmpty（S））{

Pop（S,T）;

T=T->rchild;

}

}

}

//进一步考虑：

对于处理流程中的循环体的直到型、当型+直到型的实现。

//中序非递归算法

//【思路】

//T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。

//问题：

如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取T指针？

//方法：

先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。

//【算法】

voidInOrder（BiTreeT）

{//当型循环

SqStackS;//顺序栈

InitStack（S）;

while（T!

=NULL||!

StackEmpty（S））{

while（T!

=NULL）{

Push（S,T）;

T=T->lchild;

}

if（!

StackEmpty（S））{

Pop（S,T）;

Visit（T->data）;

T=T->rchild;

}

}

}

//进一步考虑：

对于处理流程中的循环体的直到型、当型+直到型的实现。

//后序非递归算法

//【思路】

//T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。

需要判断根结点的左右子树是否均遍历过。

//可采用标记法，结点入栈时，配一个标志flag一同入栈（0：

遍历左子树前的现场保护，1：

遍历右子树前的现场保护）。

//同时top（初始值为-1）作为栈顶指针，遍历完左子树，top值增加为0，遍历完右子树，top值增加为1。

//首先将T和flag（为0）入栈，遍历左子树；而返回后，修改栈顶flag为1，栈顶元素应为T，遍历右子树；最后访问根结点.

voidPostOrder（BiTreeT）

{

stacks;//结点栈

s.top=-1;

while（T!

=NULL||s.top!

=-1）

{

while（T）

{

s.top++;

s.flag[s.top]=0;//栈顶标识flag初值为0

s.data[s.top]=T;//将T值赋给栈顶元素

T=T->lchild;

}

while（s.top>=0&&s.flag[s.top]==1）

{

T=s.data[s.top];

printf（"%c",T->data）;

s.top--;

}

if（s.top>=0）

{

T=s.data[s.top];//栈顶元素应为T

s.flag[s.top]=1;//栈顶标识变为1

T=T->rchild;

}

else

{

T=NULL;

}

}

}

voidLevelOrder（BiTreeT）//层序非递归遍历算法

{

queueq;//结点队列q

q.data[0]=T;//临时保存树根T到结点队列中

q.front=0;q.rear=1;//队头指针值为0，队尾值指针为1

while（q.front

{

if（q.data[q.front]）

{

printf（"%c",q.data[q.front]->data）;//输出队头指针指向的结点数据

q.data[q.rear++]=q.data[q.front]->lchild;//队头指针指向的结点的左孩子的值赋给队尾指针指向的结点，且队尾指针值自增1

q.data[q.rear++]=q.data[q.front]->rchild;

q.front++;

}

else

{

q.front++;//队头指针值增加1

}

}

}

intmain（）

{

BiTreebt;

printf（"请输入您要建立的二叉树的先序扩展序列（用#表示空）\n"）;

CreateBiTree（bt）;

printf（"构造二叉树成功!

\n"）;

printf（"先序递归遍历：

"）;

PreOrderTraverse（bt）;

printf（"\n中序递归遍历：

"）;

InOrderTraverse（bt）;

printf（"\n后序递归遍历：

"）;

PostOrderTraverse（bt）;

printf（"\n先序非递归遍历：

"）;

PreOrder（bt）;

printf（"\n中序非递归遍历：

"）;

InOrder（bt）;

printf（"\n后序非递归遍历：

"）;

PostOrder（bt）;

printf（"\n层次非递归遍历：

"）;

LevelOrder（bt）;

printf（"\n"）;

system（"pause"）;

return0;

}