# 二叉树 (Binary Tree)

二叉树是计算机中基础且重要的数据结构。它由一系列节点组成，每个节点最多有两个子节点。二叉树广泛应用于排序、查找和图形处理等领域。

# 二叉树的定义

二叉树是一种树形的数据结构，其中每个节点最多有两个子节点，通常称为“左子节点”和“右子节点”。每个节点包含三个部分：

  • 数据部分（data）：节点保持的数据。
  • 左子节点（left child）：指向左子节点的指针。
  • 右子节点（right child）：指向右子节点的指针。

# 二叉树的分类

二叉树的种类有很多，最常见的包括：

  • 普通二叉树：没有什么特殊限制的二叉树。
  • 二叉搜索树（BST）：每个节点的左子树中的所有节点值都小于该节点的值，右子树中的所有节点值都大于该节点的值。
  • 平衡二叉树：例如AVL和红黑树，它们保持树的高度尽量平衡，确保操作时间复杂度为O(log n)。
  • 完全二叉树：除了最后一层，其他层的节点数都达到了最大，并且最后一层的节点都集中在最左侧。

# 二叉树的基本操作

  • 插入：向二叉树中插入一个新节点。
  • 查找：在树中查找某个值是否存在。
  • 删除：删除树中的某个节点。
  • 遍历：访问树中的所有节点。最常见的遍历方式有:
    • 前序遍历：根节点 -> 左子树 -> 右子树
    • 中序遍历：左子树 -> 根节点 -> 右子树
    • 后序遍历：左子树 -> 右子树 -> 根节点
    • 层序遍历：从根节点开始，逐层遍历每一层的节点。

# 二叉树的实现

普通二叉树的插入流程可以更灵活，没有像二叉搜索树那样基于节点值大小的限制。我们可以根据空位置插入新的节点。一般而言，普通二叉树的插入是按层次遍历（或广度优先遍历）插入的，依次填充每一层的空位置。

这里我们以普通二叉树为例，给出一个简单的实现：

# 定义

// 二叉树节点
type Node struct {
	Val   any   // 节点值 (可以是任意类型)
	Left  *Node // 左子树
	Right *Node // 右子树
}

// 二叉树
type BinaryTree struct {
	Root *Node // 根节点
}

// 初始化
func NewBinaryTree() *BinaryTree {
	return &BinaryTree{}
}
  • 节点：定义一个Node结构体，包含节点值Val，左子节点Left和右子节点Right。
  • 二叉树：定义一个BinaryTree结构体，包含根节点Root。
  • 初始化：NewBinaryTree函数用于创建一个新的二叉树实例。

# 插入

# 代码实现

// 插入节点
func (t *BinaryTree) Insert(val any) {
	// 如果根节点为空，则直接创建根节点
	if t.Root == nil {
		t.Root = &Node{Val: val}
		return
	}

	// 使用队列进行层次遍历，找到第一个空节点插入新节点
	queue := []*Node{t.Root}

	// 如果队列为空，则说明树已满，无法插入新节点
	for len(queue) > 0 {
		// 取出队列的第一个节点
		node := queue[0]
		// 将队列的第一个节点出队
		queue = queue[1:]

		// 如果左子树为空，则插入新节点到左子树
		if node.Left == nil {
			node.Left = &Node{Val: val}
			return
		} else {
			// 如果左子树不为空，则将左子树加入队列
			queue = append(queue, node.Left)
		}

		// 如果右子树为空，则插入新节点到右子树
		if node.Right == nil {
			node.Right = &Node{Val: val}
			return
		} else {
			// 如果右子树不为空，则将右子树加入队列
			queue = append(queue, node.Right)
		}
	}
}

时间复杂度为O(n)，其中n是二叉树的节点数。在最坏情况下，我们需要遍历整个二叉树才能找到插入位置。

# 插入过程

假设我们依次插入节点值：10, 5, 15, 3, 7, 12, 18，我们按照层次遍历的方式来插入，依次从根节点开始，先填充左子树，再填充右子树。

# 1. 插入 10
    10
# 2. 插入 5
    10
   /
  5
# 3. 插入 15
    10
   / \
  5   15
# 4. 插入 3
    10
   / \
  5   15
 /
3
# 5. 插入 7
    10
   / \
  5   15
 / \ 
3   7
# 6. 插入 12
    10
   / \
  5     15
 / \   /
3   7 12
# 7. 插入 18
    10
   /  \
  5    15
 / \   / \
3   7 12 18

# 遍历

# 前序遍历

# 顺序
根节点 -> 左子树 -> 右子树
# 实现
// 前序遍历
func (t *BinaryTree) PreOrderTraversal() {
	// 递归函数
	var traversal func(node *Node)
	traversal = func(node *Node) {
		if node == nil {
			return
		}
		// 先打印根节点
		fmt.Print(node.Val)
		// 再遍历左子树
		traversal(node.Left)
		// 最后遍历右子树
		traversal(node.Right)
	}
	// 从根节点开始遍历
	traversal(t.Root)
}
# 示例
    10
   / \
  5   15
 / \   / \
