5.1 树的基本概念

5.1.1 树的定义

• 一棵树是结点的有限集合T：
  • 若T非空，则：
    • 有一个特别标出的结点，称作该树的根，记为root(T)；
    • 其余结点分成若干个不相交的非空集合T1, T2, …, Tm (m>0)，其中T1, T2, …, Tm又都是树，称作root(T)的子树。
  • T 空时为空树，记作root(T)=NULL。

5.1.2 森林的定义

  一个森林是0棵或多棵不相交（非空）树的集合，通常是一个有序的集合。换句话说，森林由多个树组成，这些树之间没有交集，且可以按照一定的次序排列。在森林中，每棵树都是独立的，具有根节点和子树，树与树之间没有直接的连接关系。
  森林是树的扩展概念，它是由多个树组成的集合。在计算机科学中，森林也被广泛应用于数据结构和算法设计中，特别是在图论和网络分析等领域。

5.1.3 树的术语

• 父亲（parent）、儿子（child）、兄弟（sibling）、后裔（descendant）、祖先（ancestor）
• 度（degree）、叶子节点（leaf node）、分支节点（internal node）
• 结点的层数
• 路径、路径长度、结点的深度、树的深度

参照前文：【数据结构】树与二叉树（一）：树（森林）的基本概念：父亲、儿子、兄弟、后裔、祖先、度、叶子结点、分支结点、结点的层数、路径、路径长度、结点的深度、树的深度

5.1.4 树的表示

• 【数据结构】树与二叉树（二）：树的表示C语言：树形表示法、嵌套集合表示法、嵌套括号表示法 、凹入表示法

5.2 二叉树

5.2.1 二叉树

1. 定义

  二叉树是一种常见的树状数据结构，它由结点的有限集合组成。一个二叉树要么是空集，被称为空二叉树，要么由一个根结点和两棵不相交的子树组成，分别称为左子树和右子树。每个结点最多有两个子结点，分别称为左子结点和右子结点。

2. 特点

  二叉树的特点是每个结点最多有两个子结点，并且子结点的位置是有序的，即左子结点在前，右子结点在后。这种有序性使得二叉树在搜索、排序等算法中有广泛的应用。

• 在二叉树中，根结点是整个树的起始点，通过根结点可以访问到整个树的其他结点。每个结点都可以看作是一个独立的二叉树，它的左子树和右子树也是二叉树。

• 二叉树可以是空树，也可以是只有根结点的树，或者是由多个结点组成的树。每个结点可以包含一个数据元素，以及指向左子结点和右子结点的指针。

• 二叉树的形状可以各不相同，它可以是平衡的或者不平衡的，具体取决于结点的分布情况。在二叉树中，每个结点的左子树和右子树都是二叉树，因此可以通过递归的方式来处理二叉树的操作。

3. 性质

引理5.1：二叉树中层数为i的结点至多有$2^i$个，其中$i\ge 0$。

引理5.2：高度为k的二叉树中至多有$2^{k+1}-1$个结点，其中$k\ge 0$。

引理5.3：设T是由n个结点构成的二叉树，其中叶结点个数为$n_0$，度数为2的结点个数为$n_2$，则有$n_0=n_2+1$。

• 详细证明过程见前文：【数据结构】树与二叉树（三）：二叉树的定义、特点、性质及相关证明

4. 满二叉树

  定义5.3：一棵非空高度为$k(k\ge 0)$的满二叉树(perfect binary tree)，是有$2^{k+1}-1$个结点的二叉树。

5. 完全二叉树

  定义5.4：一棵包含$n$个节点、高度为$k$的二叉树$T$，当按层次顺序编号$T$的所有节点，对应于一棵高度为$k$的满二叉树中编号由1至$n$的那些节点时，$T$被称为完全二叉树（complete binary tree）。

• 满二叉树、完全二叉树性质及证明：【数据结构】树与二叉树（四）：满二叉树、完全二叉树及其性质

5.2.2 二叉树顺序存储

  二叉树的顺序存储是指将二叉树中所有结点按层次顺序存放在一块地址连续的存储空间中
  对于完全二叉树，结点的层次顺序反映了其结构，可按层次顺序给出一棵完全二叉树之结点的编号，事实上，这就是完全二叉树的顺序存储方法，结点编号恰好反映了结点间的逻辑关系。
  只要对完全二叉树之结点按照层次顺序进行编号，就可利用一维数组$A$来存储一棵含有$n$个结点的完全二叉树，其中A[1]存储二叉树的根结点，A[i]存储二叉树中编号为i的结点，并且结点A[i]的左儿子（若存在）存放在A[2i]处，而A[i]的右儿子（若存在）存放在A[2i+1]处。注意，这里我们约定数组索引从1开始，而不是从0开始，在使用数组存储完全二叉树时，需要留出A[0]位置不使用。

