C语言进阶教程:数据结构-树(二叉树、平衡树)的概念与基本操作

大家好，欢迎来到IT知识分享网。

1. 树的基本概念

树是一种重要的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

• 结点（Node）: 树中的基本单元，包含数据元素以及指向其子树的分支。
• 根结点（Root Node）: 没有父结点的结点，一棵树最多只有一个根结点。
• 子结点（Child Node）: 一个结点的直接后继结点。
• 父结点（Parent Node）: 一个结点的直接前驱结点。
• 兄弟结点（Sibling Node）: 拥有相同父结点的结点。
• 叶子结点（Leaf Node）/ 终端结点: 没有子结点的结点。
• 内部结点 / 非终端结点: 除叶子结点之外的结点。
• 结点的度（Degree）: 一个结点拥有的子树的个数。
• 树的度: 树内各结点的度的最大值。
• 路径（Path）: 从结点n1到nk的路径为一个结点序列n1, n2, …, nk，其中ni是ni+1的父结点。
• 路径长度: 路径上边的数目。
• 结点的层次（Level）: 从根开始定义，根为第1层，根的子结点为第2层，以此类推。
• 树的深度（Depth）/ 高度（Height）: 树中结点的最大层次。
• 森林（Forest）: m（m>=0）棵互不相交的树的集合。

2. 二叉树

二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。

2.1 二叉树的性质

0. 在二叉树的第i层上至多有 2^(i-1) 个结点 (i >= 1)。
1. 深度为k的二叉树至多有 2^k – 1 个结点 (k >= 1)。
2. 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。

2.2 特殊的二叉树

• 满二叉树（Full Binary Tree）: 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树称为满二叉树。
• 完全二叉树（Complete Binary Tree）: 对一棵具有n个结点的二叉树按层序编号，如果编号为i（1<=i<=n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树。

2.3 二叉树的存储结构

• 顺序存储: 使用数组存储，适用于完全二叉树。
• 链式存储: 使用链表存储，每个结点包含数据域、左孩子指针域和右孩子指针域。

 // 二叉树的链式存储结构定义 typedef struct BiTNode { char data; // 结点数据 struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree;

3. 二叉树的遍历

二叉树的遍历是指按照某种次序访问树中的所有结点，并且每个结点仅被访问一次。

• 先序遍历（Preorder Traversal）: 根 -> 左子树 -> 右子树
• 中序遍历（Inorder Traversal）: 左子树 -> 根 -> 右子树
• 后序遍历（Postorder Traversal）: 左子树 -> 右子树 -> 根
• 层序遍历（Level Order Traversal）: 从上到下，从左到右逐层访问

4. 平衡树初步

平衡树是为了解决二叉搜索树在极端情况下退化成链表的问题而提出的。它要求树中任何结点的两个子树的高度差的绝对值不超过1。

• AVL树: 最早的自平衡二叉搜索树。
• 红黑树: 另一种自平衡二叉搜索树，广泛应用于各种数据结构和算法中。

5. 基本操作示例 (C语言)

 #include <stdio.h> #include <stdlib.h> // 二叉树结点定义 typedef struct BiTNode { char data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; // 创建二叉树 (先序遍历方式创建) BiTree CreateBiTree() { char ch; scanf("%c", &ch); if (ch == '#') { // '#' 表示空树 return NULL; } BiTree T = (BiTree)malloc(sizeof(BiTNode)); if (!T) { exit(OVERFLOW); // 内存分配失败 } T->data = ch; T->lchild = CreateBiTree(); T->rchild = CreateBiTree(); return T; } // 先序遍历 void PreOrderTraverse(BiTree T) { if (T) { printf("%c ", T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } } // 中序遍历 void InOrderTraverse(BiTree T) { if (T) { InOrderTraverse(T->lchild); printf("%c ", T->data); InOrderTraverse(T->rchild); } } // 后序遍历 void PostOrderTraverse(BiTree T) { if (T) { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf("%c ", T->data); } } int main() { BiTree myTree; printf("请按先序遍历输入二叉树结点 (例如: ABDECF, '#'表示空子树):\n"); myTree = CreateBiTree(); printf("\n先序遍历结果: "); PreOrderTraverse(myTree); printf("\n中序遍历结果: "); InOrderTraverse(myTree); printf("\n后序遍历结果: "); PostOrderTraverse(myTree); printf("\n"); // 释放树的内存 (此处省略，实际应用中需要实现) return 0; }

总结

本节介绍了树和二叉树的基本概念、性质、存储结构以及遍历方法。同时初步了解了平衡树的概念。掌握这些内容是学习更高级数据结构和算法的基础。