数据结构基础：认识树的类型和遍历方式

# 第一章：引言

## 第二章：树的基础概念

### 第三章：常见的树类型

在本章中，我们将介绍一些常见的树类型，以及它们的特点和应用场景。

#### 二叉树
二叉树是一种每个节点最多有两个子树的树结构。它具有以下特点：
- 每个节点最多有两个子节点：左子节点和右子节点。
- 可以用递归的方式定义。
- 在计算机科学中广泛应用，如在编译器中用于构建语法树。

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

# 创建一个简单的二叉树
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

#### 二叉搜索树（BST）
二叉搜索树是一种二叉树，具有以下特点：
- 左子树上所有节点的值均小于根节点的值。
- 右子树上所有节点的值均大于根节点的值。
- 可以用于快速搜索和排序。

class Node {
    int value;
    Node left, right;

    public Node(int value) {
        this.value = value;
        left = right = null;
    }
}

// 创建一个简单的二叉搜索树
Node root = new Node(8);
root.left = new Node(3);
root.right = new Node(10);
root.left.left = new Node(1);
root.left.right = new Node(6);

#### 平衡树
平衡树是一种特殊的二叉搜索树，其左右子树的高度差不超过1。它具有以下特点：
- 可以确保在最坏情况下的操作也能保持较好的时间复杂度。
- AVL树和红黑树是常见的平衡树实现。

type Node struct {
    value int
    left  *Node
    right *Node
}

// 创建一个简单的平衡树
func NewNode(value int) *Node {
    return &Node{value: value, left: nil, right: nil}
}

func main() {
    root := NewNode(10)
    root.left = NewNode(5)
    root.right = NewNode(20)
    root.left.left = NewNode(2)
    root.left.right = NewNode(8)
}

## 第四章：树的遍历方式

树是一种重要的数据结构，它的遍历方式是对树中的节点进行访问和处理的方式。树的遍历方式有两种主要类型：深度优先遍历和广度优先遍历。

深度优先遍历（Depth-First Traversal）是指从树的根节点开始，先访问子节点，再逐层向下访问子节点的子节点，直到访问到最底层的子节点（叶子节点）。深度优先遍历可以分为三种方式：前序遍历、中序遍历和后序遍历。

### 4.1 深度优先遍历

#### 4.1.1 前序遍历

前序遍历（Pre-order Traversal）是指先访问根节