树与二叉树

二叉树

树的类型

满二叉树(Perfect Binary Tree)是指除叶子节点外，每个节点都有左右两个子节点的二叉树。例如:

1
            1
2
          /   \
3
         2     3
4
        / \   / \
5
       4   5 6   7

完全二叉树(Complete Binary Tree)指除最后一层外，每层节点都达到最大值，并且最后一层的节点从左到右依次排列的二叉树。例如：

完满二叉树(Full Binary Tree)是指每个节点的度要么是0，要么是2的二叉树。例如:

1
            1
2
          /   \
3
         2     3
4
        / \   / \
5
       4   5 6   7
6
          / \
7
         8   9

平衡二叉树(AVL Tree)是指任意节点的左子树和右子树的高度差不超过1的二叉树。例如:

树的遍历

深度优先遍历（Depth-First Traversal, DFT）

1
void PreOrder(BiTree T){
2
    if(T != NULL){
3
        visit(T);
4
        PreOrder(T->lchild);
5
        PreOrder(T->rchild);
6
    }
7
}

1
void InOrder(BiTree T){
2
    if(T != NULL){
3
        InOrder(T->lchild);
4
        visit(T);
5
        InOrder(T->rchild);
6
    }
7
}

1
void PostOrder(BiTree T){
2
    if(T != NULL){
3
        PostOrder(T->lchild);
4
        PostOrder(T->rchild);
5
        visit(T);
6
    }
7
}

广度优先遍历（Breadth-First Traversal, BFT）

1
def level_order(root: TreeNode | None) -> list[int]:
2
    """层序遍历"""
3
    # 初始化队列，加入根节点
4
    queue: deque[TreeNode] = deque()
5
    queue.append(root)
6
    # 初始化一个列表，用于保存遍历序列
7
    res = []
8
    while queue:
9
        node: TreeNode = queue.popleft()  # 队列出队
10
        res.append(node.val)  # 保存节点值
11
        if node.left is not None:
12
            queue.append(node.left)  # 左子节点入队
13
        if node.right is not None:
14
            queue.append(node.right)  # 右子节点入队
15
    return res

由遍历序列构造二叉树

在节点值不重复的前提下，以下两种遍历序列可以唯一确定一棵二叉树：

前序+中序，105. 从前序与中序遍历序列构造二叉树
中序+后序，106. 从中序与后序遍历序列构造二叉树

二叉搜索树(BST)

满足以下性质的二叉树称为二叉排序树(二叉搜索树)：

若树为空，则它是一棵二叉排序树。
若左子树非空，则左子树上所有结点的值均小于根结点的值。
若右子树非空，则右子树上所有结点的值均大于根结点的值。
左、右子树也分别是一棵二叉排序树。

对二叉排序树进行中序遍历，可以得到一个递增的有序序列

Credits

第 7 章树 - Hello 算法