数据结构与算法树（B树，B+树，红黑树待完善）-阿里云开发者社区

二叉树的介绍

二叉树的节点代码

class TreeNode:
    def __init__(self, value) -> None:
        self.val = value
        self.left = None
        self.right = None

节点的「深度 depth」：从根节点到该节点所经过的边的数量。
节点的「高度 height」：从最远叶节点到该节点所经过的边的数量。

二叉树的类型

「完美二叉树 perfect binary tree」除了最底层外，其余所有层的节点都被完全填满。在完美二叉树中，叶节点的度为 0 ，其余所有节点的度都为 2 ；若树高度为 ℎ ，则节点总数为 2ⁿ⁺¹−1 ，呈现标准的指数级关系，反映了自然界中常见的细胞分裂现象。
「完全二叉树 complete binary tree」只有最底层的节点未被填满，且最底层节点尽量靠左填充。
「完满二叉树 full binary tree」除了叶节点之外，其余所有节点都有两个子节点。
「平衡二叉树 balanced binary tree」中任意节点的左子树和右子树的高度之差的绝对值不超过 1 。

链表二叉树的遍历

层序遍历(广度优先遍历breadth‑first traversal) BFT/BFS

从顶部到底部逐层遍历二叉树，并在每一层按照从左到右的顺序访问节点。

from collections import deque
def level_order(root):
    queue = deque()
    queue.append(root)
  
    res = []
    while queue:
        node = queue.popleft()
        res.append(node.val)
        if node.left is not None:
            queue.append(node.left)
        if node.right is not None:
            queue.append(node.right)
    return res

前序、中序、后序遍历（深度优先遍历）DFT/DFS

前序:访问优先级：根节点 -> 左子树 -> 右子树
中序:访问优先级：左子树 -> 根节点 -> 右子树
后序:访问优先级：左子树 -> 右子树 -> 根节点

class TreeOrder:
    def __init__(self) -> None:
        self.res = []
  
    def pre_order_need(self, root):
        if root is None:
            return None
        self.res.append(root.val)
        self.pre_order_need(root.left)
        self.pre_order_need(root.right)
  
    def pre_order(self, root):
        self.res = []
        self.pre_order_need(root)
  
    def in_order_need(self, root):
        if root is None:
            return None
        self.in_order_need(root.left)
        self.res.append(root.val)
        self.in_order_need(root.right)
  
    def in_order(self, root):
        self.res = []
        self.in_order_need(root)
  
    def post_order_need(self, root):
        if root is None:
            return None
        self.post_order_need(root.left)
        self.post_order_need(root.right)
        self.res.append(root.val)
  
    def post_order(self, root):
        self.res = []
        self.post_order_need(root)

复杂度分析

时间复杂度 𝑂(𝑛) ：所有节点被访问一次，使用 𝑂(𝑛) 时间。
空间复杂度 𝑂(𝑛) ：在最差情况下，即树退化为链表时，递归深度达到 𝑛 ，系统占用 𝑂(𝑛) 栈帧空间。

数组二叉树的构造

class ArrayTree:
    def __init__(self, arr) -> None:
        self.__tree = list(arr)
        self.res = []
  
    def size(self):
        return len(self.__tree)
    def val(self, ix):
        if ix < 0 or ix >= self.size():
            return None
        else:
            return self.__tree[ix]
    def left(self, ix):
        return 2*ix + 1
  
    def right(self, ix):
        return 2*ix + 2
    def parent(self, ix):
        return (ix -1)//2
    def level_order(self):
        self.res = []
        for i in range(self.size()):
            if self.val(i) is not None:
                self.res.append(self.val(i))
        return self.res
    def __dfs(self, ix, order):
        if self.val(ix) is None:
            return None
        if order == 'pre':
            self.res.append(self.val(ix))
        self.__dfs(self.left(ix), order)
        if order == 'in':
            self.res.append(self.val(ix))
        self.__dfs(self.right(ix), order)
        if order == 'post':
            self.res.append(self.val(ix))
  
    def pre_order(self):
        self.res = []
        self.__dfs(0, order='pre')
        return self.res
    def in_order(self):
        self.res = []
        self.__dfs(0, order='in')
        return self.res
    def post_order(self):
        self.res = []
        self.__dfs(0, order='post')
        return self.res
lst = [1,2,3,4,None,6,7,8,9,None,None,12,None,None,15]
tree = ArrayTree(lst)
tree.level_order()
tree.pre_order()
tree.in_order()
tree.post_order()

数组二叉树的优缺点

二叉树的数组表示主要有以下优点。

数组存储在连续的内存空间中，对缓存友好，访问与遍历速度较快。
不需要存储指针，比较节省空间。
允许随机访问节点。
然而，数组表示也存在一些局限性。
数组存储需要连续内存空间，因此不适合存储数据量过大的树。
增删节点需要通过数组插入与删除操作实现，效率较低。
当二叉树中存在大量 None 时，数组中包含的节点数据比重较低，空间利用率较低。

