在数据结构的世界里，树是一种非常重要的非线性结构，它相较于线性结构（如数组、链表）能更高效地解决许多实际问题。本文将以 C 语言为载体，带你逐步揭开树的神秘面纱，从基本概念到具体实现，深入浅出地掌握树这种数据结构。

一、树的基本概念

1.1 树的定义

树是由 n（n≥0）个有限节点组成的具有层次关系的集合。当 n=0 时，称为空树；当 n>0 时，有且仅有一个特定的节点称为根节点，其余节点可分为 m（m≥0）个互不相交的有限集，每个集合本身又是一棵树，称为根的子树。

这种结构类似于自然界中的树，根在上，枝叶在下，呈现出明显的层次关系。树的非线性体现在节点之间的关系不是一一对应的，一个节点可以与多个节点相关联。

1.2 树的基本术语

节点：树中的每个元素都称为节点，节点包含数据信息和指向其他节点的指针（在链式存储中）。

根节点：树中没有前驱的节点，一棵树有且仅有一个根节点（空树除外）。

父节点与子节点：若一个节点含有子树，则这个节点称为其子树的根节点的父节点；相应地，子树的根节点称为该节点的子节点。

兄弟节点：具有相同父节点的节点互称为兄弟节点。

叶子节点：没有子节点的节点称为叶子节点，也叫终端节点。

分支节点：非叶子节点称为分支节点，也叫非终端节点。

节点的度：节点拥有的子节点个数称为节点的度。叶子节点的度为 0。

树的度：树中所有节点的度的最大值称为树的度。

层次：从根节点开始，根节点为第 1 层，根的子节点为第 2 层，以此类推。

深度：树中节点的最大层次称为树的深度（或高度）。

森林：由 m（m≥0）棵互不相交的树组成的集合称为森林。

这些术语是理解树结构的基础，在后续学习中会频繁出现，需要熟练掌握。

二、二叉树

2.1 二叉树的定义

二叉树是一种特殊的树，它的每个节点最多有两棵子树，即每个节点的度不超过 2。二叉树的子树有左右之分，分别称为左子树和右子树，次序不能随意颠倒，因此二叉树是有序树。

二叉树有五种基本形态：

空二叉树

只有根节点

根节点只有左子树

根节点只有右子树

根节点既有左子树又有右子树

2.2 二叉树的性质

性质 1：在二叉树的第 i 层上，最多有 2^(i-1) 个节点（i≥1）。

例如，第 1 层最多 1 个节点（2^0），第 2 层最多 2 个节点（2^1），第 3 层最多 4 个节点（2^2），以此类推。

性质 2：深度为 k 的二叉树最多有 2^k - 1 个节点（k≥1）。

这是因为深度为 k 的二叉树，每层节点数都达到最大值时，总节点数为 2^0 + 2^1 + ... + 2^(k-1) = 2^k - 1。

性质 3：对任何一棵二叉树，若叶子节点数为 n0，度为 2 的节点数为 n2，则 n0 = n2 + 1。

证明：设度为 1 的节点数为 n1，总节点数 N = n0 + n1 + n2。同时，除根节点外，每个节点都有一个前驱，所以总边数为 N - 1。而总边数也等于 n1 + 2n2（度为 1 的节点贡献 1 条边，度为 2 的节点贡献 2 条边）。因此 N - 1 = n1 + 2n2，将 N 代入可得 n0 = n2 + 1。

2.3 特殊的二叉树

满二叉树：深度为 k 且有 2^k - 1 个节点的二叉树。满二叉树的每一层都充满了节点，叶子节点都在最底层。

完全二叉树：深度为 k，有 n 个节点的二叉树，当且仅当其中的节点与深度为 k 的满二叉树中编号从 1 到 n 的节点一一对应时，称为完全二叉树。

完全二叉树的特点是：叶子节点只可能在最后两层出现；最后一层的叶子节点都靠左排列；除最后一层外，其他层的节点数都达到最大值。

完全二叉树具有一个重要性质：对于具有 n 个节点的完全二叉树，若对节点按层序编号（从 1 开始），则对任意节点 i（1≤i≤n）有：

若 i=1，则节点 i 是根节点，无父节点；

若 i>1，则其父节点编号为 i/2（向下取整）；

若 2i≤n，则其左子节点编号为 2i；

若 2i+1≤n，则其右子节点编号为 2i+1。

三、二叉树的存储结构

3.1 顺序存储结构

顺序存储结构适用于完全二叉树，它利用数组来存储二叉树的节点，根据完全二叉树的性质，通过数组下标就能确定节点之间的父子关系。

顺序存储的实现：

#define MAXSIZE 100
typedef int TElemType;
TElemType tree[MAXSIZE];
int n; // 节点个数

