树和二叉树

本次主题，我们的主角变成了东坝小碰仔，一个帅气迷人的头发浓密泛黄，嘴角总是微笑的小胖子。

树的概念

之所以更换主角，底层的逻辑中核心的本质是对树这种结构由衷的敬叹，参天勃勃，坚实繁杂，却绽放着支撑宇宙真理的终极奥秘。这样的主题必然需要一位配得上位的主角。

树的概念最早可以追溯到20世纪早期的Haskell B. Curry，他提出了提出了“树”这种数据结构的概念，并将其应用于数学逻辑和计算理论中。

树是一种非线性结构，主要是为了应对自然世界中事物之间的复杂关系而设计的一种抽象结构。

假想一下，小胖子（东坝小碰仔）的祖上姓王，从壬河的右畔发迹，已经富了超过3代，他的父亲王仁右是一位钢铁大王，在华城混得风声水起。这一天王仁右突发奇想要为先辈著谱立传，他叫来了东坝小碰仔要他搞一下先辈的族谱，要求简洁明了、层次明确、传承清晰。

小碰仔很兴奋，作为一个合格的程序员，一个资深的极客，他知道他又可以大显身手了。很自然的碰仔翻出了树这种结构，开始边查资料边标记，很快一颗代表他的家族的茂盛的树绽放开来。

碰仔随即像他的父亲展示这种结构，并解释了这种结构的特点：

1. 层次性：树结构是一种层次性的结构，由根节点、内部节点和叶节点组成，节点之间存在明确的层次关系。
2. 分支性：每个节点可以有多个子节点，但每个子节点只有一个父节点，形成分支状结构。
3. 单一路径：树中任意两个节点之间都有唯一的路径相连，保证了数据的唯一性和可靠性。
4. 递归性质：树的定义具有递归性质，即树本身可以看作是由子树组成的，子树又可以继续分解为更小的子树。
5. 无环性：树是一种无环图，不存在环路，保证了数据结构的稳定性和避免了循环引用的问题。
6. 灵活性：树结构可以灵活地表示多对多的关系，适用于各种数据组织和管理场景，具有较高的扩展性和适应性。

“树”这种结构很像一颗真实倒立的树，它的每一个元素称为节点，连线表示节点之间的父子关系，同一层次的节点称为兄弟节点，另外没有子节点的节点一般称为叶子节点。

除此之外，树这种结构还有高度、深度、层、度这几个概念。

树的构成多种多样

二叉树

树的种类繁杂，也更契合现实中的实际场景，但在计算机的世界我们更常用的是二叉树，碰仔继续向他的风度翩翩的父亲介绍到。他的父亲也很识趣，完全捧哏的状态，反问道：二叉树是不是比普通的树简单了。

碰仔撸了撸袖口，崩出白嘟嘟软弹弹来的小臂，咧嘴笑了笑，开始了他生动的一课。

二叉树即各个节点的度不大于 2组成的树。通常二叉树中的分支节点被称为 「左子树」 或 「右子树」

以上形态皆为二叉树。

二叉树的分类

二叉树可以根据不同的特性和性质进行分类，主要包括以下几种类型：

1. 满二叉树（Full Binary Tree）：每个节点要么没有子节点，要么有两个子节点的二叉树。

1. 完全二叉树（Complete Binary Tree）：除了最后一层外，每一层的节点都是满的，并且最后一层的节点靠左排列。

1. 平衡二叉树（Balanced Binary Tree）：左右子树的高度差不超过1的二叉树，保持树的高度平衡，提高检索效率。

1. 排序二叉树（Binary Search Tree）：左子树上所有节点的值均小于根节点的值，右子树上所有节点的值均大于根节点的值，可以实现高效的查找、插入和删除操作。

其它还有一些更高阶的二叉树，如红黑树、AVL树等。

二叉树的存储方式

二叉树存储形式一般包含三种方式【顺序存储】、【链式存储】、【线索存储】

1. 顺序存储结构：将二叉树的节点按照层次顺序依次存储在数组中，根节点存储在数组下标为1的位置，左子节点存储在父节点的2i位置，右子节点存储在父节点的2i+1位置。这种方式适合完全二叉树，但对于非完全二叉树会造成空间浪费。

1. 链式存储结构：通过定义节点结构体，包含数据域和指向左右子节点的指针，通过指针的方式连接各个节点，形成二叉树的结构。这种方式适合任意类型的二叉树，但需要额外的指针空间。

1. 线索二叉树：在普通二叉树的基础上，增加了指向中序遍历前驱和后继节点的线索，可以提高中序遍历的效率。线索二叉树可以通过中序遍历构建线索，使得遍历时不需要使用递归或栈，节省了空间和时间。

   • 如果ltag=0，表示指向节点的左孩子。如果ltag=1，则表示lchild为线索，指向节点的直接前驱

   • 如果rtag=0，表示指向节点的右孩子。如果rtag=1，则表示rchild为线索，指向节点的直接后继

不同的存储方式各有优劣，可以根据实际需求和应用场景选择合适的存储方式来实现二叉树的存储和操作

二叉树的遍历

二叉树遍历是指按照一定顺序访问二叉树中所有节点的过程。

二叉树遍历方式主要包括【前序遍历】、【中序遍历】、【后序遍历】和【层序遍历】。在遍历过程中，每个节点都会被访问且仅被访问一次，可以对节点进行输出、处理或其他操作。

二叉树的遍历方式实现主要包含两种方法：【递归法】和【迭代法】。

前序遍历	OK	OK
中序遍历	OK	OK
后续遍历	OK	OK
层序遍历		OK

• 深度优先遍历
• • 前序遍历（递归法，迭代法）
  • 中序遍历（递归法，迭代法）
  • 后序遍历（递归法，迭代法）
