树与二叉树：数据结构核心解析

引言在前面的文章中我们已经系统学习了线性数据结构——链表、栈、队列。线性结构的特点是元素之间存在一对一的先后关系。然而现实世界中的很多数据关系是一对多的文件系统中的目录与子目录、公司的组织架构、网页的 DOM 结构……树Tree正是用来描述这种层级关系的非线性数据结构。它是整个数据结构体系中最重要的篇章之一也是后续学习堆、B 树、红黑树、图等高级结构的基础。第一部分树的基本概念一、什么是树树是由nn ≥ 0个节点组成的有限集合当 n 0 时称为空树当 n 0 时有一个特殊的节点称为根节点Root其余节点可分为 m 个互不相交的有限集合每个集合本身又是一棵树称为根的子树Subtree二、核心术语度、深度、高度的对比三、树的表示方法1. 双亲表示法用数组存父节点下标#define MAX_NODES 100 typedef struct { char data; // 节点数据 int parent; // 父节点下标根节点的 parent -1 } PTNode; typedef struct { PTNode nodes[MAX_NODES]; int n; // 节点数量 } PTree;2. 孩子表示法每个节点带子节点链表typedef struct ChildNode { int child_index; // 子节点在数组中的下标 struct ChildNode* next; // 下一个兄弟 } ChildNode; typedef struct { char data; ChildNode* first_child; // 第一个子节点的链表头 } CTBox; typedef struct { CTBox nodes[MAX_NODES]; int n; } CTree;3. 孩子兄弟表示法最常用二叉树的基础typedef struct CSNode { char data; struct CSNode* first_child; // 第一个孩子 struct CSNode* next_sibling; // 下一个兄弟 } CSNode;第二部分二叉树一、二叉树的定义二叉树是每个节点最多只有两个子节点的树子节点分为左子节点和右子节点。typedef struct BinTreeNode { int data; // 数据域 struct BinTreeNode* left; // 左子节点 struct BinTreeNode* right; // 右子节点 } BinTreeNode;二、两种特殊的二叉树1. 满二叉树Full Binary Tree每一层的节点数都达到最大值。第 k 层有 2^(k-1) 个节点总节点数为 2^h - 1h 为层数。2. 完全二叉树Complete Binary Tree叶子节点只出现在最底层和次底层且最底层的叶子节点都连续集中在左边。完全二叉树的重要特性可以用数组高效存储。三、二叉树的性质性质内容性质1第 i 层最多有 2^(i-1) 个节点i ≥ 1性质2深度为 k 的二叉树最多有 2^k - 1 个节点性质3对于任意二叉树若叶子数为 n₀度为 2 的节点数为 n₂则 n₀ n₂ 1性质4n 个节点的完全二叉树深度为 ⌊log₂n⌋ 1性质3证明四、二叉树的遍历遍历是二叉树最基础也是最重要的操作。共有四种遍历方式4.1 递归实现#include stdio.h #include stdlib.h typedef struct TreeNode { int data; struct TreeNode* left; struct TreeNode* right; } TreeNode; // 前序遍历根 → 左 → 右 void preorder(TreeNode* root) { if (root NULL) return; printf(%d , root-data); preorder(root-left); preorder(root-right); } // 中序遍历左 → 根 → 右 void inorder(TreeNode* root) { if (root NULL) return; inorder(root-left); printf(%d , root-data); inorder(root-right); } // 后序遍历左 → 右 → 根 void postorder(TreeNode* root) { if (root NULL) return; postorder(root-left); postorder(root-right); printf(%d , root-data); }4.2 层序遍历BFS需要队列#include stdbool.h #define MAX_QUEUE 100 typedef struct { TreeNode* data[MAX_QUEUE]; int front, rear; } Queue; void initQueue(Queue* q) { q-front q-rear 0; } bool isEmpty(Queue* q) { return q-front q-rear; } void enqueue(Queue* q, TreeNode* node) { q-data[q-rear] node; } TreeNode* dequeue(Queue* q) { return q-data[q-front]; } // 层序遍历 void levelorder(TreeNode* root) { if (root NULL) return; Queue q; initQueue(q); enqueue(q, root); while (!isEmpty(q)) { TreeNode* node dequeue(q); printf(%d , node-data); if (node-left ! NULL) enqueue(q, node-left); if (node-right ! NULL) enqueue(q, node-right); } }层序遍历过程图解4.3 非递归实现需要栈// 非递归中序遍历 void inorder_iterative(TreeNode* root) { TreeNode* stack[100]; int top -1; TreeNode* cur root; while (cur ! NULL || top ! -1) { // 一直走到最左边 while (cur ! NULL) { stack[top] cur; cur cur-left; } // 弹出栈顶访问它然后转向右子树 cur stack[top--]; printf(%d , cur-data); cur cur-right; } }