CSP-J算法基础 树状结构与二叉树

前言

在算法和数据结构中，树状结构是非常重要的一类结构，而其中最常见和基础的就是二叉树。二叉树是一种特殊的树状结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。它在很多实际问题中都有广泛的应用，如表达式树、决策树、二叉搜索树等。理解二叉树的性质与操作是学习树状结构的基础，也是掌握复杂数据结构和高效算法的关键。本文将介绍与二叉树相关的基本概念、常见操作及其应用，帮助读者为CSP-J算法竞赛中的树状结构问题打下坚实的基础。

树状结构

树状结构是一种数据结构，它由一组节点组成，并以分层的方式组织数据。它形似一棵倒置的树，根节点位于最上方，子节点向下分支。每个节点有一个父节点（除了根节点），以及0个或多个子节点。它常用于表示具有层级关系的数据，例如组织结构、文件系统等。

一棵树是由n个元素组成的有限集合，每个元素称为一个结点(node)，有一个特定的结点，称为根结点或树根(root)，除根结点外，其余结点能分成个互不相交的有限集合,其中的每个子集又都是一棵树，这些集合称为这棵树的子树。

树状结构的基本概念：

• 根节点（Root Node）： 树的起点，没有父节点。
• 叶子节点（Leaf Node）： 没有子节点的节点。
• 子节点（Child Node）： 某个节点的直接后继节点。
• 父节点（Parent Node）： 某个节点的直接前驱节点。
• 深度（Depth）： 从根节点到某节点的路径长度。
• 高度:节点到叶子节点的最长路径(边数)
• 层数:深度+1
• 树的高度：根节点的高度

为什么需要树状结构？

树状结构能够有效表示层级关系，在搜索和查找数据时可以提升效率。常见的应用场景包括：

• 文件系统： 用来组织文件和目录。
• HTML DOM： 在网页中，HTML标签也组织成树状结构。
• 数据库索引： 如B树、B+树用于数据库查询优化。

优点

1. 快速搜索和查找： 通过分层结构，可以减少遍历节点的数量。
2. 组织层次清晰： 清晰表示数据的层级关系。
3. 插入与删除操作高效： 适合频繁的插入、删除操作的场景。

树状结构的示例

Root
 ├── Child1
 │    ├── Child1.1
 │    └── Child1.2
 └── Child2
      ├── Child2.1
      │    └── Child2.1.1
      └── Child2.2

这个简单的字符串树状图展示了根节点Root，它有两个子节点Child1和Child2。每个子节点可能继续包含自己的子节点，从而形成一棵完整的树。

二叉树

什么是二叉树？

二叉树是一种特殊的树状数据结构，其中每个节点最多只能有两个子节点，分别称为左子节点和右子节点。它是树的一种形式，严格定义如下：

二叉树是一个由节点组成的有限集合，它满足以下条件：

1. 该树或者为空树（即不包含任何节点），
2. 或者是由一个根节点以及两棵互不相交的、分别称为左子树和右子树的二叉树构成。

二叉树的类型

1. 满二叉树（Full Binary Tree）： 每个节点要么是叶子节点，要么有两个子节点。没有节点只有一个子节点。
   
   n为树的层数

2. 完全二叉树（Complete Binary Tree）： 除了最后一层外，所有层都是满的，最后一层的叶子节点从左到右依次排列。

3. 平衡二叉树（Balanced Binary Tree）： 每个节点的左子树和右子树的高度差不超过1，保证了树的高度尽量小。

4. 搜索二叉树（Binary Search Tree，BST）： 左子树的所有节点值小于根节点，右子树的所有节点值大于根节点。

5. 完美二叉树（Perfect Binary Tree）： 一种特殊的满二叉树，所有叶子节点都在同一层。

什么样的树不是二叉树？

• 多叉树（k-ary Tree）： 每个节点可以有超过两个子节点，例如三叉树（每个节点最多有3个子节点）。
• 普通树： 每个节点可以有任意数量的子节点，而不限于两个。

二叉树的五种形态

1. 空二叉树（Empty Binary Tree）：

   • 这是一棵没有任何节点的树。

   Ø
   

