4 张 GIF 图帮助你理解二叉搜索树
来源:Python那些事
二叉搜索树(Binary Search Tree),也称二叉查找树,是指一棵空树或者具有下列性质的二叉树:
-
若某节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
-
若 某 节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
-
任意节点的左、右子树也分别为二叉 搜索 树;
二叉 搜索 树相比于其他数据结构的优势在于查找、插入的时间复杂度较低, 为O(log n)。
二叉搜索树的节点数据结构如下:
class TreeNode: ''' 二叉搜索树节点构造 ''' def __init__(self, val): self.val = val self.left = None self.right = None
下面 4 张 GIF 动图,是 penjee 官博制作分享, 分享给大家。
图1: 查找 BST 中的某个元素
在二叉搜索树root中查找val的过程为:
-
若root是空树,则返回失败,否则:
-
若val等于root -> val,则查找成功; 否则:
-
若val小于 root -> val ,则递归搜索左子树; 否则:
-
递归 搜索右子树。
Python代码实现如下:
def query(self, root, val): ''' 查询操作 :param root: 叉搜索树根节点 :param val: 要查找元素 :return: ''' if root == None: return False if root.val == val: return True elif val root.val: return self.query(root.right, val)
图2 ↓ : 从有序数组构造一个二叉搜索树
由顺序数组构造二叉搜索树的过程为:
如果数组不为空:
-
寻找数组中的中间元素,即为根节点;
-
由根节点递归构造左子树;
-
由 根节点递归构造右子树。
Python代码实现如下:
def sortedArrayToBST(self, list): ''' :param list: 排序好的数组,顺序是由小到大 :return: root ''' if not list: return None else: length = len(list) mid = length // 2 root = TreeNode(list[mid]) root.left = self.sortedArrayToBST(list[:mid]) root.right = self.sortedArrayToBST(list[mid + 1:]) return root
图3 ↓: 往 BST 中插入元素
向一个二叉搜索树root中插入一个值val的算法(val值不存在在root中),过程为:
-
若root是空树,则将val所形成的节点作为根节点插入,否则:
-
若root->val小于val, 则递归把 val 所 形成的 节 点 插入到左子树中,否则:
-
递归 把 val 所 形成的 节 点 插入到右子树中。
Python代码实现如下:
def insert(self, root, val): ''' 查找操作 :param root: 二叉搜索树根节点 :param val: 要插入的元素 :return: ''' if root == None: root = TreeNode(val) elif val root.val: root.right = self.insert(root.right, val) return root
图4 ↓: BST 转成有序数组
由 二叉搜索树还原 顺序数组的过程为:
如果树节点不为空:
-
递归遍历左子树的节点,将相关的val保存在list中;
-
将根节点的val保存在list中;
-
递归遍历右子树的节点,将相关的val保存在list中 。
Python代码实现如下:
def BSTtosortedArray(self, root, list): ''' BST 转成有序数组 :param root: 二叉搜索树根节点 :param list: 转换后的有序数组 :return: ''' # 打印二叉搜索树(中序打印,有序数列) if root == None: return else: self.BSTtosortedArray(root.left,list) list.append(root.val) self.BSTtosortedArray(root.right,list) return list
图片来源: www.penjee.com
往期阅读