歡迎光臨
每天分享高質量文章

4 張 GIF 圖幫助你理解二叉搜索樹

二叉搜索樹(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

已同步到看一看
赞(0)

分享創造快樂