2023年廣西壯族自治區資料總結入門

1、後序遍歷最後訪問根結點，即在遞迴演算法中，根是壓在棧底的。採用後序非遞迴演算法，棧中存放二叉樹結點的指標，當訪問到某結點時，棧中所有元素均為該結點的祖先。本題要找p和q 的最近共同祖先結點r ，不失一般性，設p在q的左邊。

後序遍歷必然先遍歷到結點p，棧中元素均為p的祖先。將棧拷入另一輔助棧中。再繼續遍歷到結點q時，將棧中元素從棧頂開始逐個到輔助棧中去匹配，第乙個匹配（即相等）的元素就是結點p 和q的最近公共祖先。

typedef struct

stack;

stack s,s1;//棧，容量夠大

bitree ancestor(bitree root,p,q,r)//求二叉樹上結點p和q的最近的共同祖先結點r。 //沿左分枝向下

if(bt==p) //不失一般性，假定p在q的左側，遇結點p時，棧中元素均為p的祖先結點//將棧s的元素轉入輔助棧s1 儲存

if(bt==q) //找到q 結點。

for(i=top;i>0;i--)//；將棧中元素的樹結點到s1去匹配

｝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

2、設有乙個陣列中存放了乙個無序的關鍵序列k1、k2、…、kn。現要求將kn放在將元素排序後的正確位置上，試編寫實現該功能的演算法，要求比較關鍵字的次數不超過n。

51. 借助於快速排序的演算法思想，在一組無序的記錄中查詢給定關鍵字值等於key的記錄。設此組記錄存放於陣列r[l..

h]中。若查詢成功，則輸出該記錄在r陣列中的位置及其值，否則顯示「not find」資訊。請編寫出演算法並簡要說明演算法思想。

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; 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==

else

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

return(p);

}//演算法結束