【大模型2609·数据结构算法·06】层次结构核心：二叉树存储体系与二叉搜索树BST深度实战

专栏导读：跨越线性维度迈向层次拓扑。本篇系统阐述树与二叉树的数学性质与存储表示，全面攻克二叉搜索树（BST）的核心生命周期：包含精准检索、递归插入、以及删除操作中最复杂的三种情况（无子节点/单子节点/双子节点寻找中序后继），手写前中后序递归与队列层序遍历。

树

树的概述

树（Tree）由一系列具有层次关系的节点（Node）组成。

image15.png

树的常见术语：

父节点：节点的上层节点。

子节点：节点的下层节点。

根节点：位于树的顶端，没有父节点的节点。

叶节点：位于树的底端，没有子节点的节点。

边：连接两个节点的线段。

节点的度：节点的子节点数量。

节点的层：从根开始定义起，根为第1层，根的子节点为第2层，以此类推。

节点的深度：从根节点到该节点所经过的边的数量，根的深度为0。

节点的高度：从距离该节点最远的叶节点到该节点所经过的边的数量，所有叶节点的高度为0。

树的深度（高度）：从根节点到最远叶节点所经过的边的数量。

image16.png

二叉树简介

树形结构中最具代表性的一种就是二叉树（Binary Tree）。二叉树规定，每个节点最多只能有两个子节点，两个子节点分别被称为左子节点和右子节点。以左子节点为根节点的子树被称为左子树，以右子节点为根节点的子树被称为右子树。

image17.png

二叉树存储结构

二叉树的数组存储

image18.png

采用数组结构存储二叉树，访问与遍历速度较快。但不适合存储数据量过大的树，且增删效率较低，而且树中存在大量None的情况下空间利用率较低，因此不是主流方式。

二叉树的链表存储

image19.png

常见的二叉树

完全二叉树

完全二叉树只有最下面一层的节点未被填满，且靠左填充。

image20.png

满二叉树

满二叉树所有层的节点都被完全填满，满二叉树也是一种完全二叉树。

image21.png

平衡二叉树

平衡二叉树中任意节点的左右子树高度之差不超过1。

image22.png

二叉搜索树

二叉搜索树中的每个节点的值，大于其左子树中的所有节点的值，并且小于右子树中的所有节点的值。

image23.png

AVL树

AVL 树是一种自平衡的二叉搜索树，插入和删除时会进行旋转操作来保证树的平衡性。

红黑树

红黑树是一种特殊的二叉搜索树，除了二叉搜索树的要求外，它还具有以下特性：

每个节点或者是黑色，或者是红色。

根节点是黑色。

每个叶节点都是黑色。这里叶节点是指为空（None）的节点。

红色节点的两个子节点必须是黑色的。即从每个叶到根的所有路径上不能有两个连续的红色节点。

从任一个节点到其每个叶的所有路径上包含相同数目的黑色节点。

堆

堆（Heap）是一种满足特定条件的完全二叉树，主要可分为两种类型：

大顶堆：每个父节点的值都大于等于其子节点的值。根节点为树中的最大值。

小顶堆：每个父节点的值都小于等于其子节点的值。根节点为树中的最小值。

霍夫曼树

霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树，通常用于数据压缩，它的构建基于字符出现频率的概率。

B树

B树是一种自平衡的多路查找树。虽然它不是严格意义上的二叉树，但与二叉树的结构类似。经常用于数据库、文件系统等需要磁盘访问的应用。

B+树

B+树是B树的优化版本。它通过将数据集中存储在叶子节点并通过链表连接来实现高效的范围查询，并且非叶子节点仅存储索引，提高了磁盘利用率。

二叉搜索树的功能定义

方法 说明
size() 返回树中节点个数
is_empty() 判断树是否为空
search(item) 查找节点是否存在
add(item) 向二叉搜索树中插入节点
remove(item) 从二叉搜索树中删除节点
for_each(func, order) 按指定方式遍历二叉树

