2023年云南省基础数据高级

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

2、我们可用“破圈法”求解带权连通无向图的一棵最小代价生成树。所谓“破圈法”就是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。

注：圈就是回路。

3、设t是给定的一棵二叉树，下面的递归程序count(t)用于求得：二叉树t中具有非空的左，右两个儿子的结点个数n2；只有非空左儿子的个数nl；只有非空右儿子的结点个数nr和叶子结点个数n0。n2、nl、nr、n0都是全局量，且在调用count(t)之前都置为0.

typedef struct node

int data; struct node *lchild,*rchild;}node;

int n2,nl,nr,n0;

void count(node *t)

if (t->lchild!=null) if (1)__n2++;else nl++;

else if (2)__nr++;else (3)__

if(t->lchild!=null)(4)__if (t->rchild!=null) (5)__

26.树的先序非递归算法。

void example(b)

btree *b;

btree *stack[20], p；

int top;

if (b!=null)

top=1; stack[top]=b;

while (top>0)

p=stack[top]; top--;

printf(“%d”,p->data);

if (p->rchild!=null)

if (p->lchild!=null)