Binary Search Tree#

Binary Tree (二叉树)#

二叉树是一种特殊的树形结构，它的每个节点最多只能有两个子节点。二叉树的子节点分为左子节点和右子节点.

Binary Search Tree (二叉搜索树)#

二叉搜索树是一种特殊的二叉树，它的每个节点都满足以下条件：

  • 左子节点的值小于父节点的值

  • 右子节点的值大于父节点的值

满二叉树（Full Binary Tree），也称为真二叉树或者严格二叉树，是一种特殊的二叉树，其中每个非叶子节点都恰好有两个子节点，并且所有叶子节点都在相同的深度上。

../_images/full-binary-tree.PNG ../_images/full-perfect.PNG

https://en.wikipedia.org/wiki/Binary_search_tree

二叉搜索树（Binary Search Tree）是一种二叉树，其中每个节点最多有两个子节点。 对于任何一个节点，其左子树中的节点的值都小于该节点的值，右子树中的节点的值都大于该节点的值。 通过这种结构，可以快速地进行搜索、插入和删除等操作。

Binary Search Tree Python实现#

  1class Node:
  2    def __init__(self, value) -> None:
  3        self.value = value
  4        self.left = None
  5        self.right = None
  6
  7    def __str__(self):
  8        return str(self.value)
  9
 10
 11class BinarySearchTree:
 12    def __init__(self) -> None:
 13        self.root = None
 14
 15    def insert(self, value):
 16
 17        new_node = Node(value)
 18        if self.root is None:
 19            self.root = new_node
 20            return True
 21
 22        tmp_root = self.root
 23
 24        while True:
 25
 26            if new_node.value == tmp_root.value:
 27                return False
 28
 29            elif new_node.value < tmp_root.value:
 30
 31                if tmp_root.left is None:
 32                    tmp_root.left = new_node
 33                    return True
 34                tmp_root = tmp_root.left
 35            else:
 36                if tmp_root.right is None:
 37                    tmp_root.right = new_node
 38                    return True
 39                else:
 40                    tmp_root = tmp_root.right
 41
 42    def search(self, value):
 43
 44        tmp = self.root
 45
 46        while tmp is not None:
 47
 48            if value < tmp.value:
 49                tmp = tmp.left
 50            elif value > tmp.value:
 51                tmp = tmp.right
 52
 53            else:
 54                return True
 55        return False
 56
 57    def _r_search(self, current_root, value):
 58
 59        if current_root == None:
 60            return False
 61        if value == current_root.value:
 62            return True
 63
 64        if value < current_root.value:
 65            return self._r_search(current_root=current_root.left, value=value)
 66        if value > current_root.value:
 67            return self._r_search(current_root=current_root.right, value=value)
 68
 69    def r_search(self, value):
 70
 71        return self._r_search(self.root, value)
 72
 73    def _r_insert(self, current_root, value):
 74        if current_root == None:
 75            return Node(value)
 76
 77        if value < current_root.value:
 78            current_root.left = self._r_insert(
 79                current_root=current_root.left, value=value
 80            )
 81        if value > current_root.value:
 82            current_root.right = self._r_insert(
 83                current_root=current_root.right, value=value
 84            )
 85        if value == current_root.value:
 86            return current_root
 87
 88    def r_insert(self, value):
 89
 90        if self.root is None:
 91            self.root = Node(value)
 92
 93        self._r_insert(self.root, value)
 94
 95
 96if __name__ == "__main__":
 97
 98    bst = BinarySearchTree()
 99
100    for i in [8, 3, 10, 1]:
101        bst.r_insert(i)
102
103    print(bst.root)
104    print(bst.root.left)
105    print(bst.root.right)