![](/style/images/good.png)
![](/style/images/bad.png)
4 张 GIF 图帮助你理解二叉搜索树
source link: https://www.tuicool.com/articles/VBbE7b6
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
来源: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.left, val) 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.left = self.insert(root.left, 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
往期阅读
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK