前言

  本篇章主要介紹二叉樹的應(yīng)用之一------二叉排序樹，包括二叉排序樹的定義、查找、插入、構(gòu)造、刪除及查找效率分析。

1. 二叉排序樹的定義

  二叉排序樹 ( B i n a r y (Binary (Binary S o r t Sort Sort T r e e , B S T ) Tree,BST) Tree,BST)，也稱為二叉查找樹，具有以下性質(zhì)：

  (1) 若左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；

  (2) 若右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；

  (3) 左、右子樹也分別是一棵二叉排序樹。

  綜上可知，在二叉排序樹中：左子樹結(jié)點(diǎn)的值 根結(jié)點(diǎn)的值 右子樹結(jié)點(diǎn)的值，所以對(duì)二叉排序樹進(jìn)行中序遍歷，可以得到一個(gè)遞增的有序序列。

2. 二叉排序樹的查找

  二叉排序樹的查找是從根結(jié)點(diǎn)開始，沿某個(gè)分支逐層向下比較的過(guò)程。若二叉排序樹非空，先將給定的關(guān)鍵字與根結(jié)點(diǎn)的關(guān)鍵字進(jìn)行比較，若相等，則查找成功；若不相等，如果小于根結(jié)點(diǎn)的關(guān)鍵字，則在根結(jié)點(diǎn)的左子樹上查找，如果大于根結(jié)點(diǎn)的關(guān)鍵字，則在根結(jié)點(diǎn)的右子樹上查找。

  二叉排序樹的查找算法：

    def BSTSearch(self, k):
        TreeNode = self.RootNode
        while TreeNode is not None and k != TreeNode.data:
            if k  TreeNode.data:
                TreeNode = TreeNode.lchild
            else:
                TreeNode = TreeNode.rchild
        return TreeNode

3. 二叉排序樹的插入

  二叉排序樹作為一種動(dòng)態(tài)樹表，它的結(jié)構(gòu)通常不是一次生成的，而是在查找過(guò)程中，當(dāng)樹中不存在關(guān)鍵字等于給定值的結(jié)點(diǎn)時(shí)插入的。

  插入過(guò)程如下：若二叉排序樹為空，則直接插入結(jié)點(diǎn)；若非空，先將給定的關(guān)鍵字與根結(jié)點(diǎn)的關(guān)鍵字進(jìn)行比較，若小于根結(jié)點(diǎn)的關(guān)鍵字，則插入左子樹，若大于根結(jié)點(diǎn)的關(guān)鍵字，則插入右子樹。插入的結(jié)點(diǎn)一定是一個(gè)新添加的葉結(jié)點(diǎn)，且是查找失敗時(shí)的查找路徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)的左孩子或右孩子。

  二叉排序樹的插入算法：

    def BSTInsert(self, k):
        TreeNode = self.RootNode
        if TreeNode is None:
            self.RootNode = BiTreeLinkNode(k)
            return True
        while True:
            if k  TreeNode.data:
                if TreeNode.lchild is None:
                    TreeNode.lchild = BiTreeLinkNode(k)
                    return True
                TreeNode = TreeNode.lchild
            elif k > TreeNode.data:
                if TreeNode.rchild is None:
                    TreeNode.rchild = BiTreeLinkNode(k)
                    return True
                TreeNode = TreeNode.rchild
            else:
                return False

4. 二叉排序樹的構(gòu)造

  二叉排序樹的構(gòu)造過(guò)程如下：從一棵空樹出發(fā)，依次輸入元素，將它們插入樹中的合適位置。關(guān)鍵字的序列不同，構(gòu)造出來(lái)的二叉排序樹也會(huì)有所不同，比如下圖：

  二叉排序樹的構(gòu)造算法：

    def CreateBST(self):
        for val in self.data_list:
            self.BSTInsert(val)
        return self.RootNode

5. 二叉排序樹的刪除

  在二叉排序樹中刪除一個(gè)結(jié)點(diǎn)時(shí)，不能把以該結(jié)點(diǎn)為根的子樹上的結(jié)點(diǎn)都刪除，必須先把被刪除的結(jié)點(diǎn)從存儲(chǔ)二叉排序樹的鏈表上摘下，將因刪除結(jié)點(diǎn)而斷開的二叉鏈表重新連接起來(lái)，同時(shí)確保二叉排序樹的性質(zhì)不會(huì)丟失。具體分三種情況：

  (1) 如果被刪除的結(jié)點(diǎn)是葉結(jié)點(diǎn)，可以直接刪除；

  (2) 如果被刪除的結(jié)點(diǎn)只有一棵左子樹或右子樹，需要讓該結(jié)點(diǎn)的子樹成為該結(jié)點(diǎn)的父結(jié)點(diǎn)的子樹，以替代被刪除結(jié)點(diǎn)的位置；

  (3) 被刪除的結(jié)點(diǎn)有左子樹和右子樹，需要用該結(jié)點(diǎn)的直接后繼來(lái)代替該結(jié)點(diǎn)的位置，然后從二叉排序樹中刪去這個(gè)直接后繼。

6. 二叉排序樹的查找效率分析

  如果二叉排序樹的左、右子樹的高度之差的絕對(duì)值不超過(guò)1，則這樣的二叉樹稱為平衡二叉樹，它的平均查找長(zhǎng)度為 O ( l o g 2 n ) O(log_2n) O(log2​n)；如果二叉排序樹是一個(gè)只有左子樹或右子樹的單支樹(類似于有序的單鏈表)，則它的平均查找長(zhǎng)度為 O ( n ) 。

  在等概率情況下，有序列 { 2 , 1 , 4 , 3 }成的排序二叉樹的查找成功的平均查找長(zhǎng)度為

  有序列 { 1 , 2 , 3 , 4 } 構(gòu)成的排序二叉樹的查找成功的平均查找長(zhǎng)度為

  二叉排序樹的查找效率主要取決于樹的高度，如果要提高查找效率，在構(gòu)造二叉排序時(shí)最好不要使用有序的序列，盡量構(gòu)造平衡二叉樹。

  有關(guān)平均查找長(zhǎng)度 A S L ASL ASL的知識(shí)會(huì)在查找這部分再說(shuō)。

總結(jié)

到此這篇關(guān)于Python數(shù)據(jù)結(jié)構(gòu)之二叉排序樹的定義、查找、插入、構(gòu)造、刪除的文章就介紹到這了,更多相關(guān)Python二叉排序樹應(yīng)用內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！