2023年新疆維吾爾自治區資料總結摘要

1、設有一組初始記錄關鍵字為(45，80，48，40，22，78)，要求構造一棵二叉排序樹並給出構造過程。

2、設t是給定的一棵二叉樹，下面的遞迴程式count(t)用於求得:二叉樹t中具有非空的左,右兩個兒子的結點個數n2;只有非空左兒子的個數nl;只有非空右兒子的結點個數nr和葉子結點個數n0。n2、nl、nr、n0都是全域性量，且在呼叫count(t)之前都置為0.

typedef struct node

node;

int n2,nl,nr,n0;

void count(node *t)

26.樹的先序非遞迴演算法。

void example(b)

btree *b;

if (p->lchild!=null)

(3)___; (4)__;

}}}}

3、二叉樹的層次遍歷序列的第乙個結點是二叉樹的根。實際上，層次遍歷序列中的每個結點都是「區域性根」。確定根後，到二叉樹的中序序列中，查到該結點，該結點將二叉樹分為「左根右」三部分。

若左、右子樹均有，則層次序列根結點的後面應是左右子樹的根；若中序序列中只有左子樹或只有右子樹，則在層次序列的根結點後也只有左子樹的根或右子樹的根。這樣，定義乙個全域性變數指標r，指向層次序列待處理元素。演算法中先處理根結點，將根結點和左右子女的資訊入佇列。

然後，在佇列不空的條件下，迴圈處理二叉樹的結點。佇列中元素的資料結構定義如下：

typedef struct

qnode;

bitree creat(datatype in,level,int n)

//由二叉樹的層次序列level[n]和中序序列in[n]生成二叉樹。 n是二叉樹的結點數

qnode s,qq是元素為qnode型別的佇列，容量足夠大

init(q); int r=0; //r是層次序列指標，指向當前待處理的結點

bitree p=(bitree)malloc(sizeof(binode生成根結點

p->data=level[0]; p->lchild=null; p->rchild=null; //填寫該結點資料

for (i=0; i if (in[i]==level[0]) break;

if (i==0) //根結點無左子樹，遍歷序列的1—n-1是右子樹

else if (i==n-1) //根結點無右子樹，遍歷序列的1—n-1是左子樹

else //根結點有左子樹和右子樹

while (!empty(q)) //當佇列不空，進行迴圈，構造二叉樹的左右子樹

else if (i==s.h)

else

}//結束while (!empty(q))

return(p);

}//演算法結束