二叉树的创建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
from collections import deque

class Node:
    """二叉树节点"""

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinarySearchTree:
    """二叉搜索树"""

    def __init__(self):
        """初始化二叉树"""
        self.__root = None
        self.__size = 0

    def print_tree(self):
        """打印树的结构"""

        # 先得到树的层数
        def get_layer(node):
            """递归计算树的层数"""
            if node is None:
                return 0
            else:
                left_depth = get_layer(node.left)
                right_depth = get_layer(node.right)
                return max(left_depth, right_depth) + 1

        layer = get_layer(self.__root)

        # 层序遍历并打印
        queue = deque([(self.__root, 1)])
        current_level = 1
        while queue:
            node, level = queue.popleft()
            if level > current_level:
                print()
                current_level += 1
            if node:
                print(f"{node.data:^{20*layer//2**(level-1)}}", end="")
            else:
                print(f"{"N":^{20*layer//2**(level-1)}}", end="")
            if level < layer:
                if node:
                    queue.append((node.left, level + 1))
                    queue.append((node.right, level + 1))
                else:
                    queue.append((None, level + 1))
                    queue.append((None, level + 1))
        print()

    @property
    def size(self):
        """返回树中节点的个数"""
        return self.__size

    def is_empty(self):
        """判断树是否为空"""
        return self.__size == 0

二叉搜索树的查找操作

查找时先与当前节点比较大小，等于则找到了目标节点，小于则向左子节点查找，大于则向右子节点查找。如果查找到None仍未找到则说明该节点不在树中。

image24.png

后续插入与删除操作也会用到查找，所以此处提供一个__search_pos()方法，返回查找到的节点和其父节点供后续使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def search(self, item):
    """查找节点是否存在"""
    return self.__search_pos(item)[0] is not None

def __search_pos(self, item):
    """查找节点，返回(节点,父节点)。如果节点不存在则为None，此时父节点为一个叶节点"""
    parent = None
    current = self.__root
    while current:
        if item == current.data:
            break
        parent = current
        current = current.left if item < current.data else current.right
    return current, parent

二叉搜索树的插入操作

插入时先执行查找操作，查找时保存当前节点的父节点。如果找到了节点则说明树中已有此元素，退出。如果找到了None，应将该元素插入到对应的节点下。

image25.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def add(self, item):
    """插入节点"""
    node = Node(item)
    if self.is_empty():
        self.__root = node
    else:
        current, parent = self.__search_pos(item)
        # 如果节点之前已存在则返回
        if current:
            return
        # 如果节点之前不存在，则插入父节点的左节点或右节点
        if parent.data > item:
            parent.left = node
        else:
            parent.right = node
    self.__size += 1

二叉搜索树的删除操作

需要保证删除节点后仍然保证二叉搜索树的性质。删除操作需要根据目标节点的子节点数量为0、1、2分三种情况。

目标节点的子节点数量为0

直接删除目标节点。

image26.png

目标节点的子节点数量为1

将目标节点替换为其子节点。

image27.png

目标节点的子节点数量为2

使用目标节点的右子树最小节点、或左子树最大节点替换目标节点。

image28.png

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
def remove(self, item):
    """删除节点"""
    current, parent = self.__search_pos(item)
    if not current:
        return

    # 如果删除的是叶节点（没有子节点）
    if not current.left and not current.right:
        if parent:
            if parent.left == current:
                parent.left = None
            else:
                parent.right = None
        else:
            # 如果没有父节点，说明是根节点
            self.__root = None

    # 如果删除的节点只有一个子节点
    elif not current.left or not current.right:
        child = current.left if current.left else current.right
        if parent:
            if parent.left == current:
                parent.left = child
            else:
                parent.right = child
        else:
            # 如果没有父节点，说明是根节点
            self.__root = child

    # 如果删除的节点有两个子节点
    else:
        # 找到中序后继（右子树中最小的节点）
        successor = self.__get_min(current.right)
        successor_data = successor.data
        # 删除中序后继节点
        self.remove(successor_data)
         # 因为current知识把值替换，没有删除
        self.__size += 1
        # 用中序后继的值替代当前节点
        current.data = successor_data

    self.__size -= 1