3   7 12 18

前序遍历结果：10 5 3 7 15 12 18

# 中序遍历

# 顺序
左子树 -> 根节点 -> 右子树
# 实现
// 中序遍历
func (t *BinaryTree) InOrderTraversal() {
    // 递归函数
	var traversal func(node *Node)
	traversal = func(node *Node) {
		if node == nil {
			return
		}
        // 先遍历左子树
		traversal(node.Left)
        // 再打印根节点
		fmt.Println(node.Val)
        // 最后遍历右子树
		traversal(node.Right)
	}
	traversal(t.Root)
}
# 示例
    10
   / \
  5   15
 / \   / \
3   7 12 18

中序遍历结果：3 5 7 10 12 15 18

# 后序遍历

# 顺序
左子树 -> 右子树 -> 根节点
# 实现
// 后序遍历
func (t *BinaryTree) PostOrderTraversal() {
    // 递归函数
	var traversal func(node *Node)
	traversal = func(node *Node) {
		if node == nil {
			return
		}
        // 先遍历左子树
		traversal(node.Left)
        // 再遍历右子树
		traversal(node.Right)
        // 最后打印根节点
		fmt.Println(node.Val)
	}
	traversal(t.Root)
}
# 示例
    10
   / \
  5   15
 / \   / \
3   7 12 18

后序遍历结果：3 7 5 12 18 15 10

# 层次遍历

# 顺序
从根节点开始，逐层遍历每一层的节点
# 实现
// 层序遍历
func (t *BinaryTree) LevelOrderTraversal() {
	if t.Root == nil {
		return
	}
    // 使用队列进行层次遍历
	queue := []*Node{t.Root}
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		fmt.Println(node.Val)
        // 左子树不为空 则加入队列
		if node.Left != nil {
			queue = append(queue, node.Left)
		}
        // 右子树不为空则加入队列
		if node.Right != nil {
			queue = append(queue, node.Right)
		}
	}
}
# 示例
    10
   / \
  5   15
 / \   / \
3   7 12 18

层序遍历结果：10 5 15 3 7 12 18

# 查找

使用前序遍历的方式查找节点，遍历所有节点，找到值等于目标值的节点。

// 查找节点
func (t *BinaryTree) Find(val any) []*Node {
	// 查找到的节点
	var result []*Node
	// 递归函数
	var find func(node *Node)
	find = func(node *Node) {
		if node == nil {
			return
		}
		// 如果节点值等于目标值，则将节点加入结果集
		if node.Val == val {
			result = append(result, node)
		}
		// 递归查找左子树
		find(node.Left)
		// 递归查找右子树
		find(node.Right)
	}
	// 从根节点开始查找
	find(t.Root)
	return result
}

时间复杂度为O(n)，其中n是二叉树的节点数。最坏情况下，我们需要遍历整个二叉树才能找到目标节点。

# 删除

删除节点时，需要考虑三种情况：

  1. 被删除的节点是叶子节点，直接删除即可。
  2. 被删除的节点只有一个子节点，则将子节点提升为父节点的子节点。
  3. 被删除的节点有两个子节点，则找到两个子树中的最低层次的最后一个节点，将其值替换为被删除节点的值，然后删除该节点。
// 删除节点
func (t *BinaryTree) Delete(val any) {
	var delete func(node *Node) *Node

	delete = func(node *Node) *Node {
		if node == nil {
			return nil
		}
		node.Left = delete(node.Left)
		node.Right = delete(node.Right)

		if node.Val == val {
			// 如果是叶子节点，直接删除
			if node.Left == nil {
				return nil
			}
			// 如果右子树为空，则返回左子树
			if node.Right == nil {
				return node.Left
			}
			// 如果有两个子节点，则找到层级遍历的最后一个节点，将其值赋给当前节点，然后删除最后一个节点
			queue := []*Node{node}
			var lastNode, parent *Node
			var isLeft bool

			for len(queue) > 0 {
				current := queue[0]
				queue = queue[1:]
				// 更新最后节点及其父节点
				lastNode = current

				// 把左右子节点加入队列
				if current.Left != nil {
					parent = current
					isLeft = true
					queue = append(queue, current.Left)
				}
				if current.Right != nil {
					parent = current
					isLeft = false
					queue = append(queue, current.Right)
				}
			}
			if parent != nil && isLeft {
				parent.Left = nil
			}
			if parent != nil {
				if isLeft {
					parent.Left = nil
				} else {
					parent.Right = nil
				}
			}
			node.Val = lastNode.Val
			return node
		}
		return node
	}
	t.Root = delete(t.Root)
}

时间复杂度为O(n)，其中n是二叉树的节点数。最坏情况下，我们需要遍历整个二叉树才能找到目标节点。

# 总结

二叉树是一种非常基础且重要的数据结构，它在计算机科学中有着广泛的应用。本文介绍了最普通的二叉树（为了方便使用了层级二叉树）的定义、性质、遍历、查找和删除操作，并给出了相应的Go语言实现。

  • MIT Licensed | Copyright © 2024-fbbyqsyea