欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

python 實(shí)現(xiàn)二叉搜索樹的四種方法

 更新時(shí)間：2023年04月12日 09:40:43   作者：SiKi學(xué)院  
本文主要介紹了python 實(shí)現(xiàn)二叉搜索樹的四種方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

樹的介紹

樹不同于鏈表或哈希表，是一種非線性數(shù)據(jù)結(jié)構(gòu)，樹分為二叉樹、二叉搜索樹、B樹、B+樹、紅黑樹等等。

樹是一種數(shù)據(jù)結(jié)構(gòu)，它是由n個(gè)有限節(jié)點(diǎn)組成的一個(gè)具有層次關(guān)系的集合。用圖片來表示的話，可以看到它很像一棵倒掛著的樹。因此我們將這類數(shù)據(jù)結(jié)構(gòu)統(tǒng)稱為樹，樹根在上面，樹葉在下面。一般的樹具有以下特點(diǎn)：

  • 每個(gè)節(jié)點(diǎn)有0個(gè)或者多個(gè)子節(jié)點(diǎn)
  • 沒有父節(jié)點(diǎn)的節(jié)點(diǎn)被稱為根節(jié)點(diǎn)
  • 每個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)
  • 每個(gè)子結(jié)點(diǎn)都可以分為多個(gè)不相交的子樹

二叉樹的定義是：每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)。即每個(gè)節(jié)點(diǎn)只能有以下四種情況：

  • 左子樹和右子樹均為空
  • 只存在左子樹
  • 只存在右子樹
  • 左子樹和右子樹均存在

二叉搜索樹

二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質(zhì)的二叉樹:

  • 若它的左子樹不為空，則左子樹上所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值 若它的右子樹不為空，則右子樹上所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值
  • 它的左右子樹也分別為二叉搜索樹

列舉幾種Python中幾種常見的實(shí)現(xiàn)方式：

1.使用類和遞歸函數(shù)實(shí)現(xiàn)

通過定義一個(gè)節(jié)點(diǎn)類，包含節(jié)點(diǎn)值、左右子節(jié)點(diǎn)等屬性，然后通過遞歸函數(shù)實(shí)現(xiàn)插入、查找、刪除等操作。代碼示例如下：

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
?
class BST:
    def __init__(self):
        self.root = None
?
    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert(value, self.root)
?
    def _insert(self, value, node):
        if value < node.data:
            if node.left is None:
                node.left = Node(value)
            else:
                self._insert(value, node.left)
        elif value > node.data:
            if node.right is None:
                node.right = Node(value)
            else:
                self._insert(value, node.right)
?
    def search(self, value):
        if self.root is None:
            return False
        else:
            return self._search(value, self.root)
?
    def _search(self, value, node):
        if node is None:
            return False
        elif node.data == value:
            return True
        elif value < node.data:
            return self._search(value, node.left)
        else:
            return self._search(value, node.right)
?
    def delete(self, value):
        if self.root is None:
            return False
        else:
            self.root = self._delete(value, self.root)
?
    def _delete(self, value, node):
        if node is None:
            return node
        elif value < node.data:
            node.left = self._delete(value, node.left)
        elif value > node.data:
            node.right = self._delete(value, node.right)
        else:
            if node.left is None and node.right is None:
                del node
                return None
            elif node.left is None:
                temp = node.right
                del node
                return temp
            elif node.right is None:
                temp = node.left
                del node
                return temp
            else:
                temp = self._find_min(node.right)
                node.data = temp.data
                node.right = self._delete(temp.data, node.right)
        return node
?
    def _find_min(self, node):
        while node.left is not None:
            node = node.left
        return node

2.使用列表實(shí)現(xiàn)

通過使用一個(gè)列表來存儲(chǔ)二叉搜索樹的元素，然后通過列表中元素的位置關(guān)系來實(shí)現(xiàn)插入、查找、刪除等操作。代碼示例如下：

class BST:
    def __init__(self):
        self.values = []
?
    def insert(self, value):
        if len(self.values) == 0:
            self.values.append(value)
        else:
            self._insert(value, 0)
