树的二叉表示

# 1. 树的基本概念

## 1.1 树的定义

树（Tree）是一种抽象数据类型（ADT）或是实际生活中具有树状结构的数据组织形式。它是由n（n>=1）个有限节点组成一个具有层次关系的集合。树有一个被称作根（Root）的特殊节点，除根节点外的其余节点被分成m（m>=0）个互不相交的子集T1，T2，...，Tm，其中每一个子集本身又是一棵树，称作原来树的子树。

## 1.2 树的基本术语

在树的基本概念中，我们定义了以下常用术语：

- 节点的度（Degree）：节点拥有的子树数目称为节点的度。
- 叶子节点（Leaf）：度为0的节点，也就是没有子节点的节点。
- 分支节点（Internal Node）：度不为0的节点，也就是至少有一个子节点的节点。
- 层次（Level）：根节点的层次为1，其孩子节点的层次为2，依此类推。
- 深度（Depth）：节点的深度是从根到该节点的唯一路径长，根的深度为0。
- 高度（Height）：树中节点的最大层次称为树的高度。

## 1.3 二叉树的概念

二叉树是每个节点最多拥有两棵子树的树结构。通常将左子树称为左子树，右子树称为右子树。二叉树常用于实现二叉查找树、表达式树等。

接下来，我们将介绍二叉树的表示方法，以及相关的存储结构和遍历算法。

# 2. 二叉树的表示方法

在计算机科学中，二叉树是一种常用的数据结构，它由节点（node）组成，每个节点最多包含两个子节点，分别称为左子节点和右子节点。二叉树的表示方法有多种，下面将介绍常见的两种表示方法：顺序存储结构和链式存储结构。

### 2.1 顺序存储结构

顺序存储结构利用数组来表示二叉树，具体存储方式如下：

1. 将二叉树的根节点存储在数组的第一个位置；
2. 若某节点的下标为i，则它的左子节点的下标为2i，右子节点的下标为2i+1；
3. 若某节点的下标为i，则它的父节点的下标为i/2。

顺序存储结构的优点是可以直观地表示二叉树，每个节点的位置都可以通过下标计算得到，但是它会浪费一部分存储空间，因为并非所有的位置都有节点。

### 2.2 链式存储结构

链式存储结构利用节点和指针来表示二叉树，每个节点包含一个数据域和两个指针域，分别指向左子节点和右子节点。具体实现如下：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

链式存储结构的优点是灵活性较高，可以动态地创建和删除节点，适用于频繁变动的场景。但是相比于顺序存储结构，在访问某个节点时需要通过指针遍历到该节点，效率稍低。

### 2.3 完全二叉树的特点

完全二叉树是一种特殊的二叉树，除了最后一层的叶子节点外，其他层的节点都是满的，并且最后一层的叶子节点尽量靠左排列。由于满足这些特点，完全二叉树可以使用数组来表示，不会浪费存储空间。顺序存储结构在处理完全二叉树时特别适用。

以上是二叉树的常见表示方法，根据实际需求选择合适的方式来表示二叉树。接下来，我们将介绍二叉树的遍历算法，包括深度优先遍历和广度优先遍历。

# 3. 二叉树的遍历

二叉树的遍历是指按照某种规则访问二叉树中的所有节点。常用的遍历方法包括深度优先遍历和广度优先遍历两种。

#### 3.1 深度优先遍历（前序、中序、后序遍历）

深度优先遍历是指优先访问节点的子节点，使用递归或栈的方式进行遍历。深度优先遍历有三种方式：

- **前序遍历**：先访问根节点，然后按照左子树-右子树的顺序遍历。
- **中序遍历**：先遍历左子树，然后访问根节点，最后遍历右子树。
- **后序遍历**：先遍历左子树，然后遍历右子树，最后访问根节点。

在Python中，可以使用递归实现二叉树的深度优先遍历，代码如下：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def preorderTraversal(root):
    result = []
    if root:
        result.append(root.val)
        result += preorderTraversal(root.left)
        result += preorderTraversal(root.right)
    return result

def inorderTraversal(root):
    result = []
    if root:
        result += inorderTraversal(root.left)
        result.append(root.val)
        result += inorderTraversal(root.right)
    return result

def postorderTraversal(root):
    result = []
    if root:
        result += postorderTraversal(root.left)
        result += postorderTraversal(root.right)
        result.append(root.val)
    return result

# 示例代码
# 使用前序遍历构建二叉树
root = TreeNode(