def __get_min(self, node):
    """找到当前子树的最小节点"""
    current = node
    while current.left:
        current = current.left
    return current

二叉树的遍历

深度优先

深度优先搜索（DFS，Depth First Search）尽可能地深入每一个分支，直到不能再深入为止，然后回溯到上一个节点，继续尝试其他的分支。

image29.png

前序遍历

先访问当前节点，再访问节点的左子树，再访问节点的右子树。

1
2
3
4
5
6
7
def dfs(node):
    """前序遍历"""
    if node is None:
        return
    print(node)  # 访问当前节点
    dfs(node.left)  # 访问节点的左子树
    dfs(node.right)  # 访问节点的右子树
中序遍历

先访问节点的左子树，再访问当前节点，再访问节点的右子树。

二叉搜索树中序遍历的结果是有序的。

1
2
3
4
5
6
7
def dfs(node):
    """中序遍历"""
    if node is None:
        return
    dfs(node.left)  # 访问节点的左子树
    print(node)  # 访问当前节点
    dfs(node.right)  # 访问节点的右子树
后续遍历

先访问节点的左子树，再访问节点的右子树，再访问当前节点。

1
2
3
4
5
6
7
def dfs(node):
    """后序遍历"""
    if node is None:
        return
    dfs(node.left)  # 访问节点的左子树
    dfs(node.right)  # 访问节点的右子树
    print(node)  # 访问当前节点

广度优先

层序遍历

广度优先搜索（BFS，Breadth First Search）从起始节点开始，首先访问该节点的所有子节点，然后再访问子节点的子节点，依此类推，逐层访问节点。

image30.png

广度优先搜索一般使用队列实现，每访问一个节点，就将该节点的子节点添加进队列中。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
def for_each(self, func, order="inorder"):
    """遍历树，默认中序遍历"""
    match order:
        case "inorder":
            self.__inorder_traversal(func)
        case "preorder":
            self.__preorder_traversal(func)
        case "postorder":
            self.__postorder_traversal(func)
        case "levelorder":
            self.__levelorder_traversal(func)

def __inorder_traversal(self, func):
    """深度优先搜索：中序遍历"""

    def inorder(node):
        if node:
            inorder(node.left)
            func(node.data)
            inorder(node.right)

    inorder(self.__root)

def __preorder_traversal(self, func):
    """深度优先搜索：前序遍历"""

    def preorder(node):
        if node:
            func(node.data)
            preorder(node.left)
            preorder(node.right)

    preorder(self.__root)

def __postorder_traversal(self, func):
    """深度优先搜索：后序遍历"""

    def postorder(node):
        if node:
            postorder(node.left)
            postorder(node.right)
            func(node.data)

    postorder(self.__root)

def __levelorder_traversal(self, func):
    """广度优先搜索：层序遍历"""
    queue = deque()
    queue.append(self.__root)
    while queue:
        node = queue.popleft()
        func(node.data)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
from collections import deque