典例

  首先，我们按照完全二叉树的结点顺序进行编号，从上到下、从左到右依次编号。根据给出的完全二叉树，我们可以得到以下结点编号：

         1
        / \
       2   3
      / \
     4   5

  接下来，我们可以利用一维数组来存储这棵完全二叉树。创建一个大小为6的数组A，其中A[1]表示根结点$A$，A[2]表示结点$B$，A[3]表示结点$E$，A[4]表示结点$C$，A[5]表示结点$D$。

索引：  1   2   3   4   5
数组： [ A,  B,  E,  C,  D ]

  根据完全二叉树的性质，结点$A$的左儿子应该存放在A[2]的位置，右儿子应该存放在A[3]的位置。结点$B$的左儿子应该存放在A[4]的位置，右儿子应该存放在A[5]的位置。

例题

  画出下面这棵完全二叉树的顺序存储结构：

$$答案见文末$$

  完全二叉树的顺序存储方式是一种简单且节省空间的存储方式。它只需要使用一个一维数组来存储完全二叉树的结点信息域的值，而不需要额外的空间来存储左儿子和右儿子的地址。

  通过计算结点的编号和数组索引之间的关系，我们可以方便地找到结点的左儿子、右儿子和父亲结点。例如，对于结点i，它的左儿子的编号是2i，右儿子的编号是2i+1，父亲结点的编号是⌊i/2⌋。这种计算关系使得寻找子孙结点和祖先结点变得非常方便和高效。

  顺序存储方式的优点是节省了存储空间，同时访问结点也非常快速，因为可以通过数组索引直接访问结点，而不需要进行指针的跳转。然而，顺序存储方式也有一些限制。由于使用数组存储，需要提前确定完全二叉树的最大结点个数，因此对于结点数不确定或者动态变化的情况下，顺序存储方式可能不适用。

C语言实现

  注意，这里我们约定数组索引从0开始，节点位置计算公式与前文略有不同。

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

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

// 二叉树的顺序存储结构
typedef struct {
    char data[MAX_SIZE];  // 数组用于存储结点的数据
    int size;  // 二叉树的大小（结点个数）
} BinaryTree;

// 初始化二叉树
void initBinaryTree(BinaryTree* tree) {
    tree->size = 0;
}

// 向二叉树中插入结点
void insertNode(BinaryTree* tree, int value, int index) {
    if (tree->size >= MAX_SIZE) {
        printf("Binary tree is full. Cannot insert more nodes.\n");
        return;
    }

    if (index < 0 || index > tree->size) {
        printf("Invalid index.\n");
        return;
    }

    // 将插入位置后的结点后移
    for (int i = tree->size - 1; i >= index; i--) {
        tree->data[i + 1] = tree->data[i];
    }

    // 插入新结点
    tree->data[index] = value;
    tree->size++;
}

// 获取结点的父节点编号
int getParentIndex(int index) {
    return (index - 1) / 2;
}

// 获取结点的左子节点编号
int getLeftChildIndex(int index) {
    return 2 * index + 1;
}

// 获取结点的右子节点编号
int getRightChildIndex(int index) {
    return 2 * index + 2;
}

// 根据索引获取结点的值
char getNodeValue(BinaryTree* tree, int index) {
    if (index >= tree->size || index < 0) {
        printf("Invalid index.\n");
        return -1;
    }

    return tree->data[index];
}

int main() {
    BinaryTree tree;
    initBinaryTree(&tree);

    // 向二叉树中插入结点
    insertNode(&tree, 'A', 0);  
    insertNode(&tree, 'B', 1);  
    insertNode(&tree, 'E', 2); 
    insertNode(&tree, 'C', 3); 
    insertNode(&tree, 'D', 4); 

    // 获取结点的值和子节点的值
    char rootValue = getNodeValue(&tree, 0);
    char leftChildValue = getNodeValue(&tree, getLeftChildIndex(0));
    char rightChildValue = getNodeValue(&tree, getRightChildIndex(0));

    printf("Root value: %c\n", rootValue);
    printf("Left child of Root: %c\n", leftChildValue);
    printf("Right child of Root: %c\n", rightChildValue);

    printf("the Parent of B: %c\n", getNodeValue(&tree, getParentIndex(1)));
    printf("the Parent of C: %c\n", getNodeValue(&tree, getParentIndex(3)));
    printf("the Parent of D: %c\n", getNodeValue(&tree, getParentIndex(4)));
    printf("the Parent of E: %c\n", getNodeValue(&tree, getParentIndex(2)));
    return 0;
}

答案