image.png
image.png
image.png
時間效率:O(n) //每個結點只訪問一次
空間效率:O(n) //棧占用的最大輔助空間
代碼
Status PreOrderTraverse(BiTree T){
if(T==NULL) return OK;
else{
cout<<T->data;
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
Status InOrderTraverse(BiTree T){
if(T==NULL) return OK;
else{
InOrderTraverse(T->lchild);
cout<<T->data;
InOrderTraverse(T->rchild);
}
}
Status PostOrderTraverse(BiTree T){
if(T==NULL) return OK;
else{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data;
}
}
b58f8c5494eef01fb1192796e0fe9925bc317d57.jpg
首先 觀察這個二叉樹
可見是這樣的：1.以B為根節(jié)點的左子樹 A根節(jié)點 以C為根節(jié)點的右子樹
2.以D為根節(jié)點的左子樹 B根節(jié)點 以E為根節(jié)點的右子樹
3.以G為根節(jié)點的左子樹 D根節(jié)點 以H為根節(jié)點的右子樹
4.以K為根節(jié)點的左子樹 C根節(jié)點 以F為根節(jié)點的右子樹
5.以I為根節(jié)點的左子樹 F根節(jié)點 右子樹為空
6.左子樹為空 I根節(jié)點 以J為根節(jié)點的右子樹
接下來可以進行遍歷了：
前序遍歷 是 根 左子樹 右子樹：
即先是跟節(jié)點A 然后遍歷 B子樹 遍歷完B子樹后 再遍歷C子樹 即最后答案為：
ABDGHECKFIJ
中序遍歷為 左子樹 根 右子樹
先遍歷 B子樹 遍歷完了 再是A節(jié)點 然后是右子樹 答案為：
GDHBEAKCIJF
后序遍歷是 左子樹 右子樹 根
答案為：
GHDEBKJIFCA
image.png
試寫出如圖所示的二叉樹分別按先序让虐、中序紊撕、后序遍歷時得到的結點序列。
答：
DLR：A B D F J G K C E H I L M
LDR: B FJ D G KAC H E LI M
LRD：J F K G D B H L M I E C A
