typedef struct bitnodebitnode,*bitree;
//按先序序列建立二叉樹
int createbitree(bitree &t)
else
return 0;
} void visit(bitree t)
} //先序遍歷
void preorder(bitree t)
} //中序遍歷
void inorder(bitree t)
} //後序遍歷
void postorder(bitree t)
} /* 先序遍歷(非遞迴)
思路:訪問t->data後,將t入棧,遍歷左子樹;遍歷完左子樹返回時,棧頂元素應為t,出棧,再先序遍歷t的右子樹。
*/void preorder2(bitree t)//while
} <2>中序遍歷
【思路】:t是要遍歷樹的根指標,中序遍歷要求在遍歷完左子樹後,訪問根,再遍歷右子樹。
先將t入棧,遍歷左子樹;遍歷完左子樹返回時,棧頂元素應為t,出棧,訪問t->data,再中序遍歷t的右子樹。
[cpp] view plaincopy
void inorder2(bitree t)//while
} <3>後序遍歷
【思路】:t是要遍歷樹的根指標,後序遍歷要求在遍歷完左右子樹後,再訪問根。需要判斷根結點的左右子樹是否均遍歷過。
[cpp] view plaincopy
//後序遍歷(非遞迴)
typedef struct bitnodepostbitnodepost,*bitreepost;
void postorder2(bitree t)//while
} <4>層次遍歷
【思路】:按從頂向下,從左至右的順序來逐層訪問每個節點,層次遍歷的過程中需要用佇列。
[cpp] view plaincopy
//層次遍歷
void levelorder(bitree t)
} 測試用例:
輸入:abc##de#g##f###
二叉樹遍歷技巧
二叉樹先根序 後根序 中根序遍歷的速演算法 解題技巧 經過研究我找出了一種不用畫圖,由先 後 根序遍歷和中根序遍歷迅速確定遍歷結果的辦法。謹以此文獻給智商與我同級而又不得不研究演算法的朋友。抽象思維太差,用例子來說明吧。下面這個是後根遍歷的演算法。例1 已知某二叉樹的先根序遍歷為abcdefg,中根...
3最優二叉樹
計算機演算法的設計與分析實驗報告 1 描述 在權為wl,w2,wn的n個葉子所構成的所有二叉樹中,帶權路徑長度最小 即代價最小 的二叉樹稱為最優二叉樹或哈夫曼樹。例 給定4個葉子結點a,b,c和d,分別帶權7,5,2和4。構造如下圖所示的三棵二叉樹 還有許多棵 它們的帶權路徑長度分別為 a wpl ...
二叉樹的遍歷
飛機票訂票系統 二 一四年六月 二叉數的遍歷 1 問題陳述 二叉樹的中序 前序 後序的遞迴 非遞迴遍歷演算法,層次序的非遞迴遍歷演算法的實現,應包含建樹的實現。限1 人完成 二叉樹的前序 後序的遞迴 非遞迴遍歷演算法,層次序的非遞迴遍歷演算法的實現,應包含建樹的實現。先序遍歷二叉樹演算法 若二叉樹為...