2. 只有根节点的二叉树（Single Node Tree）：

   • 这棵树只有一个根节点，没有子节点。

   Root
   

3. 左子树为空的二叉树（Right Skewed Binary Tree）：

   • 每个节点只有右子节点，左子树为空。

   Root
      └── Node1
           └── Node2
                └── Node3
   

4. 右子树为空的二叉树（Left Skewed Binary Tree）：

   • 每个节点只有左子节点，右子树为空。

   Root
   └── Node1
       └── Node2
           └── Node3
   

5. 完全二叉树（Complete Binary Tree）：

   • 除最后一层外，所有层都是满的，最后一层从左到右连续排列节点。

        Root
       /    \
   Node1   Node2
   /   \   /
  N3   N4 N5

这五种形态展示了二叉树的不同可能结构，二叉树的特性使它广泛应用于算法设计、数据存储等场景中。

完全二叉树相关概念

完全二叉树（Complete Binary Tree） 是一种特殊的二叉树，它具有以下特性：

完全二叉树的定义：

1. 层次填满： 对于一个完全二叉树，除了最后一层外，所有的层都是满的，也就是每一层都包含最大的可能节点数。
2. 最后一层从左至右填充： 在最后一层中，所有的节点都靠左排列，最后一层的节点从左到右依次填充，没有空隙。

相关概念

1. 高度（Height）：

• 完全二叉树的高度 h 是从根节点到最深层叶子节点的路径长度。完全二叉树的高度可以通过层数来衡量，每增加一层，树的高度加1。

2. 节点数量（Number of Nodes）：

• 对于一个高度为 h 的完全二叉树，总节点数 (N) 满足：
  

• 公式解释：

  • 最少节点数：当最后一层只有一个节点时，总节点数为 (2^h)。
  • 最多节点数：当最后一层节点全部填满时，总节点数为 (2^{h+1} - 1)。

3. 满二叉树（Full Binary Tree）与完全二叉树的关系：

• 满二叉树是完全二叉树的一种特例，当完全二叉树的所有层都完全填满，即最后一层没有剩余空间时，这棵树就是满二叉树。因此，所有的满二叉树都是完全二叉树，但并不是所有完全二叉树都是满二叉树。

4. 完全二叉树的性质：

• 父子节点的关系：

  • 若父节点的索引为 i，则其左子节点的索引为 2i + 1，右子节点的索引为 2i + 2。
  • 反过来，若某节点的索引为 i，其父节点的索引为
    。

• 节点数量的分布：

  • 在完全二叉树中，节点数较多的树通常比节点数较少的树更短，意味着更平衡，从而提高了树的时间复杂度效率，例如用于**堆（Heap）**的实现。

6. 存储结构：

• 完全二叉树可以使用数组存储，而不需要指针来连接节点。树的节点可以依次从左到右按层级顺序存储，父子节点的索引关系简单易计算，且不需要浪费额外空间。

完全二叉树的例子

一个高度为 h = 3 的完全二叉树示意图：

        1
       / \
      2   3
     / \  /
    4   5 6

在这个示例中，树的所有层都满了，除了最后一层，最后一层的节点从左到右排列。

二叉树的存储方式

二叉树的存储方式主要有两种：链式存储和顺序存储。这两种存储方式在不同的应用场景下各有优缺点。

1. 链式存储

链式存储是用指针和节点来存储二叉树的结构。每个节点包含三个字段：一个存储数据的字段和两个指向子节点的指针字段，分别指向左子节点和右子节点。

链式存储结构的特点：

• 每个节点的结构可以定义为：

  struct TreeNode {
      int data;             // 数据域
      struct TreeNode* left;  // 左子节点指针
      struct TreeNode* right; // 右子节点指针
  };
  

• 通过指针，可以直接找到某节点的左右子节点，即每个节点动态分配内存，根据需要构建整个二叉树。
• 根节点通常作为指针指向树的入口点。

优点：

1. 灵活性高：可以动态分配内存，适应不同形状的二叉树。
2. 无浪费空间：节点只为存在的节点分配存储空间，没有节点不需要存储空间。
3. 支持不规则树形结构：适合用于深度不规则、动态结构变化的二叉树。

缺点：

