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

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

再定義一個(gè)BSTree類，根節(jié)點(diǎn)初始化為None。

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

insert:
傳入?yún)?shù)key,value，插入一個(gè)新的節(jié)點(diǎn)。但是如果樹中已經(jīng)存在key為key的節(jié)點(diǎn)，就將插入操作轉(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é)點(diǎn)為None時(shí)，根據(jù)參數(shù)中的key和value建立新的節(jié)點(diǎn)，并返回這個(gè)節(jié)點(diǎn)。當(dāng)key值小于當(dāng)前節(jié)點(diǎn)的key時(shí)，將新節(jié)點(diǎn)插入到當(dāng)前節(jié)點(diǎn)的左子樹的相應(yīng)位置，然后返回當(dāng)前節(jié)點(diǎn)。同理key值大于當(dāng)前節(jié)點(diǎn)的key時(shí)，將新節(jié)點(diǎn)插入到當(dāng)前節(jié)點(diǎn)的右子樹的相應(yīng)位置，返回當(dāng)前節(jié)點(diǎn)。如果key等于當(dāng)前節(jié)點(diǎn)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é)點(diǎn)的子樹中，查找key為key的子節(jié)點(diǎn)，如果當(dāng)前node的key值與參數(shù)相同，返回當(dāng)前節(jié)點(diǎn)。否則遞歸地到左右子樹中找key為key的節(jié)點(diǎn)，如果沒有找到，最終返回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é)點(diǎn)的子樹中，查找key為key的節(jié)點(diǎn)。如果當(dāng)前node的key值與參數(shù)相同，更新當(dāng)前節(jié)點(diǎn)的value。否則遞歸地到左右子樹中找到key為key的節(jié)點(diǎn)，并更新value。

remove:

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

    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é)點(diǎn)有左孩子時(shí)，刪除左子樹中最小的節(jié)點(diǎn)，并且返回當(dāng)前節(jié)點(diǎn)。沒有左孩子時(shí)，返回右孩子。

    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é)點(diǎn)有左孩子時(shí)，獲得左子樹中最小的節(jié)點(diǎn)。沒有左孩子時(shí)，返回當(dāng)前節(jié)點(diǎn)。

深度優(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)先遍歷時(shí)，需要用到隊(duì)列。

    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)

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