?
    def _insert(self, value, index):
        if value < self.values[index]:
            left_child_index = 2 * index + 1
            if left_child_index >= len(self.values):
                self.values.extend([None] * (left_child_index - len(self.values) + 1))
            if self.values[left_child_index] is None:
                self.values[left_child_index] = value
            else:
                self._insert(value, left_child_index)
        else:
            right_child_index = 2 * index + 2
            if right_child_index >= len(self.values):
                self.values.extend([None] * (right_child_index - len(self.values) + 1))
            if self.values[right_child_index] is None:
                self.values[right_child_index] = value
            else:
                self._insert(value, right_child_index)
?
    def search(self, value):
        if value in self.values:
            return True
        else:
            return False
?
    def delete(self, value):
        if value not in self.values:
            return False
        else:
            index = self.values.index(value)
            self._delete(index)
            return True
?
    def _delete(self, index):
        left_child_index = 2 * index + 1
        right_child_index = 2 * index + 2
        if left_child_index < len(self.values) and self.values[left_child_index] is not None:
            self._delete(left_child_index)
        if right_child_index < len(self.values) and self.values[right_child_index] is not None:
            self

3.使用字典實(shí)現(xiàn)

其中字典的鍵表示節(jié)點(diǎn)值，字典的值是一個(gè)包含左右子節(jié)點(diǎn)的字典。代碼示例如下：

def insert(tree, value):
    if not tree:
        return {value: {}}
    elif value < list(tree.keys())[0]:
        tree[list(tree.keys())[0]] = insert(tree[list(tree.keys())[0]], value)
    else:
        tree[list(tree.keys())[0]][value] = {}
    return tree
?
def search(tree, value):
    if not tree:
        return False
    elif list(tree.keys())[0] == value:
        return True
    elif value < list(tree.keys())[0]:
        return search(tree[list(tree.keys())[0]], value)
    else:
        return search(tree[list(tree.keys())[0]].get(value), value)
?
def delete(tree, value):
    if not search(tree, value):
        return False
    else:
        if list(tree.keys())[0] == value:
            if not tree[list(tree.keys())[0]]:
                del tree[list(tree.keys())[0]]
            elif len(tree[list(tree.keys())[0]]) == 1:
                tree[list(tree.keys())[0]] = list(tree[list(tree.keys())[0]].values())[0]
            else:
                min_key = min(list(tree[list(tree.keys())[0]+1].keys()))
                tree[min_key] = tree[list(tree.keys())[0]+1][min_key]
                tree[min_key][list(tree.keys())[0]] = tree[list(tree.keys())[0]]
                del tree[list(tree.keys())[0]]
        elif value < list(tree.keys())[0]:
            tree[list(tree.keys())[0]] = delete(tree[list(tree.keys())[0]], value)
        else:
            tree[list(tree.keys())[0]][value] = delete(tree[list(tree.keys())[0]].get(value), value)
    return tree

由于字典是無(wú)序的，因此該實(shí)現(xiàn)方式可能會(huì)導(dǎo)致二叉搜索樹不平衡，影響插入、查找和刪除操作的效率。

4.使用堆棧實(shí)現(xiàn)

使用堆棧（Stack）可以實(shí)現(xiàn)一種簡(jiǎn)單的二叉搜索樹，可以通過迭代方式實(shí)現(xiàn)插入、查找、刪除等操作。具體實(shí)現(xiàn)過程如下：

  • 定義一個(gè)節(jié)點(diǎn)類，包含節(jié)點(diǎn)值、左右子節(jié)點(diǎn)等屬性。
  • 定義一個(gè)堆棧，初始時(shí)將根節(jié)點(diǎn)入棧。
  • 當(dāng)棧不為空時(shí)，取出棧頂元素，并對(duì)其進(jìn)行操作：如果要插入的值小于當(dāng)前節(jié)點(diǎn)值，則將要插入的值作為左子節(jié)點(diǎn)插入，并將左子節(jié)點(diǎn)入棧；如果要插入的值大于當(dāng)前節(jié)點(diǎn)值，則將要插入的值作為右子節(jié)點(diǎn)插入，并將右子節(jié)點(diǎn)入棧；如果要查找或刪除的值等于當(dāng)前節(jié)點(diǎn)值，則返回或刪除該節(jié)點(diǎn)。
  • 操作完成后，繼續(xù)從堆棧中取出下一個(gè)節(jié)點(diǎn)進(jìn)行操作，直到堆棧為空。

