树一般有两种解题方式：

  • 递归：确定递归条件和终止条件
  • 迭代：利用队列或栈这两种数据结构实现，一般层次遍历用队列实现，前序遍历、中序遍历、后序遍历用栈实现

稍微复杂的问题般都会结合DFS和回溯

二叉树

  • 特殊二叉树包括：
    1. 完全⼆叉树（Complete Binary Tree）：每⼀层都是紧凑靠左排列，计算节点数的时间复杂度是$O(logN*logN)$
    2. 满⼆叉树（Perfect Binary Tree）：每层都是是满的，节点数 = 2^树高 - 1，计算节点数的时间复杂度是$O(logN)$
    3. Full Binary Tree：⼆叉树的所有节点要么没有孩⼦节点，要么有两个孩⼦节点

二叉树的实现

以下代码实现了二叉树的初始化及增加节点函数

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
class Node(object):
    """节点类"""
    def __init__(self, val=-1, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Tree(object):
    """树类"""
    def __init__(self):
        self.root = Node()
        self.myQueue = []

    def add(self, val):
        """为树添加节点"""
        node = Node(val)
        if self.root.val == -1:  # 如果树是空的，则对根节点赋值
            self.root = node
            self.myQueue.append(self.root)
        else:
            treeNode = self.myQueue[0]  # 此结点的子树还没有齐
            if treeNode.left == None:
                treeNode.left = node
                self.myQueue.append(treeNode.left)
            else:
                treeNode.right = node
                self.myQueue.append(treeNode.right)
                self.myQueue.pop(0)  # 如果该结点存在右子树，将此结点丢弃

二叉树的遍历

递归法

以下代码实现了二叉树的前序（跟左右）、中序（左跟右）、后序（左右跟）遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def front_recursive(self, root):
    """利用递归实现树的先序遍历"""
    if root is None:
        return
    print(root.val, end=' ')
    self.front_recursive(root.left)
    self.front_recursive(root.right)

def middle_recursive(self, root):
    """利用递归实现树的中序遍历"""
    if root is None:
        return
    self.middle_recursive(root.left)
    print(root.val, end=' ')
    self.middle_recursive(root.right)

def later_recursive(self, root):
    """利用递归实现树的后序遍历"""
    if root is None:
        return
    self.later_recursive(root.left)
    self.later_recursive(root.right)
    print(root.val, end=' ')

迭代法

以下代码实现了二叉树的前序、中序、后序、层次遍历

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
def front_stack(self, root):
    """利用堆栈实现树的先序遍历"""
    if root is None:
        return
    myStack = []
    node = root
    while node or myStack:
        while node:               # 从根节点开始，一直找它的左子树
            print(node.val, end=' ')
            myStack.append(node)
            node = node.left
        node = myStack.pop()      # while结束表示当前节点node为空，即前一个节点没有左子树了
        node = node.right

def middle_stack(self, root):
    """利用堆栈实现树的中序遍历"""
    if root is None:
        return
    myStack = []
    node = root
    while node or myStack:
        while node:              # 从根节点开始，一直找它的左子树
            myStack.append(node)
            node = node.left
        node = myStack.pop()
        print(node.val, end=' ')
        node = node.right

def later_stack(self, root):
    """利用堆栈实现树的后序遍历"""
    if root is None:
        return
    myStack1 = []
    myStack2 = []
    node = root
    myStack1.append(node)
    while myStack1:                   # 找出后序遍历的逆序存在myStack2里
        node = myStack1.pop()
        if node.left:
            myStack1.append(node.left)
        if node.right:
            myStack1.append(node.right)
        myStack2.append(node)
    while myStack2:                   # 将myStack2中的元素出栈，即为后序遍历次序
        print(myStack2.pop().val, end=' ')

def level_queue(self, root):
    """利用队列实现树的层次遍历"""
    l2 = []
    cur_layer = [root]
    while cur_layer and root:
        l1, next_layer = [], []
        for node in cur_layer:
            l1.append(node.val)
            if node.left:
                next_layer.append(node.left)
            if node.right:
                next_layer.append(node.right)
        cur_layer = next_layer
        l2.append(l1)
    return l2

Morris遍历

二叉树的递归和迭代遍历都需要借助栈，空间复杂度为$O(h)$，其中$h$指二叉树的最大高度。而Morris遍历的时间复杂度为$O(n)$，空间复杂度为$O(1)$。其遍历规则如下：

  • 设当前遍历的节点为cur，若cur无左子树，则cur = cur.right
  • 若cur有左子树，找到cur左子树的最右节点记为mostRight
    • 若mostRight的右子树为空，则令mostRight.right = cur, cur = cur.left
    • 若此时mostRight.right = cur，则令mostRight.right = None, cur = cur.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
def morris(self, root, order):
    """实现Morris遍历"""
    if root is None:
        return
    cur = root
    while cur:
        if cur.left is None:
            print(cur.val, end=' ')
            cur = cur.right
        else:
            mostRight = cur.left
            while mostRight.right is not None and mostRight.right != cur:
                mostRight = mostRight.right
            if mostRight.right is None:
                mostRight.right = cur
                # 先序遍历
                if order == 'front':
                    print(cur.val, end=' ')
                cur = cur.left
            elif mostRight.right == cur:
                # 中序遍历
                if order == 'middle':
                    print(cur.val, end=' ')
                mostRight.right = None
                cur = cur.right

Morris遍历的后序遍历有点麻烦，具体可以看参考文献

测试及结果

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
if __name__ == '__main__':
    """主函数"""
    vals = range(10)           # 生成十个数据作为树节点
    tree = Tree()
    for val in vals:
        tree.add(val)

    print('队列实现层次遍历:')
    print(tree.level_queue(tree.root))  # [[0], [1, 2], [3, 4, 5, 6], [7, 8, 9]]

    print('\n\n递归实现先序遍历:')
    tree.front_recursive(tree.root)     # 0 1 3 7 8 4 9 2 5 6
    print('\n递归实现中序遍历:')
    tree.middle_recursive(tree.root)    # 7 3 8 1 9 4 0 5 2 6
    print('\n递归实现后序遍历:')
    tree.later_recursive(tree.root)     # 7 8 3 9 4 1 5 6 2 0

    print('\n\n堆栈实现先序遍历:')
    tree.front_stack(tree.root)         # 0 1 3 7 8 4 9 2 5 6
    print('\n堆栈实现中序遍历:')
    tree.middle_stack(tree.root)        # 7 3 8 1 9 4 0 5 2 6
    print('\n堆栈实现后序遍历:')
    tree.later_stack(tree.root)         # 7 8 3 9 4 1 5 6 2 0

    print('\nMorris先序遍历：')
    tree.morris(tree.root, 'front')     # 0 1 3 7 8 4 9 2 5 6
    print('\nMorris中序遍历：')
    tree.morris(tree.root, 'middle')    # 7 3 8 1 9 4 0 5 2 6

二叉搜索树

  • 简介：⼆叉搜索树（Binary Search Tree，BST）定义：⼀个⼆叉树中，任意节点的值要⼤于等于左⼦树所有节点的值，且要⼩于等于右边⼦树的所有节点的值。
  • 性质：
    • 每个节点中的值必须大于或等于其左子树中的任何值
    • 每个节点中的值必须小于或等于其右子树中的任何值
    • 二叉搜索树中序遍历时，结果依此递增

N叉树

树的每个节点可以有两个以上的子节点，称为m阶的多叉树或m叉树

节点实现

1
2
3
4
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children

前缀树（字典树）

Trie，前缀树或字典树，是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。前缀树的节点可以是任意一个字符集中的字符，如对于都是小写字母的字符串，字符集就是’a’-‘z’；对于都是数字的字符串，字符集就是’0’-‘9’；对于二进制字符串，字符集就是0和1。前缀树有相当多的应用情景，例如自动补完和拼写检查。

代码实现

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
class Trie:
    """
    实现一个字符集为小写英文字母的前缀树
    """
    def __init__(self):
        """
        Initialize data structure.
        """
        self.children = [None] * 26
        self.isEnd = False  # 该节点是否是字符串的结尾

    def searchPrefix(self, prefix):
        """
        return None if prefix not in trie else the end of the prefix
        """
        node = self
        for ch in prefix:
            ch = ord(ch) - ord('a')
            if not node.children[ch]:
                return None
            node = node.children[ch]
        return node

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self
        for ch in word:
            ch = ord(ch) - ord('a')
            if not node.children[ch]:
                # 子节点不存在，创建一个新的子节点
                node.children[ch] = Trie()
            node = node.children[ch]
        node.isEnd = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.searchPrefix(word)
        return node is not None and node.isEnd

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        return self.searchPrefix(prefix) is not None


if __name__ == '__main__':
    trie = Trie()
    trie.insert("apple")
    print(trie.search("apple"))     # True
    print(trie.search("app"))       # False
    print(trie.startsWith("app"))   # True
    trie.insert("app")
    print(trie.search("app"))       # True

复杂度分析：

  • 时间复杂度：
    初始化为$O(1)$，其余操作为$O(|S|)$，$|S|$是每次插入或查询的字符串长度
  • 空间复杂度：
    $O(|T|·\Sigma)$，其中$|T|$为所有插入字符串的长度之和，$\Sigma$为字符集的大小，代码中$\Sigma=26$

其他特殊结构

  • 线段树
  • 霍夫曼树
  • B树
  • 红黑树

力扣指南

参考资料