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、對二叉樹的某層上的結點進行運算,採用佇列結構按層次遍歷最適宜。
int leafklevel(bitree bt, int k) //求二叉樹bt 的第k(k>1) 層上葉子結點個數
//last移到指向下層最右一元素
if(level>k) return (leaf層數大於k 後退出執行
}//while }//結束leafklevel
3、兩棵空二叉樹或僅有根結點的二叉樹相似;對非空二叉樹,可判左右子樹是否相似,採用遞迴演算法。
int similar(bitree p,q) //判斷二叉樹p和q是否相似
//結束similar
2023年安徽省資料總結基礎
1 設有一組初始記錄關鍵字為 45,80,48,40,22,78 要求構造一棵二叉排序樹並給出構造過程。2 因為後序遍歷棧中保留當前結點的祖先的資訊,用一變數儲存棧的最高棧頂指標,每當退棧時,棧頂指標高於儲存最高棧頂指標的值時,則將該棧倒入輔助棧中,輔助棧始終儲存最長路徑長度上的結點,直至後序遍歷完...
2023年安徽省資料總結大綱
1 矩陣中元素按行和按列都已排序,要求查詢時間複雜度為o m n 因此不能採用常規的二層迴圈的查詢。可以先從右上角 i a,j d 元素與x比較,只有三種情況 一是a i,j x,這情況下向j 小的方向繼續查詢 二是a i,j void search datatype a int a,b,c,d,d...
2023年安徽省資料總結基礎
int n,s,m,i printf n scanf d n printf s scanf d s printf m m scanf d m if n 1 printf n 0 else r next head 生成迴圈鍊錶 jose head,s,m 呼叫函式 2 設t是一棵滿二叉樹,編寫乙個將t...