二叉搜索樹的python實現

shixinzhang 發布于2019-07-31 11:05 / 2271人閱讀

摘要：二叉搜索樹不一定是完全二叉樹，因此不能像堆一樣可以數組表示。在當前為根節點的子樹中，查找為的節點。否則遞歸地到左右子樹中找到為的節點，并更新。當當前節點有左孩子時，獲得左子樹中最小的節點。以上是我所了解的二叉搜索樹的基本功能

二叉查找樹或者是一棵空樹，或者是具有下列性質的二叉樹：若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；它的左、右子樹也分別為二叉排序樹。
二叉搜索樹不一定是完全二叉樹，因此不能像堆一樣可以數組表示。
定義一個TNode類來實例化節點，有key,value,l_child,r_child屬性。其中key,value通過構造函數傳入，l_child,r_child初始化為None。

再定義一個BSTree類，根節點初始化為None。

然后給BSTree添加以下方法：
insert(key,value) 插入一個節點
update(key,value) 更新節點的值
search(key) 通過key來找相應節點的value
remove(key) 通過key來刪除樹中相應節點
以及深度優先和廣度優先的遍歷方法。

insert:
傳入參數key,value，插入一個新的節點。但是如果樹中已經存在key為key的節點，就將插入操作轉變為更新操作。

 def __insert(self, key, value, curr_node):
        if curr_node is None:
            return TNode(key, value)

        if key < curr_node.key:
            curr_node.l_child = self.__insert(key, value, curr_node.l_child)

        elif key > curr_node.key:
            curr_node.r_child = self.__insert(key, value, curr_node.r_child)

        else:
            curr_node.value = value

        return curr_node

當當前的節點為None時，根據參數中的key和value建立新的節點，并返回這個節點。當key值小于當前節點的key時，將新節點插入到當前節點的左子樹的相應位置，然后返回當前節點。同理key值大于當前節點的key時，將新節點插入到當前節點的右子樹的相應位置，返回當前節點。如果key等于當前節點key，將插入操作改變為更新操作。

search:

    def __search(self, node, key):
        if node:
            if node.key == key:
                return node
            elif node.key > key:
                return self.__search(node.l_child, key)
            else:
                return self.__search(node.r_child, key)

        return False

在當前node為根節點的子樹中，查找key為key的子節點，如果當前node的key值與參數相同，返回當前節點。否則遞歸地到左右子樹中找key為key的節點，如果沒有找到，最終返回False。

update:

  def __update(self, key, value, node):
        if node:
            if node.key == key:
                node.value = value
            elif node.key > key:
                self.__update(key, value, node.l_child)
            else:
                self.__update(key, value, node.r_child)

在當前node為根節點的子樹中，查找key為key的節點。如果當前node的key值與參數相同，更新當前節點的value。否則遞歸地到左右子樹中找到key為key的節點，并更新value。

remove:

執行remove操作時，分為兩種情況。
1.當前要刪除的節點沒有右子節點，此時將左子節點作為當前節點，返回。
2.當前要刪除的節點(node_to_delete)有右子節點(r_child)，找到右子節點下，最小的節點(r_child_smallest_child)，將該節點與要刪除的節點換位置。具體操作為：先拿到r_child_smallest_child，再將該節點從以r_child為根的子樹中刪除。再將node_to_delete的左孩子作為r_child_smallest_child的左孩子，node_to_delete的右孩子作為r_child_smallest_child的右孩子。最終將r_child_smallest_child賦給node_to_delete，并返回。

代碼如下：

    def __remove(self, node, key):
        if node:
            if node.key < key:
                node.r_child = self.__remove(node.r_child, key)
            elif node.key > key:
                node.l_child = self.__remove(node.l_child, key)
            else:
                if node.r_child is None:
                    node = node.l_child
                else:
                    node_r_child_smallest_child = self.__get_smallest_child(node.r_child)
                    self.__remove_smallest(node.r_child)
                    node_r_child_smallest_child.r_child = node.r_child
                    node_r_child_smallest_child.l_child = node.l_child
                    node = node_r_child_smallest_child
            return node

        return False

其中__remove_smallest和__get_smallest_child含義分別是：刪除當前節點下，最小的節點，以及獲得當前節點下最小的節點。
代碼如下：

    def __remove_smallest(self, node):
        if node.l_child:
            node.l_child = self.__remove_smallest(node.l_child)
            return node
        return node.r_child