1. 存储空间利用率低：每个节点除了存储数据，还要存储两个指针，增加了存储开销。
2. 随机访问困难：无法直接通过索引定位节点，必须通过指针逐级遍历节点。

链式存储的二叉树图示：

       1
      / \
     2   3
    / \   \
   4   5   6

每个节点都通过左右子指针指向其相应的子节点。

2. 顺序存储

顺序存储使用数组来存储二叉树。它通常适用于完全二叉树或接近完全的二叉树，因为这种树的结构具有较少的空节点，可以通过数组有效存储。顺序存储会将树的节点按层次遍历的顺序存储在数组中。

顺序存储结构的特点：

• 将二叉树的节点按照层次遍历依次放入数组中。
• 对于数组中索引为 i 的节点：
  • 左子节点的索引为 2i + 1。
  • 右子节点的索引为 2i + 2。
  • 父节点的索引为
    。
• 根节点放在数组的第0位。

优点：

1. 快速定位：可以直接通过索引访问任意节点，定位子节点和父节点的关系非常简单。
2. 存储紧凑：对于完全二叉树或接近完全二叉树，空间利用率较高。
3. 实现方便：只需使用一个数组，无需使用指针来表示结构。

缺点：

1. 浪费空间：如果二叉树不是完全二叉树，树中的空节点也要占据数组中的位置，造成空间浪费。
2. 不适合不规则树：对不规则的、深度较大的二叉树，数组的存储空间利用效率不高。
3. 难以调整树形：插入和删除操作较复杂，重新平衡树形困难。

顺序存储的二叉树图示：

假设我们有一个如下的二叉树：

       1
      / \
     2   3
    / \   \
   4   5   6

它在数组中的存储为：

索引：  0   1   2   3   4   5   6
节点： [1,  2,  3,  4,  5,  -,  6]

• 节点 1 的左子节点是 2，右子节点是 3。
• 节点 2 的左子节点是 4，右子节点是 5。
• 节点 3 只有右子节点 6，因此数组索引5位置为空。

总结

• 链式存储更适合不规则的、动态变化的二叉树结构，操作灵活，但需要额外的指针存储空间，访问速度较慢。
• 顺序存储适用于完全二叉树，结构简单，存储紧凑，便于随机访问节点，但不适合稀疏或不规则的树，可能浪费大量空间。

使用数组实现完全二叉树

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100 // 数组的最大大小

typedef struct {
    int* arr;
    int size;
} BinaryTree;

// 初始化完全二叉树
BinaryTree* initTree() {
    BinaryTree* tree = (BinaryTree*)malloc(sizeof(BinaryTree));
    tree->arr = (int*)malloc(sizeof(int) * MAX_SIZE);
    tree->size = 0;
    return tree;
}

// 插入元素到完全二叉树
void insert(BinaryTree* tree, int value) {
    if (tree->size >= MAX_SIZE) {
        printf("树已满，无法插入元素！\n");
        return;
    }
    tree->arr[tree->size] = value;
    tree->size++;
}

// 获取父节点
int getParent(BinaryTree* tree, int index) {
    if (index <= 0 || index >= tree->size) {
        printf("索引无效或根节点没有父节点！\n");
        return -1;
    }
    return tree->arr[(index - 1) / 2];
}

// 获取左子节点
int getLeftChild(BinaryTree* tree, int index) {
    int leftIndex = 2 * index + 1;
    if (leftIndex >= tree->size) {
        printf("该节点没有左子节点！\n");
        return -1;
    }
    return tree->arr[leftIndex];
}

// 获取右子节点
int getRightChild(BinaryTree* tree, int index) {
    int rightIndex = 2 * index + 2;
    if (rightIndex >= tree->size) {
        printf("该节点没有右子节点！\n");
        return -1;
    }
    return tree->arr[rightIndex];
}

// 删除树中的最后一个节点
void deleteLast(BinaryTree* tree) {
    if (tree->size == 0) {
        printf("树为空，无法删除！\n");
        return;
    }
    tree->size--;
}

// 查找元素
int findElement(BinaryTree* tree, int value) {
    for (int i = 0; i < tree->size; i++) {
        if (tree->arr[i] == value) {
            return i;
        }
    }
    return -1;
}

