一、树与二叉树从概念到形态1.1 树的定义树是由n (n≥0)个节点组成的有限集合当n0时称为空树当n0时满足有且仅有一个根节点Root其余节点可分为m≥0个互不相交的子集每个子集本身也是一棵树称为子树Subtree。1.2 树的核心概念节点的度节点拥有的子树个数叶子节点度为 0树的度树中所有节点的度的最大值叶子节点度为 0 的节点没有子节点孩子 / 父节点节点的子树的根是它的孩子它是孩子的父节点兄弟节点同一个父节点的孩子互为兄弟高度 / 深度树的层数根节点在第 1 层深度为 1。1.3 二叉树的定义二叉树是每个节点最多有两个子树的树结构两个子树分别称为左子树和右子树有严格的顺序之分。1.4 二叉树的五种基本形态空二叉树没有任何节点只有一个根节点根节点只有左子树根节点只有右子树根节点既有左子树又有右子树。1.5 特殊二叉树满二叉树特点每个分支节点都有左子树和右子树且所有叶子节点都在同一层形态完美对称没有任何空缺。完全二叉树特点除了最后一层其他层的节点数都达到最大值最后一层的节点都靠左排列关系满二叉树是特殊的完全二叉树但完全二叉树不一定是满的。二、二叉树的重要性质这些性质是解题和面试的核心必须牢记性质内容1第i层i≥1上最多有2^(i-1)个节点2深度为k的二叉树最多有2^k - 1个节点3对任意非空二叉树n0 n2 1n0是叶子节点数n2是度为 2 的节点数4具有n个节点的完全二叉树其深度为⌊log₂n⌋ 1向下取整推导示例n0 n2 1总节点数n n0 n1 n2总边数n-1 n1 2n2每个节点除了根都有一条边联立两式n0 n1 n2 - 1 n1 2n2→n0 n2 1三、二叉树的遍历三种核心遍历方式遍历是指按某种顺序访问二叉树的所有节点二叉树有三种经典遍历方式核心区别在于访问根节点的时机3.1 前序遍历Pre-order顺序根节点 → 左子树 → 右子树口诀根左右示例A / \ B C / \ D E 前序遍历结果A → B → D → E → C3.2 中序遍历In-order顺序左子树 → 根节点 → 右子树口诀左根右示例A / \ B C / \ D E 中序遍历结果D → B → E → A → C3.3 后序遍历Post-order顺序左子树 → 右子树 → 根节点口诀左右根示例A / \ B C / \ D E 后序遍历结果D → E → B → C → A3.4 层序遍历Level-order顺序按层次从上到下、从左到右访问节点实现借助队列先入队根节点然后依次出队访问再将左右子节点入队直到队列为空。示例A / \ B C / \ D E 层序遍历结果A → B → C → D → E四、二叉树的代码实现C 语言4.1 二叉树节点结构定义#include stdio.h #include stdlib.h #include string.h typedef int data_t; // 数据类型别名 // 二叉树节点结构 typedef struct btree { data_t data; // 数据域 struct btree *pl; // 左子树指针 struct btree *pr; // 右子树指针 } btree_t;4.2 创建二叉树前序递归创建我们用字符串表示二叉树#代表空节点例如ABD##E##CF##// 全局索引用于遍历创建字符串 int idx 0; char tree_seq[] ABD##E##CF##; // 示例前序序列 // 前序递归创建二叉树 btree_t *create_btree(void) { char data tree_seq[idx]; if (data #) { return NULL; // #表示空节点 } // 1. 创建根节点 btree_t *new_node (btree_t *)malloc(sizeof(btree_t)); new_node-data data; // 2. 递归创建左子树和右子树 new_node-pl create_btree(); // 左 new_node-pr create_btree(); // 右 return new_node; }4.3 前序遍历递归实现void pre_order_traverse(btree_t *t) { if (t NULL) { return; } printf(%c , t-data); // 访问根节点 pre_order_traverse(t-pl); // 遍历左子树 pre_order_traverse(t-pr); // 遍历右子树 }4.4 中序遍历递归实现void in_order_traverse(btree_t *t) { if (t NULL) { return; } in_order_traverse(t-pl); // 遍历左子树 printf(%c , t-data); // 访问根节点 in_order_traverse(t-pr); // 遍历右子树 }4.5 后序遍历递归实现void post_order_traverse(btree_t *t) { if (t NULL) { return; } post_order_traverse(t-pl); // 遍历左子树 post_order_traverse(t-pr); // 遍历右子树 printf(%c , t-data); // 访问根节点 }4.6 层序遍历队列实现// 队列节点结构 typedef struct qnode { btree_t *data; struct qnode *next; } qnode_t; // 队列结构 typedef struct queue { qnode_t *front; qnode_t *rear; } queue_t; // 创建队列 queue_t *queue_create(void) { queue_t *q (queue_t *)malloc(sizeof(queue_t)); q-front q-rear NULL; return q; } // 入队 void enqueue(queue_t *q, btree_t *data) { qnode_t *new_node (qnode_t *)malloc(sizeof(qnode_t)); new_node-data data; new_node-next NULL; if (q-rear NULL) { q-front q-rear new_node; return; } q-rear-next new_node; q-rear new_node; } // 出队 btree_t *dequeue(queue_t *q) { if (q-front NULL) { return NULL; } qnode_t *temp q-front; btree_t *data temp-data; q-front q-front-next; if (q-front NULL) { q-rear NULL; } free(temp); return data; } // 队列是否为空 int queue_is_empty(queue_t *q) { return q-front NULL; } // 层序遍历 void level_order_traverse(btree_t *t) { if (t NULL) { return; } queue_t *q queue_create(); enqueue(q, t); // 根节点入队 while (!queue_is_empty(q)) { btree_t *node dequeue(q); printf(%c , node-data); // 访问节点 // 左子节点入队 if (node-pl ! NULL) { enqueue(q, node-pl); } // 右子节点入队 if (node-pr ! NULL) { enqueue(q, node-pr); } } free(q); }4.7 销毁二叉树后序递归销毁void btree_destroy(btree_t *t) { if (t NULL) { return; } btree_destroy(t-pl); // 销毁左子树 btree_destroy(t-pr); // 销毁右子树 free(t); // 销毁根节点 }4.8 完整测试代码int main() { // 1. 创建二叉树 btree_t *root create_btree(); // 2. 遍历测试 printf(前序遍历); pre_order_traverse(root); // 输出A B D E C F printf(\n); printf(中序遍历); in_order_traverse(root); // 输出D B E A C F printf(\n); printf(后序遍历); post_order_traverse(root); // 输出D E B F C A printf(\n); printf(层序遍历); level_order_traverse(root); // 输出A B C D E F printf(\n); // 3. 销毁二叉树 btree_destroy(root); return 0; }五、遍历序列与二叉树的重建这是面试高频考点已知两种遍历序列可以唯一确定一棵二叉树但必须包含中序遍历已知序列能否重建说明前序 中序✅ 可以前序确定根中序划分左右子树中序 后序✅ 可以后序确定根中序划分左右子树前序 后序❌ 不可以无法确定左右子树的边界示例已知前序ABDECF和中序DBEAFC重建二叉树前序第一个节点A是根中序中A左边DBE是左子树右边FC是右子树递归处理左子树前序BDE中序DBE和右子树前序CF中序FC。六、总结6.1 核心知识点回顾二叉树定义每个节点最多两个子树有严格左右顺序特殊形态满二叉树、完全二叉树掌握它们的性质核心性质n0 n2 1、深度计算、每层最大节点数四种遍历前序根左右、中序左根右、后序左右根、层序队列代码实现递归创建、递归遍历、层序遍历、销毁。
树与二叉树
一、树与二叉树从概念到形态1.1 树的定义树是由n (n≥0)个节点组成的有限集合当n0时称为空树当n0时满足有且仅有一个根节点Root其余节点可分为m≥0个互不相交的子集每个子集本身也是一棵树称为子树Subtree。1.2 树的核心概念节点的度节点拥有的子树个数叶子节点度为 0树的度树中所有节点的度的最大值叶子节点度为 0 的节点没有子节点孩子 / 父节点节点的子树的根是它的孩子它是孩子的父节点兄弟节点同一个父节点的孩子互为兄弟高度 / 深度树的层数根节点在第 1 层深度为 1。1.3 二叉树的定义二叉树是每个节点最多有两个子树的树结构两个子树分别称为左子树和右子树有严格的顺序之分。1.4 二叉树的五种基本形态空二叉树没有任何节点只有一个根节点根节点只有左子树根节点只有右子树根节点既有左子树又有右子树。1.5 特殊二叉树满二叉树特点每个分支节点都有左子树和右子树且所有叶子节点都在同一层形态完美对称没有任何空缺。完全二叉树特点除了最后一层其他层的节点数都达到最大值最后一层的节点都靠左排列关系满二叉树是特殊的完全二叉树但完全二叉树不一定是满的。二、二叉树的重要性质这些性质是解题和面试的核心必须牢记性质内容1第i层i≥1上最多有2^(i-1)个节点2深度为k的二叉树最多有2^k - 1个节点3对任意非空二叉树n0 n2 1n0是叶子节点数n2是度为 2 的节点数4具有n个节点的完全二叉树其深度为⌊log₂n⌋ 1向下取整推导示例n0 n2 1总节点数n n0 n1 n2总边数n-1 n1 2n2每个节点除了根都有一条边联立两式n0 n1 n2 - 1 n1 2n2→n0 n2 1三、二叉树的遍历三种核心遍历方式遍历是指按某种顺序访问二叉树的所有节点二叉树有三种经典遍历方式核心区别在于访问根节点的时机3.1 前序遍历Pre-order顺序根节点 → 左子树 → 右子树口诀根左右示例A / \ B C / \ D E 前序遍历结果A → B → D → E → C3.2 中序遍历In-order顺序左子树 → 根节点 → 右子树口诀左根右示例A / \ B C / \ D E 中序遍历结果D → B → E → A → C3.3 后序遍历Post-order顺序左子树 → 右子树 → 根节点口诀左右根示例A / \ B C / \ D E 后序遍历结果D → E → B → C → A3.4 层序遍历Level-order顺序按层次从上到下、从左到右访问节点实现借助队列先入队根节点然后依次出队访问再将左右子节点入队直到队列为空。示例A / \ B C / \ D E 层序遍历结果A → B → C → D → E四、二叉树的代码实现C 语言4.1 二叉树节点结构定义#include stdio.h #include stdlib.h #include string.h typedef int data_t; // 数据类型别名 // 二叉树节点结构 typedef struct btree { data_t data; // 数据域 struct btree *pl; // 左子树指针 struct btree *pr; // 右子树指针 } btree_t;4.2 创建二叉树前序递归创建我们用字符串表示二叉树#代表空节点例如ABD##E##CF##// 全局索引用于遍历创建字符串 int idx 0; char tree_seq[] ABD##E##CF##; // 示例前序序列 // 前序递归创建二叉树 btree_t *create_btree(void) { char data tree_seq[idx]; if (data #) { return NULL; // #表示空节点 } // 1. 创建根节点 btree_t *new_node (btree_t *)malloc(sizeof(btree_t)); new_node-data data; // 2. 递归创建左子树和右子树 new_node-pl create_btree(); // 左 new_node-pr create_btree(); // 右 return new_node; }4.3 前序遍历递归实现void pre_order_traverse(btree_t *t) { if (t NULL) { return; } printf(%c , t-data); // 访问根节点 pre_order_traverse(t-pl); // 遍历左子树 pre_order_traverse(t-pr); // 遍历右子树 }4.4 中序遍历递归实现void in_order_traverse(btree_t *t) { if (t NULL) { return; } in_order_traverse(t-pl); // 遍历左子树 printf(%c , t-data); // 访问根节点 in_order_traverse(t-pr); // 遍历右子树 }4.5 后序遍历递归实现void post_order_traverse(btree_t *t) { if (t NULL) { return; } post_order_traverse(t-pl); // 遍历左子树 post_order_traverse(t-pr); // 遍历右子树 printf(%c , t-data); // 访问根节点 }4.6 层序遍历队列实现// 队列节点结构 typedef struct qnode { btree_t *data; struct qnode *next; } qnode_t; // 队列结构 typedef struct queue { qnode_t *front; qnode_t *rear; } queue_t; // 创建队列 queue_t *queue_create(void) { queue_t *q (queue_t *)malloc(sizeof(queue_t)); q-front q-rear NULL; return q; } // 入队 void enqueue(queue_t *q, btree_t *data) { qnode_t *new_node (qnode_t *)malloc(sizeof(qnode_t)); new_node-data data; new_node-next NULL; if (q-rear NULL) { q-front q-rear new_node; return; } q-rear-next new_node; q-rear new_node; } // 出队 btree_t *dequeue(queue_t *q) { if (q-front NULL) { return NULL; } qnode_t *temp q-front; btree_t *data temp-data; q-front q-front-next; if (q-front NULL) { q-rear NULL; } free(temp); return data; } // 队列是否为空 int queue_is_empty(queue_t *q) { return q-front NULL; } // 层序遍历 void level_order_traverse(btree_t *t) { if (t NULL) { return; } queue_t *q queue_create(); enqueue(q, t); // 根节点入队 while (!queue_is_empty(q)) { btree_t *node dequeue(q); printf(%c , node-data); // 访问节点 // 左子节点入队 if (node-pl ! NULL) { enqueue(q, node-pl); } // 右子节点入队 if (node-pr ! NULL) { enqueue(q, node-pr); } } free(q); }4.7 销毁二叉树后序递归销毁void btree_destroy(btree_t *t) { if (t NULL) { return; } btree_destroy(t-pl); // 销毁左子树 btree_destroy(t-pr); // 销毁右子树 free(t); // 销毁根节点 }4.8 完整测试代码int main() { // 1. 创建二叉树 btree_t *root create_btree(); // 2. 遍历测试 printf(前序遍历); pre_order_traverse(root); // 输出A B D E C F printf(\n); printf(中序遍历); in_order_traverse(root); // 输出D B E A C F printf(\n); printf(后序遍历); post_order_traverse(root); // 输出D E B F C A printf(\n); printf(层序遍历); level_order_traverse(root); // 输出A B C D E F printf(\n); // 3. 销毁二叉树 btree_destroy(root); return 0; }五、遍历序列与二叉树的重建这是面试高频考点已知两种遍历序列可以唯一确定一棵二叉树但必须包含中序遍历已知序列能否重建说明前序 中序✅ 可以前序确定根中序划分左右子树中序 后序✅ 可以后序确定根中序划分左右子树前序 后序❌ 不可以无法确定左右子树的边界示例已知前序ABDECF和中序DBEAFC重建二叉树前序第一个节点A是根中序中A左边DBE是左子树右边FC是右子树递归处理左子树前序BDE中序DBE和右子树前序CF中序FC。六、总结6.1 核心知识点回顾二叉树定义每个节点最多两个子树有严格左右顺序特殊形态满二叉树、完全二叉树掌握它们的性质核心性质n0 n2 1、深度计算、每层最大节点数四种遍历前序根左右、中序左根右、后序左右根、层序队列代码实现递归创建、递归遍历、层序遍历、销毁。