當當前節點有左孩子時，刪除左子樹中最小的節點，并且返回當前節點。沒有左孩子時，返回右孩子。

    def __get_smallest_child(self, node):
        if node.l_child:
            return self.__get_smallest_child(node.l_child)
        return node

當當前節點有左孩子時，獲得左子樹中最小的節點。沒有左孩子時，返回當前節點。

深度優先遍歷，可以選擇先序遍歷，中序遍歷，后續遍歷，以其中之一為例：

    def __l_m_r(self, node):
        if node:
            self.__l_m_r(node.l_child)
            print(node)
            self.__l_m_r(node.r_child)

當進行廣度優先遍歷時，需要用到隊列。

    def bfs(self):
        queue = deque()
        queue.append(self.root)

        while queue:
            node = queue.popleft()
            if node:
                l_child = node.l_child
                r_child = node.r_child
                print(node.value)
                queue.append(l_child)
                queue.append(r_child)

以上是我所了解的二叉搜索樹的基本功能

GPU云服務器云服務器二叉樹的遍歷二叉樹的存儲二叉樹的存儲結構 java二叉樹的構建

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/44613.html

Python數據結構——二叉搜索樹的實現（上）

摘要：圖展示了二叉搜索樹的這一特性，顯示的鍵沒有關聯任何的值。因為我們必須能夠創建和使用一個空的二叉搜索樹，所以我們將使用兩個類來實現，第一個類我們稱之為，第二個類我們稱之為。圖說明了將新節點插入到一個二叉搜索樹的過程。二叉搜索樹我們已經知道了在一個集合中獲取鍵值對的兩種不同的方法。回憶一下這些集合是如何實現ADT（抽象數據類型）MAP的。我們討論兩種ADT MAP的實現方式，基于列表的...

AbnerMing 2019-07-31 11:41 評論0 收藏0
Python數據結構——二叉搜索樹的實現（下）

摘要：現在對我們來說首要的問題是從二叉搜索樹中刪除一個節點。搜索樹分析通過二叉搜索樹實現的完成，我們將對我們已經實現的方法進行一個快速的分析。對它的執行效果造成限制的是二叉樹的高度。當表示樹的高度時，一個滿二叉樹中節點的總數是。搜索樹實現（續）最后，我們把注意力轉向二叉搜索樹中最具挑戰性的方法，刪除一個鍵值（參見Listing 7）。首要任務是要找到搜索樹中要刪除的節點。如果樹有一個以上...

weapon 2019-07-24 18:27 評論0 收藏0
Python數據結構——AVL樹的基本概念

摘要：我們知道，當樹變得不平衡時和操作會使二叉搜索樹的性能降低到。樹實現抽象數據類型就像一個普通的二叉搜索樹，唯一不同的是這棵樹的工作方式。我們通過比較每個節點的左右子樹的高度完成比較。平衡二叉搜索樹在上一節中我們討論了建立一個二叉搜索樹。我們知道，當樹變得不平衡時get和put操作會使二叉搜索樹的性能降低到O(n)。在這一節中我們將看到一種特殊的二叉搜索樹，它可以自動進行調整，以確保樹...

jiekechoo 2019-07-24 18:26 評論0 收藏0
樹和樹的算法

摘要：樹和樹的算法一樹樹的概念樹英語是一種抽象數據類型或是實作這種抽象數據類型的數據結構，用來模擬具有樹狀結構性質的數據集合。一種時間復雜度額外空間復雜度的二叉樹的遍歷方式，為二叉樹的節點個數。樹和樹的算法一、樹 1.1 樹的概念樹（英語：tree）是一種抽象數據類型（ADT）或是實作這種抽象數據類型的數據結構，用來模擬具有樹狀結構性質的數據集合。它是由n（n>=1）個有限節點組成一個...

RaoMeng 2019-08-19 11:08 評論0 收藏0
樹和樹的算法

摘要：樹和樹的算法一樹樹的概念樹英語是一種抽象數據類型或是實作這種抽象數據類型的數據結構，用來模擬具有樹狀結構性質的數據集合。一種時間復雜度額外空間復雜度的二叉樹的遍歷方式，為二叉樹的節點個數。樹和樹的算法一、樹 1.1 樹的概念樹（英語：tree）是一種抽象數據類型（ADT）或是實作這種抽象數據類型的數據結構，用來模擬具有樹狀結構性質的數據集合。它是由n（n>=1）個有限節點組成一個...

PiscesYE 2019-07-30 17:45 評論0 收藏0