【数据结构与算法】第20篇：二叉树的链式存储与四种遍历（前序、中序、后序、层序）

一、二叉树的链式存储1.1 节点结构每个节点包含三部分数据域左孩子指针右孩子指针ctypedef struct TreeNode { int data; struct TreeNode *left; struct TreeNode *right; } TreeNode, *Tree;1.2 创建节点cTreeNode* createNode(int value) { TreeNode *node (TreeNode*)malloc(sizeof(TreeNode)); if (node NULL) { printf(内存分配失败\n); return NULL; } node-data value; node-left NULL; node-right NULL; return node; }1.3 构建二叉树为了方便测试我们先手动构建一棵二叉树text1 / \ 2 3 / \ \ 4 5 6cTreeNode* buildTree() { TreeNode *root createNode(1); root-left createNode(2); root-right createNode(3); root-left-left createNode(4); root-left-right createNode(5); root-right-right createNode(6); return root; }二、二叉树的递归遍历2.1 前序遍历根→左→右访问顺序先访问根节点再遍历左子树最后遍历右子树。text示例树的前序1 → 2 → 4 → 5 → 3 → 6cvoid preorder(TreeNode *root) { if (root NULL) return; printf(%d , root-data); // 访问根 preorder(root-left); // 遍历左子树 preorder(root-right); // 遍历右子树 }递归调用栈以前序为例textpreorder(1) ├─ 打印1 ├─ preorder(2) │ ├─ 打印2 │ ├─ preorder(4) │ │ ├─ 打印4 │ │ ├─ preorder(NULL) │ │ └─ preorder(NULL) │ └─ preorder(5) │ ├─ 打印5 │ └─ ... └─ preorder(3) ├─ 打印3 └─ preorder(6) └─ ...2.2 中序遍历左→根→右访问顺序先遍历左子树再访问根节点最后遍历右子树。text示例树的中序4 → 2 → 5 → 1 → 3 → 6cvoid inorder(TreeNode *root) { if (root NULL) return; inorder(root-left); // 遍历左子树 printf(%d , root-data); // 访问根 inorder(root-right); // 遍历右子树 }2.3 后序遍历左→右→根访问顺序先遍历左子树再遍历右子树最后访问根节点。text示例树的后序4 → 5 → 2 → 6 → 3 → 1cvoid postorder(TreeNode *root) { if (root NULL) return; postorder(root-left); // 遍历左子树 postorder(root-right); // 遍历右子树 printf(%d , root-data); // 访问根 }三、层序遍历广度优先3.1 算法思路层序遍历按树的层次从上到下、从左到右访问节点。需要借助队列根节点入队当队列不为空时出队一个节点访问它如果左孩子存在左孩子入队如果右孩子存在右孩子入队text示例树的层序1 → 2 → 3 → 4 → 5 → 63.2 队列实现c// 队列节点 typedef struct QueueNode { TreeNode *node; struct QueueNode *next; } QueueNode; typedef struct { QueueNode *front; QueueNode *rear; } Queue; void initQueue(Queue *q) { q-front q-rear NULL; } int isEmpty(Queue *q) { return q-front NULL; } void enqueue(Queue *q, TreeNode *node) { QueueNode *newNode (QueueNode*)malloc(sizeof(QueueNode)); newNode-node node; newNode-next NULL; if (isEmpty(q)) { q-front q-rear newNode; } else { q-rear-next newNode; q-rear newNode; } } TreeNode* dequeue(Queue *q) { if (isEmpty(q)) return NULL; QueueNode *temp q-front; TreeNode *node temp-node; q-front q-front-next; if (q-front NULL) q-rear NULL; free(temp); return node; }3.3 层序遍历实现cvoid levelOrder(TreeNode *root) { if (root NULL) return; Queue q; initQueue(q); enqueue(q, root); while (!isEmpty(q)) { TreeNode *cur dequeue(q); printf(%d , cur-data); if (cur-left ! NULL) { enqueue(q, cur-left); } if (cur-right ! NULL) { enqueue(q, cur-right); } } }四、完整代码演示c#include stdio.h #include stdlib.h // 二叉树节点 typedef struct TreeNode { int data; struct TreeNode *left; struct TreeNode *right; } TreeNode; // 队列节点 typedef struct QueueNode { TreeNode *node; struct QueueNode *next; } QueueNode; typedef struct { QueueNode *front; QueueNode *rear; } Queue; // 二叉树操作 TreeNode* createNode(int value) { TreeNode *node (TreeNode*)malloc(sizeof(TreeNode)); if (node NULL) return NULL; node-data value; node-left NULL; node-right NULL; return node; } TreeNode* buildTree() { TreeNode *root createNode(1); root-left createNode(2); root-right createNode(3); root-left-left createNode(4); root-left-right createNode(5); root-right-right createNode(6); return root; } // 队列操作 void initQueue(Queue *q) { q-front q-rear NULL; } int isEmpty(Queue *q) { return q-front NULL; } void enqueue(Queue *q, TreeNode *node) { QueueNode *newNode (QueueNode*)malloc(sizeof(QueueNode)); newNode-node node; newNode-next NULL; if (isEmpty(q)) { q-front q-rear newNode; } else { q-rear-next newNode; q-rear newNode; } } TreeNode* dequeue(Queue *q) { if (isEmpty(q)) return NULL; QueueNode *temp q-front; TreeNode *node temp-node; q-front q-front-next; if (q-front NULL) q-rear NULL; free(temp); return node; } // 四种遍历 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); } void levelOrder(TreeNode *root) { if (root NULL) return; Queue q; initQueue(q); enqueue(q, root); while (!isEmpty(q)) { TreeNode *cur dequeue(q); printf(%d , cur-data); if (cur-left ! NULL) { enqueue(q, cur-left);enqueue(q, cur-left); } if (cur-right ! NULL) { enqueue(q, cur-right); } } } // 释放二叉树 void freeTree(TreeNode *root) { if (root NULL) return; freeTree(root-left); freeTree(root-right); free(root); } int main() { TreeNode *root buildTree(); printf(二叉树结构\n); printf( 1\n); printf( / \\\n); printf( 2 3\n); printf( / \\ \\\n); printf( 4 5 6\n\n); printf(前序遍历根左右: ); preorder(root); printf(\n); printf(中序遍历左根右: ); inorder(root); printf(\n); printf(后序遍历左右根: ); postorder(root); printf(\n); printf(层序遍历: ); levelOrder(root); printf(\n); freeTree(root); return 0; }运行结果text二叉树结构 1 / \ 2 3 / \ \ 4 5 6 前序遍历根左右: 1 2 4 5 3 6 中序遍历左根右: 4 2 5 1 3 6 后序遍历左右根: 4 5 2 6 3 1 层序遍历: 1 2 3 4 5 6五、四种遍历的对比总结遍历方式访问顺序示例结果应用场景前序根→左→右1,2,4,5,3,6复制树、求表达式前缀中序左→根→右4,2,5,1,3,6二叉搜索树输出有序序列后序左→右→根4,5,2,6,3,1删除树、求表达式后缀层序按层从左到右1,2,3,4,5,6广度优先搜索、树的可视化六、递归与栈的关系递归遍历的本质是利用了系统调用栈text前序遍历的递归调用过程 preorder(1) ├─ 打印1 ├─ preorder(2) │ ├─ 打印2 │ ├─ preorder(4) │ │ └─ 打印4 │ └─ preorder(5) │ └─ 打印5 └─ preorder(3) ├─ 打印3 └─ preorder(6) └─ 打印6每层递归调用都会把当前状态压栈返回时弹出。理解这个过程对掌握递归非常重要。七、复杂度分析遍历方式时间复杂度空间复杂度前序/中序/后序O(n)O(h)h为树高最坏O(n)层序O(n)O(w)w为最大宽度最坏O(n)八、小结这一篇我们实现了二叉树的链式存储和四种遍历要点说明链式存储节点包含data、left、right前序遍历根→左→右递归实现中序遍历左→根→右递归实现后序遍历左→右→根递归实现层序遍历借助队列按层访问递归三要素终止条件root NULL处理当前层递归调用左右子树下一篇我们讲由遍历序列重构二叉树。九、思考题已知前序遍历序列1 2 4 5 3 6中序遍历序列4 2 5 1 3 6如何还原二叉树递归遍历的空间复杂度为什么是O(h)最坏情况下是多少如何用栈实现非递归的前序遍历层序遍历中如何区分每一层即按层输出而不是一行输出所有欢迎在评论区讨论你的答案。