对于非完全二叉树，使用顺序存储会浪费大量存储空间，因为需要用空节点填补空缺位置以保持编号的对应关系。

3.2 链式存储结构

链式存储是二叉树最常用的存储方式，每个节点包含数据域和两个指针域，分别指向左子节点和右子节点，这种结构称为二叉链表。

二叉链表节点的定义：

typedef int TElemType;
typedef struct BiTNode {
TElemType data; // 数据域
    struct BiTNode lchild, rchild; // 左、右子节点指针
} BiTNode, *BiTree;

有时为了方便查找父节点，会增加一个指向父节点的指针域，形成三叉链表，但二叉链表已能满足大部分操作需求。

四、二叉树的基本操作

4.1 创建二叉树

创建二叉树的方法有多种，这里介绍按前序遍历序列创建二叉树的方法（约定输入数据中用特定值表示空节点，如 - 1）。

// 按前序遍历创建二叉树
void CreateBiTree(BiTree *T) {
TElemType ch;
scanf("%d", &ch);
if (ch == -1) { // 空节点
        *T = NULL;
    } else {
        T = (BiTNode )malloc(sizeof(BiTNode));
if (!*T) {
exit(OVERFLOW); // 内存分配失败
        }
        (*T)->data = ch; // 根节点数据
CreateBiTree(&(*T)->lchild); // 创建左子树
CreateBiTree(&(*T)->rchild); // 创建右子树
    }
}

4.2 二叉树的遍历

遍历是指按某种次序访问树中的所有节点，使每个节点被访问一次且仅被访问一次。二叉树的遍历主要有四种方式：

4.2.1 前序遍历

前序遍历的顺序是：根节点 -> 左子树 -> 右子树（根左右）。

递归实现：

// 前序遍历
void PreOrderTraverse(BiTree T) {
if (T == NULL) {
return;
    }
printf("%d ", T->data); // 访问根节点
PreOrderTraverse(T->lchild); // 遍历左子树
PreOrderTraverse(T->rchild); // 遍历右子树
}

非递归实现（借助栈）：

void PreOrderTraverseNonRecursive(BiTree T) {
BiTree stack[MAXSIZE];
    int top = -1;
BiTree p = T;
while (p != NULL || top != -1) {
while (p != NULL) {
printf("%d ", p->data); // 访问根节点
            stack[++top] = p; // 入栈
            p = p->lchild; // 遍历左子树
       }
if (top != -1) {
            p = stack[top--]; // 出栈
            p = p->rchild; // 遍历右子树
        }
    }
}

4.2.2 中序遍历

中序遍历的顺序是：左子树 -> 根节点 -> 右子树（左根右）。

递归实现：

// 中序遍历
void InOrderTraverse(BiTree T) {
if (T == NULL) {
return;
    }
InOrderTraverse(T->lchild); // 遍历左子树
printf("%d ", T->data); // 访问根节点
InOrderTraverse(T->rchild); // 遍历右子树
}

非递归实现：

void InOrderTraverseNonRecursive(BiTree T) {
BiTree stack[MAXSIZE];
    int top = -1;
BiTree p = T;
while (p != NULL || top != -1) {
while (p != NULL) {
            stack[++top] = p; // 入栈
            p = p->lchild; // 遍历左子树
        }
if (top != -1) {
            p = stack[top--]; // 出栈
printf("%d ", p->data); // 访问根节点
            p = p->rchild; // 遍历右子树
        }
    }
}

4.2.3 后序遍历

后序遍历的顺序是：左子树 -> 右子树 -> 根节点（左右根）。

递归实现：

// 后序遍历
void PostOrderTraverse(BiTree T) {
if (T == NULL) {
return;
    }
PostOrderTraverse(T->lchild); // 遍历左子树
PostOrderTraverse(T->rchild); // 遍历右子树
printf("%d ", T->data); // 访问根节点
}

非递归实现（相对复杂，需要标记节点是否被访问过）：

void PostOrderTraverseNonRecursive(BiTree T) {
BiTree stack[MAXSIZE];
    int top = -1;
BiTree p = T;
BiTree lastVisit = NULL; // 记录最后访问的节点
while (p != NULL || top != -1) {
while (p != NULL) {
            stack[++top] = p;
            p = p->lchild;
        }
        p = stack[top]; // 获取栈顶节点
// 若右子树为空或已被访问，则访问当前节点
if (p->rchild  NULL || p->rchild  lastVisit) {
printf("%d ", p->data);
            top--;
            lastVisit = p;
            p = NULL;
        } else {
            p = p->rchild;
        }
    }
}

4.2.4 层序遍历

层序遍历是按层次顺序（从根节点开始，逐层从左到右）访问节点，需要借助队列实现。

