数据结构（5）二叉树的存储、创建与四种遍历算法

一、二叉树的基本概念二叉树Binary Tree是每个节点最多拥有两棵子树的树结构通常子树被称作左子树和右子树。1.1 二叉树的递归定义二叉树是 nn≥0个节点的有限集合该集合或者为空集空二叉树或者由一个根节点和两棵互不相交的、分别称为左子树和右子树的二叉树组成。1.2 二叉树的性质第 i 层最多有 2^(i-1) 个节点深度为 k 的二叉树最多有 2^k - 1 个节点叶子节点数 n₀ 度为2的节点数 n₂ 1。1.3 二叉树的存储本文采用链式存储每个节点包含一个数据域和两个指针域分别指向左孩子和右孩子。二、二叉树的节点定义btree.h#ifndef _BTREE_H_ #define _BTREE_H_ typedef int data_t; typedef struct btnode { data_t data; // 数据域 struct btnode *pl; // 指向左子树 struct btnode *pr; // 指向右子树 } btree_t; // 二叉树节点类型 #endif三、由前序和中序序列手动还原二叉树已知一棵二叉树的先序序列为A B D F C E G H中序序列为B F D A G E H C手动还原这棵二叉树。3.1 还原过程基本原理前序遍历根→ 左 → 右第一个元素是根中序遍历左 →根→ 右根的左边是左子树右边是右子树Step 1确定整棵树的根前序序列第一个元素是A所以A 是根。Step 2在中序序列中划分左右子树中序序列B F D A G E H C以A为分界A 的左边B F D→ A 的左子树A 的右边G E H C→ A 的右子树Step 3递归还原左子树B F D左子树节点集合为 {B, F, D}对应前序序列为B D F前序中紧跟 A 之后的 3 个属于左子树的元素。前序中B排第一 →B 是左子树的根在中序B F D中B 左边为空 → B 没有左子树B 右边F D→ B 的右子树继续分析F DB 的右子树对应前序D F前序中D排第一 →D 是根在中序F D中D 左边F→ D 的左子树D 右边为空 → D 没有右子树F是叶子节点Step 4递归还原右子树G E H C右子树节点集合为 {G, E, H, C}对应前序序列为C E G H。前序中C排第一 →C 是右子树的根在中序G E H C中C 左边G E H→ C 的左子树C 右边为空 → C 没有右子树继续分析G E HC 的左子树对应前序E G H前序中E排第一 →E 是根在中序G E H中E 左边G→ E 的左子树E 右边H→ E 的右子树G和H都是叶子节点3.2 还原结果最终得到的二叉树结构如下A / B \ D / F C / E / \ G H也可以画得更完整A / \ B C \ / D E / / \ F G H3.3 后序遍历验证后序遍历左 → 右 → 根F D B G H E C A先遍历左子树F → D → B再遍历右子树G → H → E → C最后根A合并F D B G H E C A✓3.4 后序线索树后序遍历序列F → D → B → G → H → E → C → A在后序遍历序列中每个节点的前驱序列中前一个和后继序列中后一个如下节点前驱pre后继postF无第一个DDFBBDGGBHHGEEHCCEAAC无最后一个后序线索树中利用空指针域存放遍历序列中的前驱/后继信息左指针指前驱右指针指后继其中首节点 F 的前驱线索和末节点 A 的后继线索为空。3.5 将二叉树转换为对应的树或森林转换规则二叉树转树/森林的核心是左孩子右兄弟表示法的逆过程——节点的左孩子转为树中的第一个孩子节点的右兄弟转为树中的下一个兄弟。转换过程1.从根节点 A 开始A 的左孩子 B 变成 A 的第一个孩子A 的右孩子 C 变成 A 的下一个兄弟——但 A 是根无兄弟所以 C 作为 A 的另一个孩子即 B 的右兄弟 → A 的第二个孩子2.但更准确地说A 的左子树和右子树分别构成两棵树形成森林第一棵树根为 AA 的左孩子 B 是 A 的第一个孩子D 是 B 的孩子F 是 D 的孩子第二棵树根为 CE 是 C 的孩子G 和 H 是 E 的孩子森林的树形表示 第一棵树 第二棵树 A C | | B E | / \ D G H | F四、二叉树的创建代码实现扩展先序序列采用扩展先序序列递归创建二叉树。遇到空节点时用#标记。例如序列ABDG##H###CE#I##F##对应的二叉树结构如下A / \ B C / / \ D E F / \ \ G H I核心代码#include stdio.h #include stdlib.h #include btree.h char tree_seq[] ABDG##H###CE#I##F##; int idx 0; // 当前读取位置 btree_t *create_btree(void) { char data tree_seq[idx]; if (data #) { return NULL; // # 表示空节点结束 } btree_t *new malloc(sizeof(btree_t)); if (new NULL) { printf(malloc fail!\n); return NULL; } new-data data; new-pl create_btree(); // 递归创建左子树 new-pr create_btree(); // 递归创建右子树 return new; }思路解析1.从序列中读取一个字符2.如果是#返回NULL表示该子树为空3.否则创建新节点填入数据然后递归创建左子树和右子树4.全局变量idx记录当前读取到序列的第几个字符。五、二叉树的四种遍历方式5.1 前序遍历Pre-Order根 → 左 → 右int pre_order_traverse(btree_t *t) { if (t NULL) return 0; printf(%c , t-data); // 根 pre_order_traverse(t-pl); // 左子树 pre_order_traverse(t-pr); // 右子树 return 0; }输出A B D G H C E I F5.2 中序遍历In-Order左 → 根 → 右int in_order_traverse(btree_t *t) { if (t NULL) return 0; in_order_traverse(t-pl); // 左子树 printf(%c , t-data); // 根 in_order_traverse(t-pr); // 右子树 return 0; }输出G D H B A E I C F5.3 后序遍历Post-Order左 → 右 → 根int post_order_traverse(btree_t *t) { if (t NULL) return 0; post_order_traverse(t-pl); // 左子树 post_order_traverse(t-pr); // 右子树 printf(%c , t-data); // 根 return 0; }输出G H D B I E F C A5.4 三种递归遍历的对比总结遍历方式访问顺序特点前序遍历根 → 左 → 右适合复制/序列化树结构中序遍历左 → 根 → 右对二叉搜索树结果为有序序列后序遍历左 → 右 → 根适合释放内存/计算树的大小递归遍历的共同模式终止条件t NULL时返回递归结构三个函数的代码结构完全相同只是printf语句的位置不同。5.5 层序遍历Level-Order逐层从左到右层序遍历需要借助队列来实现属于广度优先搜索BFS的思想。#include linkqueue.h int layer_order_traverse(btree_t *t) { if (t NULL) return -1; // 步骤1创建队列根节点入队 node_t *pq linkqueue_create(); enqueue(pq, t); // 步骤2循环出队、打印、子节点入队 while (is_empty(pq) ! 1) { btree_t *data NULL; dequeue(pq, data); printf(%c , data-data); if (data-pl ! NULL) enqueue(pq, data-pl); // 左孩子入队 if (data-pr ! NULL) enqueue(pq, data-pr); // 右孩子入队 } // 步骤3销毁队列 linkqueue_destroy(pq); return 0; }输出A B C D E F G H I为什么层序遍历需要队列队列的 FIFO 特性保证了同一层的节点先被访问其子节点后被访问从而实现逐层遍历。六、二叉树的销毁释放二叉树内存需要采用后序遍历的顺序左 → 右 → 根必须先释放子节点再释放父节点否则会丢失子节点的引用野指针。int btree_destroy(btree_t *t) { if (t NULL) return -1; btree_destroy(t-pl); // 递归销毁左子树 btree_destroy(t-pr); // 递归销毁右子树 free(t); // 释放根节点 return 0; }七、主函数与完整运行结果int main(int argc, const char *argv[]) { btree_t *root create_btree(); printf(前序遍历: ); pre_order_traverse(root); putchar(\n); printf(中序遍历: ); in_order_traverse(root); putchar(\n); printf(后序遍历: ); post_order_traverse(root); putchar(\n); printf(层序遍历: ); layer_order_traverse(root); putchar(\n); // btree_destroy(root); // 释放二叉树 return 0; }运行结果text前序遍历: A B D G H C E I F 中序遍历: G D H B A E I C F 后序遍历: G H D B I E F C A 层序遍历: A B C D E F G H I八、总结遍历方式实现方式核心数据结构时间复杂度空间复杂度前序遍历递归系统调用栈O(n)O(h)h为树高中序遍历递归系统调用栈O(n)O(h)后序遍历递归系统调用栈O(n)O(h)层序遍历迭代队列链表实现O(n)O(w)w为最大层宽学习要点回顾1.链式队列的核心入队 尾插出队 头删两者配合保证 FIFO2.二叉树是递归结构遍历算法天然适合递归实现3.前/中/后序遍历的区别仅在于printf的位置4.已知前序 中序序列可以唯一还原二叉树前序定根中序分左右子树5.层序遍历是唯一的非递归遍历需要队列辅助6.销毁二叉树必须使用后序顺序避免野指针7.二叉树可以通过左孩子右兄弟的逆规则转换为树或森林。