数据结构
树(tree)

二叉树

二叉树(binary tree)是一种非线性数据结构，代表“祖先”与“后代”之间的派生关系，体现了“一分为二”的分治逻辑。 与链表类似，二叉树的基本单元是节点，每个节点包含值、左子节点引用和右子节点引用。

tree

/* 二叉树节点结构体 */
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}
/* 构造方法 */
func NewTreeNode(v int) *TreeNode {
    return &TreeNode{
        Left:  nil, // 左子节点指针
        Right: nil, // 右子节点指针
        Val:   v,   // 节点值
    }
}
  • 根节点：一棵树最上面的节点称为根节点。
  • 父节点、子节点：如果一个节点下面连接多个节点，那么该节点称为父节点，它下面的节点称为子 节点。
  • 叶子节点：没有任何子节点的节点称为叶子节点。
  • 兄弟节点：具有相同父节点的节点互称为兄弟节点。
  • 节点度：节点拥有的子树数。上图中，13的度为2，46的度为1，28的度为0。
  • 树的深度：从根节点开始（其深度为0）自顶向下逐层累加的。上图中，13的深度是1，30的深度是2，28的深度是3。
  • 树的高度：从叶子节点开始（其高度为0）自底向上逐层累加的。54的高度是2，根节点23的高度是3。

二叉树基本操作

初始化

与链表类似，首先初始化节点，然后构建引用（指针）

/* 初始化二叉树 */
// 初始化节点
n1 := NewTreeNode(1)
n2 := NewTreeNode(2)
n3 := NewTreeNode(3)
n4 := NewTreeNode(4)
n5 := NewTreeNode(5)
// 构建节点之间的引用（指针）
n1.Left = n2
n1.Right = n3
n2.Left = n4
n2.Right = n5

插入与删除节点

与链表类似，在二叉树中插入与删除节点可以通过修改指针来实现。

/* 插入与删除节点 */
// 在 n1 -> n2 中间插入节点 P
p := NewTreeNode(0)
n1.Left = p
p.Left = n2
// 删除节点 P
n1.Left = n2

遍历

从物理结构的角度来看，树是一种基于链表的数据结构，因此其遍历方式是通过指针逐个访问节点。然而，树是一种非线性数据结构，这使得遍历树比遍历链表更加复杂，需要借助搜索算法来实现。

二叉树常见的遍历方式包括层序遍历、前序遍历、中序遍历和后序遍历等。

层序遍历

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

层序遍历本质上属于广度优先遍历 breadth-first traversal)，也称广度优先搜索(breadth-first search, BFS)，它体现了一种“一圈一圈向外扩展”的逐层遍历方式。

广度优先遍历通常借助“队列”来实现。队列遵循“先进先出”的规则，而广度优先遍历则遵循“逐层推进”的规则，两者背后的思想是一致的。实现代码如下：

/* 层序遍历 */
func levelOrder(root *TreeNode) []any {
    // 初始化队列，加入根节点
    queue := list.New()
    queue.PushBack(root)
    // 初始化一个切片，用于保存遍历序列
    nums := make([]any, 0)
    for queue.Len() > 0 {
        // 队列出队
        node := queue.Remove(queue.Front()).(*TreeNode)
        // 保存节点值
        nums = append(nums, node.Val)
        if node.Left != nil {
            // 左子节点入队
            queue.PushBack(node.Left)
        }
        if node.Right != nil {
            // 右子节点入队
            queue.PushBack(node.Right)
        }
    }
    return nums
}

前序、中序、后序遍历

前序、中序和后序遍历都属于深度优先遍历(depth-first traversal)，也称深度优先搜索(depth-first search, DFS)，它体现了一种“先走到尽头，再回溯继续”的遍历方式。

/* 前序遍历 */
func preOrder(node *TreeNode) {
    if node == nil {
        return
    }
    // 访问优先级：根节点 -> 左子树 -> 右子树
    nums = append(nums, node.Val)
    preOrder(node.Left)
    preOrder(node.Right)
}
 
/* 中序遍历 */
func inOrder(node *TreeNode) {
    if node == nil {
        return
    }
    // 访问优先级：左子树 -> 根节点 -> 右子树
    inOrder(node.Left)
    nums = append(nums, node.Val)
    inOrder(node.Right)
}
 
/* 后序遍历 */
func postOrder(node *TreeNode) {
    if node == nil {
        return
    }
    // 访问优先级：左子树 -> 右子树 -> 根节点
    postOrder(node.Left)
    postOrder(node.Right)
    nums = append(nums, node.Val)
}

二叉树的类型

满二叉树

Full Binary Tree 除最后一层无任何子节点外，每一层上的所有节点都有两个子节点，最后一层都是叶子节点。满足下列性质：

  1. 一颗树深度为h，最大层数为k，深度与最大层数相同，k=h；
  2. 叶子节点数（最后一层）为2k−1；
  3. 第 i 层的节点数是：2i−1；
  4. 总节点数是：2k-1，且总节点数一定是奇数。

完全二叉树

Complete Binary Tree 若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。满足下列性质：

  1. 只允许最后一层有空缺结点且空缺在右边，即叶子节点只能在层次最大的两层上出现；
  2. 对任一节点，如果其右子树的深度为j，则其左子树的深度必为j或j+1。 即度为1的点只有1个或0个；
  3. 除最后一层，第 i 层的节点数是：2i−1；
  4. 有n个节点的完全二叉树，其深度为：log2n+1或为log2n+1；
  5. 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

平衡二叉树

Balanced Binary Tree 又被称为AVL树，它是一颗空树或左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是一棵平衡二叉树。

二叉搜索树

Binary Search Tree 又称二叉查找树、二叉排序树（Binary Sort Tree）。它是一颗空树或是满足下列性质的二叉树：

  1. 若左子树不空，则左子树上所有节点的值均小于或等于它的根节点的值；
  2. 若右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；
  3. 左、右子树也分别为二叉排序树。

红黑树

Red Black Tree 是每个节点都带有颜色属性（颜色为红色或黑色）的自平衡二叉查找树，满足下列性质：

  1. 节点是红色或黑色；
  2. 根节点是黑色；
  3. 所有叶子节点都是黑色；
  4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)
  5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
哈希表(hash map)堆(heap)