// 层序遍历
void LevelOrderTraverse(BiTree T) {
if (T == NULL) {
return;
    }
BiTree queue[MAXSIZE];
    int front = 0, rear = 0;
    queue[rear++] = T; // 根节点入队
while (front != rear) {
BiTree p = queue[front++]; // 出队
printf("%d ", p->data); // 访问节点
if (p->lchild != NULL) {
            queue[rear++] = p->lchild; // 左子节点入队
        }
if (p->rchild != NULL) {
            queue[rear++] = p->rchild; // 右子节点入队
        }
    }
}

4.3 求二叉树的深度

// 求二叉树的深度
int BiTreeDepth(BiTree T) {
if (T == NULL) {
return 0;
    }
    int leftDepth = BiTreeDepth(T->lchild);
    int rightDepth = BiTreeDepth(T->rchild);
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}

4.4 求二叉树的节点个数

// 求二叉树的节点个数
int BiTreeNodeCount(BiTree T) {
if (T == NULL) {
return 0;
    }
return BiTreeNodeCount(T->lchild) + BiTreeNodeCount(T->rchild) + 1;
}

4.5 求叶子节点个数

// 求叶子节点个数
int LeafNodeCount(BiTree T) {
if (T == NULL) {
return 0;
    }
if (T->lchild  NULL && T->rchild  NULL) {
return 1; // 叶子节点
    }
return LeafNodeCount(T->lchild) + LeafNodeCount(T->rchild);
}

五、二叉搜索树（BST）

5.1 二叉搜索树的定义

二叉搜索树是一种特殊的二叉树，它或者是一棵空树，或者具有以下性质：

若左子树不为空，则左子树上所有节点的值均小于根节点的值；

若右子树不为空，则右子树上所有节点的值均大于根节点的值；

左、右子树也分别为二叉搜索树。

二叉搜索树的特点是可以高效地进行查找、插入和删除操作，平均时间复杂度为 O (log n)。

5.2 二叉搜索树的查找

// 查找值为key的节点
BiTree SearchBST(BiTree T, TElemType key) {
if (T  NULL || T->data  key) {
return T;
    } else if (key < T->data) {
return SearchBST(T->lchild, key); // 在左子树中查找
    } else {
return SearchBST(T->rchild, key); // 在右子树中查找
    }
}

5.3 二叉搜索树的插入

// 插入节点
int InsertBST(BiTree *T, TElemType key) {
if (*T == NULL) { // 找到插入位置
        T = (BiTNode )malloc(sizeof(BiTNode));
if (!*T) {
exit(OVERFLOW);
        }
        (*T)->data = key;
        (*T)->lchild = (*T)->rchild = NULL;
return 1; // 插入成功
    } else if (key == (*T)->data) {
return 0; // 关键字已存在，插入失败
    } else if (key < (*T)->data) {
return InsertBST(&(*T)->lchild, key); // 插入左子树
    } else {
return InsertBST(&(*T)->rchild, key); // 插入右子树
    }
}

5.4 二叉搜索树的删除

删除操作相对复杂，需要考虑三种情况：

被删除节点是叶子节点：直接删除。

被删除节点只有一棵子树：将子树连接到父节点。

被删除节点有两棵子树：找到该节点的中序后继（右子树中最小的节点）或中序前驱（左子树中最大的节点），用其值替换被删除节点的值，然后删除后继（或前驱）节点。

