歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
Linux教程網 >> Linux編程 >> Linux編程 >> 關於二叉搜索樹及三種樹遍歷的特點

關於二叉搜索樹及三種樹遍歷的特點

日期:2017/3/1 9:52:55   编辑:Linux編程

二叉搜索樹:或者是一棵空樹,或者具有如下性質:對樹中任一節點X,它的左子樹中的所有關鍵字節點的值都不大於(小於或等於)X的關鍵字值,而它的右子樹中的所有關鍵字節點的值都大於X的關鍵字值。

中序遍歷二叉搜索樹可得到一個關鍵字的有序序列,由小到大排序。

在二叉搜索樹中的插入、刪除、搜索的復雜度等於樹高,即(log(n))。

在二叉搜索樹中找最小節點和最大節點也很方面,如要找最小節點,只需從根節點開始,一直找左子樹,當某個節點沒有左子樹時,該節點就是最小節點,即終止節點就是最小節點。同理,如果要找最大節點,那麼從根節點開始一直找右子樹即可,當某個節點沒有右子樹時,該節點就是最大節點。

二叉樹後序遍歷的特點:最後一個節點肯定是根節點。

二叉樹先序遍歷的特定:第一個節點肯定是根節點。

根據這些知識我們可以解決下列問題:如果一棵二叉搜索樹中存儲了字符’A’, ‘B’,’C’,’D’, ‘E’, ‘F’, ‘G’, ‘H’,判斷下列哪個結果是後序樹遍歷的結果(選C):

A: ADBCEGFH, B: BCAGEHFD, C: BCAEFDHG, D: BDACEFHG

Copyright © Linux教程網 All Rights Reserved