// 打印树
void printTree(BinaryTree* tree) {
    printf("当前树中的元素: ");
    for (int i = 0; i < tree->size; i++) {
        printf("%d ", tree->arr[i]);
    }
    printf("\n");
}

// 释放树内存
void freeTree(BinaryTree* tree) {
    free(tree->arr);
    free(tree);
}

int main() {
    BinaryTree* tree = initTree();

    insert(tree, 10);
    insert(tree, 20);
    insert(tree, 30);
    insert(tree, 40);
    insert(tree, 50);

    printTree(tree);

    printf("根节点的左子节点: %d\n", getLeftChild(tree, 0));
    printf("根节点的右子节点: %d\n", getRightChild(tree, 0));
    printf("索引 1 的父节点: %d\n", getParent(tree, 1));

    printf("删除最后一个节点。\n");
    deleteLast(tree);
    printTree(tree);

    freeTree(tree);
    return 0;
}

二叉树的遍历

层次遍历

二叉树的层次遍历（也叫广度优先遍历，Breadth-First Search，BFS）是按照每一层从左到右的顺序依次访问每个节点。在层次遍历中，首先访问根节点，然后访问根节点的所有直接子节点，接着访问这些子节点的子节点，以此类推，直到所有节点都被访问。

层次遍历常用队列（Queue）来辅助实现，因为队列遵循先进先出（FIFO）的特点，可以很好地实现按层访问的顺序。

层次遍历过程

假设我们有如下二叉树：

        1
       / \
      2   3
     / \   \
    4   5   6

步骤：

1. 初始化队列，将根节点（1）入队。
2. 从队列中取出一个节点（出队），访问该节点，然后将它的左、右子节点（如果有）依次入队。
3. 重复第2步，直到队列为空。

层次遍历的顺序为：

• 第一步：根节点 1 入队，访问 1，将其子节点 2 和 3 入队。
• 第二步：节点 2 出队，访问 2，将其子节点 4 和 5 入队。
• 第三步：节点 3 出队，访问 3，将其子节点 6 入队。
• 第四步：节点 4 出队，访问 4。
• 第五步：节点 5 出队，访问 5。
• 第六步：节点 6 出队，访问 6。

最终的访问顺序是：1, 2, 3, 4, 5, 6。

层次遍历的代码实现（C语言）

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构体
typedef struct Node {
    int data;
    struct Node *left, *right;
} Node;

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 层次遍历使用队列
typedef struct Queue {
    int front, rear;
    int size;
    Node** array;
} Queue;

// 创建队列
Queue* createQueue(int size) {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = queue->rear = -1;
    queue->size = size;
    queue->array = (Node**)malloc(queue->size * sizeof(Node*));
    return queue;
}

// 检查队列是否为空
int isEmpty(Queue* queue) {
    return queue->front == -1;
}

// 入队操作
void enqueue(Queue* queue, Node* node) {
    if (queue->rear == queue->size - 1)
        return; // 队列已满
    if (queue->front == -1)
        queue->front = 0;
    queue->array[++queue->rear] = node;
}

// 出队操作
Node* dequeue(Queue* queue) {
    if (isEmpty(queue))
        return NULL;
    Node* node = queue->array[queue->front];
    if (queue->front >= queue->rear) {
        queue->front = queue->rear = -1;
    } else {
        queue->front++;
    }
    return node;
}

// 层次遍历函数
void levelOrderTraversal(Node* root) {
    if (root == NULL)
        return;

    // 创建队列并初始化
    Queue* queue = createQueue(100);
    enqueue(queue, root);

    while (!isEmpty(queue)) {
        Node* currentNode = dequeue(queue);
        printf("%d ", currentNode->data);

        // 将左子节点入队
        if (currentNode->left != NULL)
            enqueue(queue, currentNode->left);

        // 将右子节点入队
        if (currentNode->right != NULL)
            enqueue(queue, currentNode->right);
    }

    free(queue->array);
    free(queue);
}

// 主函数
int main() {
    Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->right = createNode(6);

    printf("层次遍历结果: ");
    levelOrderTraversal(root);
    printf("\n");

    return 0;
}

输出

层次遍历结果: 1 2 3 4 5 6 

