2023年浙江省資料總結摘要

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

若左、右子樹均有，則層次序列根結點的後面應是左右子樹的根；若中序序列中只有左子樹或只有右子樹，則在層次序列的根結點後也只有左子樹的根或右子樹的根。這樣，定義乙個全域性變數指標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; iif (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);

}//演算法結束

2、對二叉樹的某層上的結點進行運算，採用佇列結構按層次遍歷最適宜。

int leafklevel(bitree bt, int k) //求二叉樹bt 的第k(k>1) 層上葉子結點個數

//last移到指向下層最右一元素

if(level>k) return (leaf層數大於k 後退出執行

}//while }//結束leafklevel

3、由二叉樹的前序遍歷和中序遍歷序列能確定唯一的一棵二叉樹，下面程式的作用是實現由已知某二叉樹的前序遍歷和中序遍歷序列，生成一棵用二叉鍊錶表示的二叉樹並列印出後序遍歷序列，請寫出程式所缺的語句。

#define max 100

typedef struct node

tnode;

char pred[max],inod[max];

main(int argc,int **ar**)

tnode *restore(char *ppos,char *ipos,int n)

postorder(tnode*ptr)

2023年浙江省資料總結摘要

1 二叉樹的層次遍歷序列的第乙個結點是二叉樹的根。實際上，層次遍歷序列中的每個結點都是 區域性根 確定根後，到二叉樹的中序序列中，查到該結點，該結點將二叉樹分為 左根右 三部分。若左 右子樹均有，則層次序列根結點的後面應是左右子樹的根 若中序序列中只有左子樹或只有右子樹，則在層次序列的根結點後也只有...

2023年浙江省資料總結摘要

1 約瑟夫環問題 josephus問題 是指編號為1 2 n的n n 0 個人按順時針方向圍坐成一圈，現從第s個人開始按順時針方向報數，數到第m個人出列，然後從出列的下乙個人重新開始報數，數到第m的人又出列，如此重複直到所有的人全部出列為止。現要求採用迴圈鍊錶結構設計乙個演算法，模擬此過程。incl...

2023年浙江省資料總結要領

1 將頂點放在兩個集合v1和v2。對每個頂點，檢查其和鄰接點是否在同乙個集合中，如是，則為非二部圖。為此，用整數1和2表示兩個集合。再用一佇列結構存放圖中訪問的頂點。int bpgraph adjmatrix g 判斷以鄰接矩陣表示的圖g是否是二部圖。初始化，各頂點未確定屬於那個集合 q 1 1 r...