国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

二叉搜索樹的python實現(xiàn)

shixinzhang / 2265人閱讀

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

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

再定義一個BSTree類,根節(jié)點初始化為None。

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

insert:
傳入?yún)?shù)key,value,插入一個新的節(jié)點。但是如果樹中已經(jīng)存在key為key的節(jié)點,就將插入操作轉(zhuǎn)變?yōu)楦虏僮鳌?/p>

 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

當(dāng)當(dāng)前的節(jié)點為None時,根據(jù)參數(shù)中的key和value建立新的節(jié)點,并返回這個節(jié)點。當(dāng)key值小于當(dāng)前節(jié)點的key時,將新節(jié)點插入到當(dāng)前節(jié)點的左子樹的相應(yīng)位置,然后返回當(dāng)前節(jié)點。同理key值大于當(dāng)前節(jié)點的key時,將新節(jié)點插入到當(dāng)前節(jié)點的右子樹的相應(yīng)位置,返回當(dāng)前節(jié)點。如果key等于當(dāng)前節(jié)點key,將插入操作改變?yōu)楦虏僮鳌?/p>

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

在當(dāng)前node為根節(jié)點的子樹中,查找key為key的子節(jié)點,如果當(dāng)前node的key值與參數(shù)相同,返回當(dāng)前節(jié)點。否則遞歸地到左右子樹中找key為key的節(jié)點,如果沒有找到,最終返回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)

在當(dāng)前node為根節(jié)點的子樹中,查找key為key的節(jié)點。如果當(dāng)前node的key值與參數(shù)相同,更新當(dāng)前節(jié)點的value。否則遞歸地到左右子樹中找到key為key的節(jié)點,并更新value。

remove:

執(zhí)行remove操作時,分為兩種情況。
1.當(dāng)前要刪除的節(jié)點沒有右子節(jié)點,此時將左子節(jié)點作為當(dāng)前節(jié)點,返回。
2.當(dāng)前要刪除的節(jié)點(node_to_delete)有右子節(jié)點(r_child),找到右子節(jié)點下,最小的節(jié)點(r_child_smallest_child),將該節(jié)點與要刪除的節(jié)點換位置。具體操作為:先拿到r_child_smallest_child,再將該節(jié)點從以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含義分別是:刪除當(dāng)前節(jié)點下,最小的節(jié)點,以及獲得當(dāng)前節(jié)點下最小的節(jié)點。
代碼如下:

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

當(dāng)當(dāng)前節(jié)點有左孩子時,刪除左子樹中最小的節(jié)點,并且返回當(dāng)前節(jié)點。沒有左孩子時,返回右孩子。

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

當(dāng)當(dāng)前節(jié)點有左孩子時,獲得左子樹中最小的節(jié)點。沒有左孩子時,返回當(dāng)前節(jié)點。

深度優(yōu)先遍歷,可以選擇先序遍歷,中序遍歷,后續(xù)遍歷,以其中之一為例:

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

當(dāng)進(jìn)行廣度優(yōu)先遍歷時,需要用到隊列。

    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)

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

文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/44613.html

相關(guān)文章

  • Python數(shù)據(jù)結(jié)構(gòu)——二叉搜索樹的實現(xiàn)(上)

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

    AbnerMing 評論0 收藏0
  • Python數(shù)據(jù)結(jié)構(gòu)——二叉搜索樹的實現(xiàn)(下)

    摘要:現(xiàn)在對我們來說首要的問題是從二叉搜索樹中刪除一個節(jié)點。搜索樹分析通過二叉搜索樹實現(xiàn)的完成,我們將對我們已經(jīng)實現(xiàn)的方法進(jìn)行一個快速的分析。對它的執(zhí)行效果造成限制的是二叉樹的高度。當(dāng)表示樹的高度時,一個滿二叉樹中節(jié)點的總數(shù)是。 搜索樹實現(xiàn)(續(xù)) 最后,我們把注意力轉(zhuǎn)向二叉搜索樹中最具挑戰(zhàn)性的方法,刪除一個鍵值(參見Listing 7)。首要任務(wù)是要找到搜索樹中要刪除的節(jié)點。如果樹有一個以上...

    weapon 評論0 收藏0
  • Python數(shù)據(jù)結(jié)構(gòu)——AVL樹的基本概念

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

    jiekechoo 評論0 收藏0
  • 樹和樹的算法

    摘要:樹和樹的算法一樹樹的概念樹英語是一種抽象數(shù)據(jù)類型或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu),用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。一種時間復(fù)雜度額外空間復(fù)雜度的二叉樹的遍歷方式,為二叉樹的節(jié)點個數(shù)。 樹和樹的算法 一、樹 1.1 樹的概念 樹(英語:tree)是一種抽象數(shù)據(jù)類型(ADT)或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu),用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n(n>=1)個有限節(jié)點組成一個...

    RaoMeng 評論0 收藏0
  • 樹和樹的算法

    摘要:樹和樹的算法一樹樹的概念樹英語是一種抽象數(shù)據(jù)類型或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu),用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。一種時間復(fù)雜度額外空間復(fù)雜度的二叉樹的遍歷方式,為二叉樹的節(jié)點個數(shù)。 樹和樹的算法 一、樹 1.1 樹的概念 樹(英語:tree)是一種抽象數(shù)據(jù)類型(ADT)或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu),用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n(n>=1)個有限節(jié)點組成一個...

    PiscesYE 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<