class Node:
    """二叉树节点"""

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinarySearchTree:
    """二叉搜索树"""

    def __init__(self):
        """初始化二叉树"""
        self.__root = None
        self.__size = 0

    def print_tree(self):
        """打印树的结构"""

        # 先得到树的层数
        def get_layer(node):
            """递归计算树的层数"""
            if node is None:
                return 0
            else:
                left_depth = get_layer(node.left)
                right_depth = get_layer(node.right)
                return max(left_depth, right_depth) + 1

        layer = get_layer(self.__root)
        # 层序遍历并打印
        queue = deque([(self.__root, 1)])
        current_level = 1
        while queue:
            node, level = queue.popleft()
            if level > current_level:
                print()
                current_level += 1
            if node:
                print(f"{node.data:^{20*layer//2**(level-1)}}", end="")
            else:
                print(f"{"N":^{20*layer//2**(level-1)}}", end="")
            if level < layer:
                if node:
                    queue.append((node.left, level + 1))
                    queue.append((node.right, level + 1))
                else:
                    queue.append((None, level + 1))
                    queue.append((None, level + 1))
        print()

    @property
    def size(self):
        """返回树中节点的个数"""
        return self.__size

    def is_empty(self):
        """判断树是否为空"""
        return self.__size == 0

    def search(self, item):
        """查找节点是否存在"""
        return self.__search_pos(item)[0] is not None

    def __search_pos(self, item):
        """查找节点，返回(节点,父节点)。如果节点不存在则为None，此时父节点为一个叶节点"""
        parent = None
        current = self.__root
        while current:
            if item == current.data:
                break
            parent = current
            current = current.left if item < current.data else current.right
        return current, parent

    def add(self, item):
        """插入节点"""
        node = Node(item)
        if self.is_empty():
            self.__root = node
        else:
            current, parent = self.__search_pos(item)
            # 如果节点之前已存在则返回
            if current:
                return
            # 如果节点之前不存在，则插入父节点的左节点或右节点
            if parent.data > item:
                parent.left = node
            else:
                parent.right = node
        self.__size += 1

    def remove(self, item):
        """删除节点"""
        current, parent = self.__search_pos(item)
        if not current:
            return

        # 如果删除的是叶节点（没有子节点）
        if not current.left and not current.right:
            if parent:
                if parent.left == current:
                    parent.left = None
                else:
                    parent.right = None
            else:
                # 如果没有父节点，说明是根节点
                self.__root = None

        # 如果删除的节点只有一个子节点
        elif not current.left or not current.right:
            child = current.left if current.left else current.right
            if parent:
                if parent.left == current:
                    parent.left = child
                else:
                    parent.right = child
            else:
                # 如果没有父节点，说明是根节点
                self.__root = child

        # 如果删除的节点有两个子节点
        else:
            # 找到中序后继（右子树中最小的节点）
            successor = self.__get_min(current.right)
            successor_data = successor.data
            # 删除中序后继节点
            self.remove(successor_data)
             # 因为current知识把值替换，没有删除
            self.__size += 1
            # 用中序后继的值替代当前节点
            current.data = successor_data

        self.__size -= 1

    def __get_min(self, node):
        """找到当前子树的最小节点"""
        current = node
        while current.left:
            current = current.left
        return current

    def for_each(self, func, order="inorder"):
        """遍历树，默认中序遍历"""
        match order:
            case "inorder":
                self.__inorder_traversal(func)
            case "preorder":
                self.__preorder_traversal(func)
            case "postorder":
                self.__postorder_traversal(func)
            case "levelorder":
                self.__levelorder_traversal(func)

    def __inorder_traversal(self, func):
        """深度优先搜索：中序遍历"""

        def inorder(node):
            if node:
                inorder(node.left)
                func(node.data)
                inorder(node.right)

        inorder(self.__root)

    def __preorder_traversal(self, func):
        """深度优先搜索：前序遍历"""

        def preorder(node):
            if node:
                func(node.data)
                preorder(node.left)
                preorder(node.right)

        preorder(self.__root)

    def __postorder_traversal(self, func):
        """深度优先搜索：后序遍历"""

        def postorder(node):
            if node:
                postorder(node.left)
                postorder(node.right)
                func(node.data)

        postorder(self.__root)

    def __levelorder_traversal(self, func):
        """广度优先搜索：层序遍历"""
        queue = deque()
        queue.append(self.__root)
        while queue:
            node = queue.popleft()
            func(node.data)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)