过程解释：

1. 创建树：首先使用 createNode 函数来构建树的结构。根节点为 1，其左子节点为 2，右子节点为 3，依次建立二叉树。
2. 队列辅助遍历：通过自定义的 Queue 结构体来存储每层的节点。将根节点入队，然后按顺序访问每个节点，同时将每个节点的左右子节点入队。
3. 输出遍历结果：每次从队列中出队时，访问当前节点并打印其值。

流程图

下面用层次遍历的过程表示这个二叉树（每个括号内代表节点被访问的顺序）：

        (1)
       /   \
     (2)   (3)
     / \      \
   (4) (5)    (6)

每一层被依次访问：

• 第1层：访问 1
• 第2层：访问 2 和 3
• 第3层：访问 4, 5 和 6

通过使用队列，按照从左到右、从上到下的顺序完成了层次遍历。

前序遍历、中序遍历和后序遍历

在二叉树中，前序遍历、中序遍历和后序遍历是最常见的三种遍历方法。它们都属于深度优先遍历（DFS）的范畴，每种方法都根据访问节点的顺序有所不同。

1. 前序遍历（Preorder Traversal）

前序遍历的顺序是：访问根节点 → 遍历左子树 → 遍历右子树。

过程：

1. 访问根节点。
2. 递归地进行前序遍历左子树。
3. 递归地进行前序遍历右子树。

例子：
对于如下二叉树：

        A
       / \
      B   C
     / \
    D   E

前序遍历的过程：

1. 访问根节点 A。
2. 递归遍历左子树 B：
   • 访问节点 B。
   • 递归遍历左子树 D：访问 D。
   • 递归遍历右子树 E：访问 E。
3. 递归遍历右子树 C：访问 C。

前序遍历的结果：A, B, D, E, C

2. 中序遍历（Inorder Traversal）

中序遍历的顺序是：遍历左子树 → 访问根节点 → 遍历右子树。

过程：

1. 递归地进行中序遍历左子树。
2. 访问根节点。
3. 递归地进行中序遍历右子树。

例子：
对于如下二叉树：

        A
       / \
      B   C
     / \
    D   E

中序遍历的过程：

1. 递归遍历左子树 B：
   • 递归遍历左子树 D：访问 D。
   • 访问节点 B。
   • 递归遍历右子树 E：访问 E。
2. 访问根节点 A。
3. 递归遍历右子树 C：访问 C。

中序遍历的结果：D, B, E, A, C

3. 后序遍历（Postorder Traversal）

后序遍历的顺序是：遍历左子树 → 遍历右子树 → 访问根节点。

过程：

1. 递归地进行后序遍历左子树。
2. 递归地进行后序遍历右子树。
3. 访问根节点。

例子：
对于如下二叉树：

        A
       / \
      B   C
     / \
    D   E

后序遍历的过程：

1. 递归遍历左子树 B：
   • 递归遍历左子树 D：访问 D。
   • 递归遍历右子树 E：访问 E。
   • 访问节点 B。
2. 递归遍历右子树 C：访问 C。
3. 访问根节点 A。

后序遍历的结果：D, E, B, C, A

总结

• 前序遍历：根节点 → 左子树 → 右子树
• 中序遍历：左子树 → 根节点 → 右子树
• 后序遍历：左子树 → 右子树 → 根节点

这些遍历方式可以用于不同的应用场景，例如构造树的表达式、计算树的高度等。

根据两个遍历方式求另一个

给定二叉树的两个遍历方式（前序遍历、中序遍历、后序遍历中的任意两个），可以唯一确定二叉树，并推导出第三种遍历方式。以下是如何从已知的两个遍历方式中推导出第三种遍历方式的详细介绍。

遍历方式简介

1. 前序遍历（Preorder Traversal）：根节点 → 左子树 → 右子树
2. 中序遍历（Inorder Traversal）：左子树 → 根节点 → 右子树
3. 后序遍历（Postorder Traversal）：左子树 → 右子树 → 根节点

通过两个遍历方式推导第三种遍历方式

1. 已知前序遍历和中序遍历，求后序遍历

步骤：