• 广度优先遍历
• • 层次遍历（迭代法）

递归实现

以中序为例，步骤为：

1. 判断二叉树是否为空，为空则直接返回。
2. 先递归遍历左子树。
3. 然后访问根节点。
4. 最后递归遍历右子树。

中序遍历递归实现代码如下：

func inorderTraversal(root *TreeNode) []int {
	result := make([]int, 0)

	var dfs func(node *TreeNode)
	dfs = func(node *TreeNode) {
		if node == nil { // 结束条件
			return
		}

		dfs(node.Left) // 遍历左
		result = append(result, node.Val) // 修改这行代码的位置，可以实现前序、后续
		dfs(node.Right) // 遍历右
	}

	dfs(root)
	return result
}

递归的代码改一下顺序就是前序和后续。

迭代实现

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是很自然的可以用栈模拟递归，也就是迭代法的实现思路。

前序遍历

前序遍历是：根、左、右。步骤如下：

1. 创建一个栈，用于存储待访问的节点。
2. 将根节点入栈。
3. 循环执行以下步骤，直到栈为空：

a. 弹出栈顶节点，访问该节点。 

b. 如果该节点的右子节点不为空，则将右子节点入栈（注意先入右子节点，再入左子节点，保证左子节点先被访问）。 

c. 如果该节点的左子节点不为空，则将左子节点入栈。

1. 当栈为空且所有节点都被访问后，遍历结束。

前序遍历的代码

func preorderTraversal(root *TreeNode) []int {
    result := []int{}

	if root == nil {
		return result
	}

	st := stack.New()
    st.Push(root)

    for st.Len() > 0 {
        node := st.Pop().(*TreeNode)

        result = append(result, node.Val) // 访问
        if node.Right != nil {
            st.Push(node.Right) // 先入栈右
        }
        if node.Left != nil {
            st.Push(node.Left)
        }
    }
    return result
}

中序遍历

中序遍历的顺序为：左、根、右，所以保证在左子树访问之前，当前节点不能出栈。

中序遍历的步骤：

1. 创建一个栈，用于存储待访问的节点。
2. 初始化当前节点为根节点。
3. 循环执行以下步骤，直到栈为空或当前节点为空：

a. 将当前节点及其所有左子节点依次入栈，直到当前节点为空。 

b. 弹出栈顶节点，访问该节点。 

c. 将当前节点指向弹出节点的右子节点，重复步骤a。

1. 当栈为空且当前节点为空时，遍历结束。

中续遍历代码：

func inorderTraversal(root *TreeNode) []int {
    var result []int
    stack := make([]*TreeNode, 0)
    curr := root

    for curr != nil || len(stack) > 0 {
        for curr != nil { // 左入栈，一直到叶子
            stack = append(stack, curr)
            curr = curr.Left
        }
        curr = stack[len(stack)-1]
        stack = stack[:len(stack)-1] // 左出栈
        result = append(result, curr.Val) 
        curr = curr.Right // 访问右
    }

    return result
}

后续遍历

后续遍历是左右中，特殊的地方在于保证在左右孩子节点访问结束之前，当前节点不能出栈，步骤如下：

1. 创建一个栈，用于存储待访问的节点。
2. 初始化当前节点为根节点。
3. 循环执行以下步骤，直到栈为空或当前节点为空： 

a. 将当前节点入栈。 

b. 如果当前节点的左子节点不为空，则将左子节点作为当前节点。 

c. 如果当前节点的右子节点不为空，则将右子节点作为当前节点。 

d. 如果当前节点的左右子节点都为空，或者当前节点的左右子节点都已经被访问过，那么将当前节点出栈并访问。 

e. 标记当前节点为已访问。

1. 当栈为空且当前节点为空时，遍历结束。

代码如下:

func postorderTraversal(root *TreeNode) []int {
    var result []int
    stack := make([]*TreeNode, 0)
    visited := make(map[*TreeNode]bool)
    curr := root

    for curr != nil || len(stack) > 0 {
        for curr != nil { // 左入栈，一直到叶子
            stack = append(stack, curr)
            curr = curr.Left
        }
        curr = stack[len(stack)-1]
        if curr.Right == nil || visited[curr.Right] { // 判断右是否访问，只有右访问了才出栈
            result = append(result, curr.Val) // 访问该节点
            stack = stack[:len(stack)-1]
            visited[curr] = true
            curr = nil
        } else {
            curr = curr.Right // 访问右
        }
    }

    return result
}

层序遍历

二叉树的层序遍历是一种广度优先搜索（BFS）的方法，按照树的层级顺序逐层访问节点。一般借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑。

代码如下：

func levelOrder(root *TreeNode) [][]int {

	result := make([][]int, 0)
	if root == nil {
		return result
	}

	queue := NewQueue()
	queue.Push(root)
	for !queue.Empty() {
		vals := make([]int, 0)
		len := queue.Length()      // 这里必须搞出来长度
		for i := 0; i < len; i++ { // 下一层所有入队
			item := queue.Pop()    // 访问当前节点
			vals = append(vals, item.Val)

			if item.Left != nil {
				queue.Push(item.Left) // 左
			}
			if item.Right != nil {
				queue.Push(item.Right) // 右
			}
		}

		result = append(result, vals)
	}
	return result
} 

最后

只顾着讲内容，差一点忘了我们的主角小碰仔，还是由他做一次他最擅长的总结，树是整个数学和计算机科学中非常重要和NB数据结构之一，他在很多场景有着不可替代的作用，比如编译器、人工智能、网络通信等。就如同小碰仔一样低调却内心丰富，用一腔热血表达书写构架这个世界，在每一个极其微小或者雄大的地方都能看到他杰出的设计。