现在位置: > > 外语学习 > 韩语学习

2013年吉林省数据概述摘要

2013年吉林省数据概述摘要

1、后序遍历最后访问根结点,即在递归算法中,根是压在栈底的。采用后序非递归算法,栈中存放二叉树结点的指针,当访问到某结点时,栈中所有元素均为该结点的祖先。本题要找p和q 的最近共同祖先结点r ,不失一般性,设p在q的左边。后序遍历必然先遍历到结点p,栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时,将栈中元素从栈顶开始逐个到辅助栈中去匹配,第一个匹配(即相等)的元素就是结点p 和q的最近公共祖先。

typedef struct

{BiTree t;int tag;//tag=0 表示结点的左子女已被访问,tag=1表示结点的右子女已被访问

}stack;

stack s[],s1[];//栈,容量够大

BiTree Ancestor(BiTree ROOT,p,q,r)//求二叉树上结点p和q的最近的共同祖先结点r。 {top=0; bt=ROOT;

while(bt!=null ||top>0)

{while(bt!=null && bt!=p && bt!=q) //结点入栈

{s[++top].t=bt; s[top].tag=0; bt=bt->lchild;} //沿左分枝向下

if(bt==p) //不失一般性,假定p在q的左侧,遇结点p时,栈中元素均为p的祖先结点 {for(i=1;i<=top;i++) s1[i]=s[i]; top1=top; }//将栈s的元素转入辅助栈s1 保存 if(bt==q) //找到q 结点。

for(i=top;i>0;i--)//;将栈中元素的树结点到s1去匹配

{pp=s[i].t;

for (j=top1;j>0;j--)

if(s1[j].t==pp) {printf(“p 和q的最近共同的祖先已找到”);return (pp);} }

while(top!=0 && s[top].tag==1) top--; //退栈

if (top!=0){s[top].tag=1;bt=s[top].t->rchild;} //沿右分枝向下遍历

}//结束while(bt!=null ||top>0)

return(null);//q、p无公共祖先

}//结束Ancestor

2、根据二叉排序树中序遍历所得结点值为增序的性质,在遍历中将当前遍历结点与其前驱结点值比较,即可得出结论,为此设全局指针变量pre(初值为null)和全局变量flag,初值为true。若非二叉排序树,则置flag为false。

#define true 1

#define false 0

typedef struct node

{datatype data; struct node *llink,*rlink;} *BTree;

void JudgeBST(BTree t,int flag)

// 判断二叉树是否是二叉排序树,本算法结束后,在调用程序中由flag得出结论。 { if(t!=null && flag)

{ Judgebst(t->llink,flag);// 中序遍历左子树

if(pre==null)pre=t;// 中序遍历的第一个结点不必判断

else if(pre->data<t->data)pre=t;//前驱指针指向当前结点

else{flag=flase;} //不是完全二叉树

相关文档
2013年吉林省数据概述摘要
2013年吉林省数据概述摘要_韩语学习_外语学习_教育专区。2013年吉林省数据概述摘要 1、设有一组初始记录关键字序列(K1,K2,…,Kn) ,要求设计一个算法能够在 O(...
2013年吉林省数据概述摘要
2013年吉林省数据概述摘要_韩语学习_外语学习_教育专区。2013年吉林省数据概述摘要 1、设有一组初始记录关键字序列(K1,K2,…,Kn) ,要求设计一个算法能够在 O(...
2013年吉林省数据概述摘要
2013年吉林省数据概述摘要_韩语学习_外语学习_教育专区。2013年吉林省数据概述摘要 1、设有一组初始记录关键字序列(K1,K2,…,Kn) ,要求设计一个算法能够在 O(...
2013年吉林省数据概述摘要
2013年吉林省数据概述摘要_韩语学习_外语学习_教育专区。2013年吉林省数据概述摘要 1、设一棵树 T 中边的集合为{(A,B),(A,C),(A,D),(B,E),(C,F),...
2013年吉林省数据概述摘要
2013年吉林省数据概述摘要_韩语学习_外语学习_教育专区。2013年吉林省数据概述摘要 1、后序遍历最后访问根结点,即在递归算法中,根是压在栈底的。采用后序非递归...
2013年吉林省数据概述摘要
2013年吉林省数据概述摘要_韩语学习_外语学习_教育专区。2013年吉林省数据概述摘要 1、后序遍历最后访问根结点,即在递归算法中,根是压在栈底的。采用后序非递归...
2014年吉林省数据概述摘要
2014年吉林省数据概述摘要_韩语学习_外语学习_教育专区。2014年吉林省数据概述摘要 1、设t是给定的一棵二叉树,下面的递归程序count(t)用于求得:二叉树t中具有非...
2015年吉林省数据概述摘要
2015年吉林省数据概述摘要_韩语学习_外语学习_教育专区。2015年吉林省数据概述摘要 1、设指针变量 p 指向双向链表中结点 A,指针变量 q 指向被插入结点 B,要求给...
2013年吉林省数据摘要
2013年吉林省数据摘要_韩语学习_外语学习_教育专区。2013年吉林省数据摘要 1、请编写一个判别给定二叉树是否为二叉排序树的算法,设二叉树用 llink-rlink 法存储。...
相关主题
返回顶部
热门文档