2023年江苏省C语言入门

1、设一棵树t中边的集合为，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。

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

#define true 1

#define false 0

typedef struct node

*btree;

void judgebst（btree t,int flag）

/ 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。

if（t!=null &&flag）

//不是完全二叉树

judgebst （t->rlink,flag）；/中序遍历右子树。

//judgebst算法结束。

3、在有向图g中，如果r到g中的每个结点都有路径可达，则称结点r为g的根结点。编写一个算法完成下列功能：

1）．建立有向图g的邻接表存储结构；

2）．判断有向图g是否有根，若有，则打印出所有根结点的值。

4、后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。本题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。

后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（即相等）的元素就是结点p 和q的最近公共祖先。

typedef struct

//沿左分枝向下。

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)

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);/p无公共祖先。

//结束ancestor