二叉搜索树

「二叉搜索树 binary search tree」满足以下条件：

对于根节点，左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值。
任意节点的左、右子树也是二叉搜索树，即同样满足条件 1. 。

二叉搜索树的构造

二叉搜索树的中序遍历序列是升序的。在二叉搜索树中获取有序数据仅需 𝑂(𝑛)时间

class binary_search_tree:
    def __init__(self, root) -> None:
        self.__root = root
        self.res = []
    def search(self, num):
        cur = self.__root
        while cur is not None:
            if cur.val == num:
                return cur
            elif cur.val < num:
                cur = cur.right
            elif cur.val > num:
                cur = cur.left
        else:
            return None
    def insert(self, num):
        node = TreeNode(num)
        if self.__root is None:
            self.__root = node
        pre = None
        cur = self.__root
        while cur is not None:
            if cur.val == num:
                return ValueError('值重复')
            elif cur.val < num:
                pre = cur
                cur = cur.right
            elif cur.val > num:
                pre = cur
                cur = cur.left
        if pre.val < num:
            pre.right = node
        else:
            pre.left = node
  
    def remove(self, num):
        cur = self.__root
        pre = None
        while cur is not None:
            if cur.val == num:
                break
            elif cur.val < num:
                pre = cur
                cur = cur.right
            elif cur.val > num:
                pre = cur
                cur = cur.left
        else:
            raise ValueError('没有这个值')
        if cur.left is None or cur.right is None:
            child = cur.left or cur.right
            if pre is None:
                self.__root = None
            if pre.left == cur:
                pre.left = child
            elif pre.right == cur:
                pre.right = child
        else:
            tem = cur.left
            while tem.right is not None:
                tem = tem.right
            self.remove(tem.val)
            cur.val = tem.val
  
  
  
    def __dfs(self, node, order):
        if node is None:
            return None
        if order == 'pre':
            self.res.append(node.val)
        self.__dfs(node.left, order)
        if order == 'in':
            self.res.append(node.val)
        self.__dfs(node.right, order)
        if order == 'post':
            self.res.append(node.val)
  
    def pre_order(self):
        self.res = []
        self.__dfs(self.__root, 'pre')
        return self.res
    def in_order(self):
        self.res = []
        self.__dfs(self.__root, 'in')
        return self.res
    def post_order(self):
        self.res = []
        self.__dfs(self.__root, 'post')
        return self.res
node_1 = TreeNode(8)
node_2 = TreeNode(4)
node_3 = TreeNode(12)
node_4 = TreeNode(3)
node_5 = TreeNode(6)
node_6 = TreeNode(10)
node_7 = TreeNode(14)
  
node_1.left = node_2
node_1.right = node_3
node_2.left = node_4
node_2.right = node_5
node_3.left = node_6
node_3.right = node_7

二叉搜索树的效率

给定一组数据，我们考虑使用数组或二叉搜索树存储。观察表 7‑2 ，二叉搜索树的各项操作的时间复杂度都是对数阶，具有稳定且高效的性能表现。只有在高频添加、低频查找删除的数据适用场景下，数组比二叉搜索树的效率更高。在理想情况下，二叉搜索树是“平衡”的，这样就可以在 log 𝑛 轮循环内查找任意节点。然而，如果我们在二叉搜索树中不断地插入和删除节点，可能导致二叉树退化为图 7‑23 所示的链表，这时各种操作的时间复杂度也会退化为 𝑂(𝑛) 。

AVL树

