树应用问题.docx
- 文档编号:12405387
- 上传时间:2023-06-05
- 格式:DOCX
- 页数:16
- 大小:49.89KB
树应用问题.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; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 应用 问题