2023年湖南省資料總結基礎

1、對一般二叉樹，僅根據乙個先序、中序、後序遍歷，不能確定另乙個遍歷序列。但對於滿二叉樹，任一結點的左右子樹均含有數量相等的結點，根據此性質，可將任一遍歷序列轉為另一遍歷序列（即任一遍歷序列均可確定一棵二叉樹）。

void pretopost(elemtype pre ,post,int l1,h1,l2,h2)

//將滿二叉樹的先序序列轉為後序序列，l1,h1,l2,h2是序列初始和最後結點的下標。

}//pretopost

32. .葉子結點只有在遍歷中才能知道，這裡使用中序遞迴遍歷。

設定前驅結點指標pre，初始為空。第乙個葉子結點由指標head指向，遍歷到葉子結點時，就將它前驅的rchild指標指向它，最後葉子結點的rchild為空。

linkedlist head,pre=null; //全域性變數

linkedlist inorder(bitree bt)

//中序遍歷二叉樹bt，將葉子結點從左到右鏈成乙個單鏈表，表頭指標為head

//處理第乙個葉子結點

else //將葉子結點鏈入鍊錶

inorder(bt->rchild中序遍歷左子樹

pre->rchild=null設定鍊錶尾

}return(head); } //inorder

時間複雜度為o(n)，輔助變數使用head和pre，棧空間複雜度o(n)

2、設有一組初始記錄關鍵字序列（k1，k2，…，kn），要求設計乙個演算法能夠在o(n)的時間複雜度內將線性表劃分成兩部分，其中左半部分的每個關鍵字均小於ki，右半部分的每個關鍵字均大於等於ki。

void quickpass(int r, int s, int t)

r[i]=x;

}3、設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)__;

}}}}

4、兩棵空二叉樹或僅有根結點的二叉樹相似；對非空二叉樹，可判左右子樹是否相似，採用遞迴演算法。

int similar(bitree p,q) //判斷二叉樹p和q是否相似

//結束similar