class AVL:
    def __init__(self, root) -> None:
        self.root = root
        self.res = []
  
  
    def height(self, node):
        if node is not None:
            return node.height
        else:
            return -1
    def __update_height(self, node):
        node.height = max(node.left.height, node.right.height) + 1
  
    def balance_factor(self, node):
        if node is None:
            return 0
        else:
            return self.height(node.left) - self.height(node.right)
    def __right_rotate(self, node):
        child = node.left
        grand_child = child.right
  
        child.right = node
        node.left = grand_child
  
        self.__update_height(node)
        self.__update_height(child)
        return child
    def __left_rotate(self, node):
        child = node.right
        grand_child = child.left
  
        child.left = node
        node.right = grand_child
  
        self.__update_height(node)
        self.__update_height(child)
        return child
    def __rotate(self, node):
        balance_factor = self.balance_factor(node)
        if balance_factor > 1:
            if self.balance_factor(node.left) >= 0:
                return self.__right_rotate(node)
            else:
                node.left = self.__left_rotate(node.left)
                return self.__right_rotate(node)
        elif balance_factor < -1:
            if self.balance_factor(node.right) <= 0:
                return self.__left_rotate(node)
            else:
                node.right = self.__right_rotate(node.right)
                return self.__left_rotate(node)
        return node
    def __insert_helper(self, node, val):
        if node is None:
            return TreeNode(val)
        if val < node.val:
            node.left = self.__insert_helper(node.left, val)
        elif val > node.val:
            node.right = self.__insert_helper(node.right, val)
        else:
            return node
        self.__update_height(node)
        return self.__rotate(node)
    def insert(self, val):
        self.root = self.__insert_helper(self.root, val)
  
    def __remove_helper(self, node, val):
        if node is None:
            return None
        if val < node.val:
            node.left = self.__remove_helper(node.left, val)
        elif val > node.val:
            node.right = self.__remove_helper(node.right, val)
        else:
            if node.left is None or node.right is None:
                child = node.left or node.right
                if child is None:
                    return None
                else:
                    node = child
            else:
                temp = node.left
                while temp.right:
                    temp = temp.right
                node.left = self.__remove_helper(node.left, temp.val)
                node.val = temp.val
        self.__update_height(node)
        return self.__rotate(node)
    def remove(self, val):
        self.root = self.__remove_helper(self.root, val)
  
    def __dfs(self, node, order):
        if node is None:
            return None
        if order == 'pre':
            self.res.append(node.val)
        self.__dfs(node.left, order)
        if order == 'in':
            self.res.append(node.val)
        self.__dfs(node.right, order)
        if order == 'post':
            self.res.append(node.val)
  
    def pre_order(self):
        self.res = []
        self.__dfs(self.root, 'pre')
        return self.res
    def in_order(self):
        self.res = []
        self.__dfs(self.root, 'in')
        return self.res
    def post_order(self):
        self.res = []
        self.__dfs(self.root, 'post')
        return self.res
    def search(self, value):
        cur = self.root
        while cur:
            if cur.val == value:
                break
            elif cur.val < value:
                cur = cur.right
            elif cur.val > value:
                cur = cur.left
        else:
            raise ValueError('这个值不存在')
        return cur

重点回顾

二叉树是一种非线性数据结构，体现“一分为二”的分治逻辑。每个二叉树节点包含一个值以及两个指针，分别指向其左子节点和右子节点。
对于二叉树中的某个节点，其左（右）子节点及其以下形成的树被称为该节点的左（右）子树。
二叉树的相关术语包括根节点、叶节点、层、度、边、高度和深度等。
二叉树的初始化、节点插入和节点删除操作与链表操作方法类似。
常见的二叉树类型有完美二叉树、完全二叉树、满二叉树和平衡二叉树。完美二叉树是最理想的状态，而链表是退化后的最差状态。
二叉树可以用数组表示，方法是将节点值和空位按层序遍历顺序排列，并根据父节点与子节点之间的索引映射关系来实现指针。
二叉树的层序遍历是一种广度优先搜索方法，它体现了“一圈一圈向外”的分层遍历方式，通常通过队列来实现。
前序、中序、后序遍历皆属于深度优先搜索，它们体现了“走到尽头，再回头继续”的回溯遍历方式，通常使用递归来实现。
二叉搜索树是一种高效的元素查找数据结构，其查找、插入和删除操作的时间复杂度均为 𝑂(log 𝑛) 。
当二叉搜索树退化为链表时，各项时间复杂度会劣化至 𝑂(𝑛) 。
AVL 树，也称为平衡二叉搜索树，它通过旋转操作，确保在不断插入和删除节点后，树仍然保持平衡。
AVL 树的旋转操作包括右旋、左旋、先右旋再左旋、先左旋再右旋。在插入或删除节点后，AVL 树会从底向顶执行旋转操作，使树重新恢复平衡。

数据结构与算法树（B树，B+树，红黑树待完善）

二叉树的介绍

二叉树的节点代码

二叉树的类型

链表二叉树的遍历

层序遍历(广度优先遍历breadth‑first traversal) BFT/BFS

前序、中序、后序遍历（深度优先遍历）DFT/DFS

复杂度分析

数组二叉树的构造

数组二叉树的优缺点

二叉搜索树

二叉搜索树的构造

二叉搜索树的效率

AVL树

重点回顾

热门文章

最新文章

相关课程

相关电子书

相关实验场景

数据结构与算法 树（B树，B+树，红黑树待完善）

二叉树的介绍

二叉树的节点代码

二叉树的类型

链表二叉树的遍历

层序遍历(广度优先遍历breadth‑first traversal) BFT/BFS

前序、中序、后序遍历（深度优先遍历）DFT/DFS

复杂度分析

数组二叉树的构造

数组二叉树的优缺点

二叉搜索树

二叉搜索树的构造

二叉搜索树的效率

AVL树

重点回顾

热门文章

最新文章

相关课程

相关电子书

相关实验场景

数据结构与算法树（B树，B+树，红黑树待完善）