二叉查找树BST

Posted by Faushine on September 8, 2018

BST全称是binary search tree,二叉查找树的左子树比根节点小,右子树比根节点大,而且没有键值相等的节点。这种数据结构在查找、插入等操作的时间复杂度较低,为O(logn)。 中序遍历二叉查找树可以得到一个有序序列,通过一个无序序列构造二叉查找树的过程可以看成对无序序列进行查找的过程,每次插入的节点都是二叉查找树上新的叶子节点。下文所提及的代码实现皆为python。

定义

class TreeNode(object):
    def__init__(self, x):
        self.val = x
        self.left = None
self.right = None

插入节点

具体做法类似于深度优先,从根节点开始逐步向下深入,比根节点小的元素放左边,比根节点大的元素放右边,直到左子树为空或右子树为空。必须说明的是BST的形状由根节点决定,也就是说因为根节点不一样,即便含有同样元素的情况下BST也可以不一样。 插入算法可以描述为:

  • 如果树为空,将该节点当成跟节点。
  • 如果插入节点的值大于跟节点值,分为两种情况:1 如果根节点的右子树为空,将节点赋给右子树;2 否则将根节点的右子树作为根节点,递归执行插入算法。
  • 如果插入节点的值小于根节点值,分为两种情况:1 如果根节点的左子树为空,将节点赋给左子树;2 否则将根节点的左子树作为根节点,递归执行插入算法。
    def insert(tree, node):
      if tree is None:
          tree = TreeNode(node.val)
      if node.val > tree.val:
          if tree.right is None:
              tree.right = TreeNode(node.val)
          else:
              insert(tree.right, node)
      else:
          if tree.left is None:
              tree.left = TreeNode(node.val)
          else:
              insert(tree.left, node)
    

遍历节点

从最底层不为空的节点开始遍历,按照左节点->父节点->右节点的顺序依次输出。

def inorder(root):
    if root:
        inorder(root.left)
        print(root.val)
        inorder(root.right)

### 查找第k个节点 ###

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Example 1: alt text

Example 2: alt text

def getKthElement(root,k):
    stack = []
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        k = k-1
        if k == 0:
            return root.val
        root = root.right