二叉搜索樹:或者是一棵空樹,或者具有如下性質:對樹中任一節點X,它的左子樹中的所有關鍵字節點的值都不大於(小於或等於)X的關鍵字值,而它的右子樹中的所有關鍵字節點的值都大於X的關鍵字值。
中序遍歷二叉搜索樹可得到一個關鍵字的有序序列,由小到大排序。
在二叉搜索樹中的插入、刪除、搜索的復雜度等於樹高,即(log(n))。
在二叉搜索樹中找最小節點和最大節點也很方面,如要找最小節點,只需從根節點開始,一直找左子樹,當某個節點沒有左子樹時,該節點就是最小節點,即終止節點就是最小節點。同理,如果要找最大節點,那麼從根節點開始一直找右子樹即可,當某個節點沒有右子樹時,該節點就是最大節點。
二叉樹後序遍歷的特點:最後一個節點肯定是根節點。
二叉樹先序遍歷的特定:第一個節點肯定是根節點。
根據這些知識我們可以解決下列問題:如果一棵二叉搜索樹中存儲了字符’A’, ‘B’,’C’,’D’, ‘E’, ‘F’, ‘G’, ‘H’,判斷下列哪個結果是後序樹遍歷的結果(選C):
A: ADBCEGFH, B: BCAGEHFD, C: BCAEFDHG, D: BDACEFHG