需要注意的是，在這種實(shí)現(xiàn)方式中，由于使用了堆棧來存儲(chǔ)遍歷樹的過程，因此可能會(huì)導(dǎo)致內(nèi)存占用較高。另外，由于堆棧的特性，這種實(shí)現(xiàn)方式只能支持深度優(yōu)先遍歷（Depth-First Search，DFS），不能支持廣度優(yōu)先遍歷（Breadth-First Search，BFS）。

以下是偽代碼示例：

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
?
def insert(root, value):
    if not root:
        return Node(value)
    stack = [root]
    while stack:
        node = stack.pop()
        if value < node.data:
            if node.left is None:
                node.left = Node(value)
                break
            else:
                stack.append(node.left)
        elif value > node.data:
            if node.right is None:
                node.right = Node(value)
                break
            else:
                stack.append(node.right)
?
def search(root, value):
    stack = [root]
    while stack:
        node = stack.pop()
        if node.data == value:
            return True
        elif value < node.data and node.left:
            stack.append(node.left)
        elif value > node.data and node.right:
            stack.append(node.right)
    return False
?
def delete(root, value):
    if root is None:
        return None
    if value < root.data:
        root.left = delete(root.left, value)
    elif value > root.data:
        root.right = delete(root.right, value)
    else:
        if root.left is None:
            temp = root.right
            del root
            return temp
        elif root.right is None:
            temp = root.left
            del root
            return temp
        else:
            temp = root.right
            while temp.left is not None:
                temp = temp.left
            root.data = temp.data
            root.right = delete(root.right, temp.data)
    return root

以上是四種在Python中實(shí)現(xiàn)二叉搜索樹的方法，在具體使用過程中還是需要合理選擇，盡量以運(yùn)行速度快、內(nèi)存占用少為出發(fā)點(diǎn)，更多相關(guān)python 二叉搜索樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

  • django使用多個(gè)數(shù)據(jù)庫(kù)的方法實(shí)例

    django使用多個(gè)數(shù)據(jù)庫(kù)的方法實(shí)例

    這篇文章主要給大家介紹了關(guān)于django使用多個(gè)數(shù)據(jù)庫(kù)的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2021-03-03
  • python sys，os，time模塊的使用（包括時(shí)間格式的各種轉(zhuǎn)換）

    python sys，os，time模塊的使用（包括時(shí)間格式的各種轉(zhuǎn)換）

    這篇文章主要介紹了python sys，os，time模塊的使用（包括時(shí)間格式的各種轉(zhuǎn)換），小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧
    2018-04-04
  • Anaconda環(huán)境克隆、遷移的詳細(xì)步驟

    Anaconda環(huán)境克隆、遷移的詳細(xì)步驟

    最近需要在多臺(tái)計(jì)算機(jī)上工作,每次重新部署環(huán)境比較麻煩,所以學(xué)習(xí)一下anaconda環(huán)境遷移的方法,下面這篇文章主要給大家介紹了關(guān)于Anaconda環(huán)境克隆、遷移的詳細(xì)步驟,需要的朋友可以參考下
    2022-08-08
  • pytorch自定義loss損失函數(shù)

    pytorch自定義loss損失函數(shù)

    這篇文章主要介紹了pytorch自定義loss損失函數(shù)，自定義loss的方法有很多，本文要介紹的是把loss作為一個(gè)pytorch的模塊，下面詳細(xì)資料需要的小伙伴可以參考一下
    2022-02-02
  • Django 5種類型Session使用方法解析

    Django 5種類型Session使用方法解析

    這篇文章主要介紹了Django 5種類型Session使用方法解析,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-04-04
  • PyQt 圖解Qt Designer工具的使用方法

    PyQt 圖解Qt Designer工具的使用方法

    這篇文章主要介紹了PyQt 圖解Qt Designer工具的使用方法,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2019-08-08

    • 最新評(píng)論