打印二叉搜索树的叶子结点_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的过程为：

1. 若root是空树，则返回失败，否则：

2. 若val等于root->val，则查找成功；否则：

3. 若val小于root->val，则递归搜索左子树；否则：

4. 递归搜索右子树。

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 ↓ ：从有序数组构造一个二叉搜索树

由顺序数组构造二叉搜索树的过程为：

如果数组不为空：

1. 寻找数组中的中间元素，即为根节点；

2. 由根节点递归构造左子树；

3. 由根节点递归构造右子树。

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中)，过程为：

1. 若root是空树，则将val所形成的节点作为根节点插入，否则：

2. 若root->val小于val，则递归把val所形成的节点插入到左子树中，否则：

3. 递归把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 转成有序数组

由二叉搜索树还原顺序数组的过程为：

如果树节点不为空：

1. 递归遍历左子树的节点，将相关的val保存在list中；

2. 将根节点的val保存在list中；

3. 递归遍历右子树的节点，将相关的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

(完)

看完本文有收获？请转发分享给更多人

关注「Python那些事」，做全栈开发工程师