// 删除节点
int DeleteBST(BiTree *T, TElemType key) {
if (*T == NULL) {
return 0; // 树空，删除失败
    } else {
if (key == (*T)->data) {
return Delete(T); // 找到节点，执行删除
        } else if (key < (*T)->data) {
return DeleteBST(&(*T)->lchild, key); // 在左子树中删除
        } else {
return DeleteBST(&(*T)->rchild, key); // 在右子树中删除
        }
    }
}
// 实际执行删除操作
int Delete(BiTree *p) {
BiTree q, s;
if ((*p)->rchild == NULL) { // 右子树为空，只需重接左子树
        q = *p;
        p = (p)->lchild;
free(q);
    } else if ((*p)->lchild == NULL) { // 左子树为空，只需重接右子树

六、其他树结构简介

6.1 平衡二叉树（AVL 树）

平衡二叉树是一种二叉搜索树，它的左右两个子树的高度差的绝对值不超过 1，并且左右两个子树都是平衡二叉树。平衡二叉树通过旋转操作（左旋、右旋、左右旋、右左旋）来维持平衡性，确保查找、插入、删除的时间复杂度稳定在 O (log n)。

6.2 红黑树

红黑树是一种自平衡的二叉搜索树，它通过颜色（红色或黑色）的约束来维持树的平衡。红黑树的规则包括：根节点是黑色；所有叶子节点都是黑色；如果一个节点是红色，则它的子节点必须是黑色；从任一节点到其叶子节点的所有路径都包含相同数目的黑色节点。红黑树的插入和删除操作也需要通过旋转和颜色调整来保持平衡，它在实际应用中非常广泛（如 C++ 的 map、set）。

6.3 B 树和 B + 树

B 树是一种多路平衡查找树，它的每个节点可以有多个子节点，适合外存存储（如磁盘）。B 树的阶数表示节点最多拥有的子节点数。B + 树是 B 树的变种，它的所有叶子节点包含了全部关键字信息，且叶子节点之间以链表连接，更适合范围查询，是数据库索引的常用结构。

七、树的应用场景

树结构在计算机科学中有着广泛的应用：

操作系统文件系统：采用树形结构组织文件和目录，方便文件的管理和查找。

数据库索引：B 树、B + 树等用于数据库索引，提高数据查询效率。

编译原理：语法树用于表示程序的语法结构。

搜索引擎：倒排索引中可能用到树结构来快速匹配关键词。

人工智能：决策树用于分类和预测。

八、总结

本文详细介绍了树的基本概念、二叉树的定义、性质、存储结构和基本操作，以及二叉搜索树等特殊树结构。通过 C 语言代码实现，我们可以更直观地理解树的工作原理。

树作为一种重要的数据结构，其高效的操作性能使其在众多领域发挥着关键作用。掌握树的基本原理和实现方法，对于提升编程能力和解决实际问题具有重要意义。

在学习过程中，建议多动手编写代码，通过实践加深对树结构的理解。例如，可以尝试实现平衡二叉树或红黑树，进一步掌握树的平衡维护机制。

C 语言版数据结构之树：从基础到实践

一、树的基本概念

1.1 树的定义

1.2 树的基本术语

二、二叉树

2.1 二叉树的定义

2.2 二叉树的性质

2.3 特殊的二叉树

三、二叉树的存储结构

3.1 顺序存储结构

3.2 链式存储结构

四、二叉树的基本操作

4.1 创建二叉树

4.2 二叉树的遍历

4.2.1 前序遍历

4.2.2 中序遍历

4.2.3 后序遍历

4.2.4 层序遍历

4.3 求二叉树的深度

4.4 求二叉树的节点个数

4.5 求叶子节点个数

五、二叉搜索树（BST）

5.1 二叉搜索树的定义

5.2 二叉搜索树的查找

5.3 二叉搜索树的插入

5.4 二叉搜索树的删除

六、其他树结构简介

6.1 平衡二叉树（AVL 树）

6.2 红黑树

6.3 B 树和 B + 树

七、树的应用场景

八、总结

切换评论系统

热门文章

C 语言版数据结构之树：从基础到实践

一、树的基本概念​

1.1 树的定义​

1.2 树的基本术语​

二、二叉树​

2.1 二叉树的定义​

2.2 二叉树的性质​

2.3 特殊的二叉树​

三、二叉树的存储结构​

3.1 顺序存储结构​

3.2 链式存储结构​

四、二叉树的基本操作​

4.1 创建二叉树​

4.2 二叉树的遍历​

4.2.1 前序遍历​

4.2.2 中序遍历​

4.2.3 后序遍历​

4.2.4 层序遍历​

4.3 求二叉树的深度​

4.4 求二叉树的节点个数​

4.5 求叶子节点个数​

五、二叉搜索树（BST）​

5.1 二叉搜索树的定义​

5.2 二叉搜索树的查找​

5.3 二叉搜索树的插入​

5.4 二叉搜索树的删除​

六、其他树结构简介​

6.1 平衡二叉树（AVL 树）​

6.2 红黑树​

6.3 B 树和 B + 树​

七、树的应用场景​

八、总结​

切换评论系统

热门文章

一、树的基本概念

1.1 树的定义

1.2 树的基本术语

二、二叉树

2.1 二叉树的定义

2.2 二叉树的性质

2.3 特殊的二叉树

三、二叉树的存储结构

3.1 顺序存储结构

3.2 链式存储结构

四、二叉树的基本操作

4.1 创建二叉树

4.2 二叉树的遍历

4.2.1 前序遍历

4.2.2 中序遍历

4.2.3 后序遍历

4.2.4 层序遍历

4.3 求二叉树的深度

4.4 求二叉树的节点个数

4.5 求叶子节点个数

五、二叉搜索树（BST）

5.1 二叉搜索树的定义

5.2 二叉搜索树的查找

5.3 二叉搜索树的插入

5.4 二叉搜索树的删除

六、其他树结构简介

6.1 平衡二叉树（AVL 树）

6.2 红黑树

6.3 B 树和 B + 树

七、树的应用场景

八、总结