1. 确定根节点：

   • 前序遍历的第一个节点是根节点。
   • 在中序遍历中找到根节点的位置，根节点的左边部分是左子树，右边部分是右子树。

2. 分割左右子树：

   • 根据中序遍历将树分成左子树和右子树。
   • 使用前序遍历中的节点分配到相应的子树中。

3. 递归处理：

   • 递归地对左子树和右子树执行相同的步骤，直到树遍历完全。

4. 生成后序遍历：

   • 先遍历左子树，再遍历右子树，最后访问根节点。

示例：

• 前序遍历：A B D E C F
• 中序遍历：D B E A F C

过程：

• 根节点是 A（前序遍历的第一个节点）。
• 在中序遍历中，A 的左子树是 D B E，右子树是 F C。
• 对左子树 D B E：
  • 前序遍历为 B D E，根节点为 B。
  • 中序遍历为 D B E，左子树是 D，右子树是 E。
  • 生成后序遍历 D E B。
• 对右子树 F C：
  • 前序遍历为 C F，根节点为 C。
  • 中序遍历为 F C，左子树是 F。
  • 生成后序遍历 F C。

最终后序遍历：D E B F C A

2. 已知前序遍历和后序遍历，求中序遍历

步骤：

1. 确定根节点：

   • 前序遍历的第一个节点是根节点。

2. 分割左右子树：

   • 在后序遍历的倒数第二个位置找到根节点，左子树在根节点前面的部分，右子树在根节点后的部分。

3. 递归处理：

   • 递归地对左子树和右子树执行相同的步骤。

4. 生成中序遍历：

   • 中序遍历的顺序是先遍历左子树，再访问根节点，最后遍历右子树。

示例：

• 前序遍历：A B D E C
• 后序遍历：D E B C A

过程：

• 根节点是 A（前序遍历的第一个节点）。
• 在后序遍历中，A 的左子树是 D E B，右子树是 C。
• 对左子树 D E B：
  • 前序遍历为 B D E，根节点为 B。
  • 后序遍历为 D E B，左子树是 D，右子树是 E。
  • 生成中序遍历 D B E。
• 对右子树 C：
  • 前序遍历为 C，后序遍历为 C。
  • 生成中序遍历 C。

最终中序遍历：D B E A C

3. 已知中序遍历和后序遍历，求前序遍历

步骤：

1. 确定根节点：

   • 后序遍历的最后一个节点是根节点。

2. 分割左右子树：

   • 在中序遍历中找到根节点的位置，根节点的左边部分是左子树，右边部分是右子树。

3. 递归处理：

   • 递归地对左子树和右子树执行相同的步骤。

4. 生成前序遍历：

   • 前序遍历的顺序是先访问根节点，再遍历左子树，最后遍历右子树。

示例：

• 中序遍历：D B E A F C
• 后序遍历：D E B F C A

过程：

• 根节点是 A（后序遍历的最后一个节点）。
• 在中序遍历中，A 的左子树是 D B E，右子树是 F C。
• 对左子树 D B E：
  • 后序遍历为 D E B，根节点为 B。
  • 中序遍历为 D B E，左子树是 D，右子树是 E。
  • 生成前序遍历 B D E。
• 对右子树 F C：
  • 后序遍历为 F C，根节点为 C。
  • 中序遍历为 F C，左子树是 F。
  • 生成前序遍历 C F。

最终前序遍历：A B D E C F

总结

• 前序遍历 + 中序遍历: 生成后序遍历。
• 前序遍历 + 后序遍历: 生成中序遍历。
• 中序遍历 + 后序遍历: 生成前序遍历。

这些方法利用了不同遍历方式中的节点顺序信息和结构来恢复二叉树的整体结构，并推导出其他遍历方式。

总结

树状结构，尤其是二叉树，作为算法基础中的重要组成部分，具备灵活的表现形式和广泛的应用场景。从基础的遍历方式到更为复杂的操作和应用，二叉树在解决实际问题中起到了至关重要的作用。通过深入理解二叉树的基本性质与常见操作，能够为更高效的数据处理、搜索算法提供坚实的基础。在CSP-J竞赛和其他算法挑战中，树状结构的掌握不仅仅是应对考试的需要，更是提高编程能力和算法思维的有效途径。