二叉树前中后序遍历 - 代码实现思路与图解1. 项目概述本项目实现了二叉树的三种遍历方式前序遍历、中序遍历和后序遍历均采用递归实现。2. 数据结构定义2.1 二叉树节点结构typedefcharBTDataType;typedefstructBinaryTreeNode{structBinaryTreeNode*left;// 指向左孩子的指针structBinaryTreeNode*right;// 指向右孩子的指针BTDataType data;// 数据元素}BTNode;结构说明data存储节点数据字符类型left指向左子节点的指针right指向右子节点的指针3. 二叉树构建过程3.1 手动构造二叉树BTNode*CreateTree(){BTNode*nodeaBuyBTNode(a);BTNode*nodebBuyBTNode(b);BTNode*nodecBuyBTNode(c);BTNode*nodedBuyBTNode(d);BTNode*nodeeBuyBTNode(e);BTNode*nodefBuyBTNode(f);nodea-leftnodeb;nodea-rightnodec;nodeb-leftnoded;nodeb-rightnodee;nodec-rightnodef;returnnodea;}3.2 构造的二叉树结构a / \ b c / \ \ d e f4. 遍历实现思路4.1 前序遍历Pre-order Traversal访问顺序根节点 → 左子树 → 右子树voidPreorder(BTNode*root){if(rootNULL){printf(NULL );return;}printf(%c ,root-data);// 1. 访问根节点Preorder(root-left);// 2. 递归遍历左子树Preorder(root-right);// 3. 递归遍历右子树}前序遍历结果a b d e c f4.2 中序遍历In-order Traversal访问顺序左子树 → 根节点 → 右子树voidInorder(BTNode*root){if(rootNULL){printf(NULL );return;}Inorder(root-left);// 1. 递归遍历左子树printf(%c ,root-data);// 2. 访问根节点Inorder(root-right);// 3. 递归遍历右子树}中序遍历结果d b e a c f4.3 后序遍历Post-order Traversal访问顺序左子树 → 右子树 → 根节点voidPostorder(BTNode*root){if(rootNULL){printf(NULL );return;}Postorder(root-left);// 1. 递归遍历左子树Postorder(root-right);// 2. 递归遍历右子树printf(%c ,root-data);// 3. 访问根节点}后序遍历结果d e b f c a5. 递归执行过程图解5.1 前序遍历递归展开图Preorder(a) ├── printf(a ) // 访问根节点a ├── Preorder(b) │ ├── printf(b ) // 访问节点b │ ├── Preorder(d) │ │ ├── printf(d ) // 访问叶子节点d │ │ ├── Preorder(NULL) → 打印NULL并返回 │ │ └── Preorder(NULL) → 打印NULL并返回 │ └── Preorder(e) │ ├── printf(e ) // 访问叶子节点e │ ├── Preorder(NULL) → 打印NULL并返回 │ └── Preorder(NULL) → 打印NULL并返回 └── Preorder(c) ├── printf(c ) // 访问节点c ├── Preorder(NULL) → 打印NULL并返回 └── Preorder(f) ├── printf(f ) // 访问叶子节点f ├── Preorder(NULL) → 打印NULL并返回 └── Preorder(NULL) → 打印NULL并返回输出结果a b d NULL NULL e NULL NULL c NULL f NULL NULL5.2 中序遍历递归展开图Inorder(a) ├── Inorder(b) │ ├── Inorder(d) │ │ ├── Inorder(NULL) → 打印NULL并返回 │ │ ├── printf(d ) // 访问叶子节点d │ │ └── Inorder(NULL) → 打印NULL并返回 │ ├── printf(b ) // 访问节点b │ └── Inorder(e) │ ├── Inorder(NULL) → 打印NULL并返回 │ ├── printf(e ) // 访问叶子节点e │ └── Inorder(NULL) → 打印NULL并返回 ├── printf(a ) // 访问根节点a └── Inorder(c) ├── Inorder(NULL) → 打印NULL并返回 ├── printf(c ) // 访问节点c └── Inorder(f) ├── Inorder(NULL) → 打印NULL并返回 ├── printf(f ) // 访问叶子节点f └── Inorder(NULL) → 打印NULL并返回输出结果NULL d NULL b NULL e NULL a NULL c NULL f NULL5.3 后序遍历递归展开图Postorder(a) ├── Postorder(b) │ ├── Postorder(d) │ │ ├── Postorder(NULL) → 打印NULL并返回 │ │ ├── Postorder(NULL) → 打印NULL并返回 │ │ └── printf(d ) // 访问叶子节点d │ ├── Postorder(e) │ │ ├── Postorder(NULL) → 打印NULL并返回 │ │ ├── Postorder(NULL) → 打印NULL并返回 │ │ └── printf(e ) // 访问叶子节点e │ └── printf(b ) // 访问节点b ├── Postorder(c) │ ├── Postorder(NULL) → 打印NULL并返回 │ ├── Postorder(f) │ │ ├── Postorder(NULL) → 打印NULL并返回 │ │ ├── Postorder(NULL) → 打印NULL并返回 │ │ └── printf(f ) // 访问叶子节点f │ └── printf(c ) // 访问节点c └── printf(a ) // 访问根节点a输出结果NULL NULL d NULL NULL e b NULL NULL f c a6. 核心要点总结6.1 递归三要素递归终止条件节点为空时停止当前层操作打印节点数据递归调用分别调用左子树和右子树的遍历函数6.2 三种遍历的区别遍历方式访问顺序输出结果前序遍历根→左→右a b d e c f中序遍历左→根→右d b e a c f后序遍历左→右→根d e b f c a6.3 时间复杂度分析时间复杂度O(n)每个节点恰好被访问一次空间复杂度O(h)递归栈的深度h为树的高度7. 代码优化建议去掉NULL打印实际应用中通常不需要打印NULL非递归实现使用栈模拟递归过程层序遍历使用队列实现广度优先遍历文档说明本文档基于代码实现详细解释了二叉树三种遍历方式的递归思路和执行过程。
二叉树前中后序遍历 - 代码实现思路与图解1. 项目概述本项目实现了二叉树的三种遍历方式前序遍历、中序遍历和后序遍历均采用递归实现。2. 数据结构定义2.1 二叉树节点结构typedefcharBTDataType;typedefstructBinaryTreeNode{structBinaryTreeNode*left;// 指向左孩子的指针structBinaryTreeNode*right;// 指向右孩子的指针BTDataType data;// 数据元素}BTNode;结构说明data存储节点数据字符类型left指向左子节点的指针right指向右子节点的指针3. 二叉树构建过程3.1 手动构造二叉树BTNode*CreateTree(){BTNode*nodeaBuyBTNode(a);BTNode*nodebBuyBTNode(b);BTNode*nodecBuyBTNode(c);BTNode*nodedBuyBTNode(d);BTNode*nodeeBuyBTNode(e);BTNode*nodefBuyBTNode(f);nodea-leftnodeb;nodea-rightnodec;nodeb-leftnoded;nodeb-rightnodee;nodec-rightnodef;returnnodea;}3.2 构造的二叉树结构a / \ b c / \ \ d e f4. 遍历实现思路4.1 前序遍历Pre-order Traversal访问顺序根节点 → 左子树 → 右子树voidPreorder(BTNode*root){if(rootNULL){printf(NULL );return;}printf(%c ,root-data);// 1. 访问根节点Preorder(root-left);// 2. 递归遍历左子树Preorder(root-right);// 3. 递归遍历右子树}前序遍历结果a b d e c f4.2 中序遍历In-order Traversal访问顺序左子树 → 根节点 → 右子树voidInorder(BTNode*root){if(rootNULL){printf(NULL );return;}Inorder(root-left);// 1. 递归遍历左子树printf(%c ,root-data);// 2. 访问根节点Inorder(root-right);// 3. 递归遍历右子树}中序遍历结果d b e a c f4.3 后序遍历Post-order Traversal访问顺序左子树 → 右子树 → 根节点voidPostorder(BTNode*root){if(rootNULL){printf(NULL );return;}Postorder(root-left);// 1. 递归遍历左子树Postorder(root-right);// 2. 递归遍历右子树printf(%c ,root-data);// 3. 访问根节点}后序遍历结果d e b f c a5. 递归执行过程图解5.1 前序遍历递归展开图Preorder(a) ├── printf(a ) // 访问根节点a ├── Preorder(b) │ ├── printf(b ) // 访问节点b │ ├── Preorder(d) │ │ ├── printf(d ) // 访问叶子节点d │ │ ├── Preorder(NULL) → 打印NULL并返回 │ │ └── Preorder(NULL) → 打印NULL并返回 │ └── Preorder(e) │ ├── printf(e ) // 访问叶子节点e │ ├── Preorder(NULL) → 打印NULL并返回 │ └── Preorder(NULL) → 打印NULL并返回 └── Preorder(c) ├── printf(c ) // 访问节点c ├── Preorder(NULL) → 打印NULL并返回 └── Preorder(f) ├── printf(f ) // 访问叶子节点f ├── Preorder(NULL) → 打印NULL并返回 └── Preorder(NULL) → 打印NULL并返回输出结果a b d NULL NULL e NULL NULL c NULL f NULL NULL5.2 中序遍历递归展开图Inorder(a) ├── Inorder(b) │ ├── Inorder(d) │ │ ├── Inorder(NULL) → 打印NULL并返回 │ │ ├── printf(d ) // 访问叶子节点d │ │ └── Inorder(NULL) → 打印NULL并返回 │ ├── printf(b ) // 访问节点b │ └── Inorder(e) │ ├── Inorder(NULL) → 打印NULL并返回 │ ├── printf(e ) // 访问叶子节点e │ └── Inorder(NULL) → 打印NULL并返回 ├── printf(a ) // 访问根节点a └── Inorder(c) ├── Inorder(NULL) → 打印NULL并返回 ├── printf(c ) // 访问节点c └── Inorder(f) ├── Inorder(NULL) → 打印NULL并返回 ├── printf(f ) // 访问叶子节点f └── Inorder(NULL) → 打印NULL并返回输出结果NULL d NULL b NULL e NULL a NULL c NULL f NULL5.3 后序遍历递归展开图Postorder(a) ├── Postorder(b) │ ├── Postorder(d) │ │ ├── Postorder(NULL) → 打印NULL并返回 │ │ ├── Postorder(NULL) → 打印NULL并返回 │ │ └── printf(d ) // 访问叶子节点d │ ├── Postorder(e) │ │ ├── Postorder(NULL) → 打印NULL并返回 │ │ ├── Postorder(NULL) → 打印NULL并返回 │ │ └── printf(e ) // 访问叶子节点e │ └── printf(b ) // 访问节点b ├── Postorder(c) │ ├── Postorder(NULL) → 打印NULL并返回 │ ├── Postorder(f) │ │ ├── Postorder(NULL) → 打印NULL并返回 │ │ ├── Postorder(NULL) → 打印NULL并返回 │ │ └── printf(f ) // 访问叶子节点f │ └── printf(c ) // 访问节点c └── printf(a ) // 访问根节点a输出结果NULL NULL d NULL NULL e b NULL NULL f c a6. 核心要点总结6.1 递归三要素递归终止条件节点为空时停止当前层操作打印节点数据递归调用分别调用左子树和右子树的遍历函数6.2 三种遍历的区别遍历方式访问顺序输出结果前序遍历根→左→右a b d e c f中序遍历左→根→右d b e a c f后序遍历左→右→根d e b f c a6.3 时间复杂度分析时间复杂度O(n)每个节点恰好被访问一次空间复杂度O(h)递归栈的深度h为树的高度7. 代码优化建议去掉NULL打印实际应用中通常不需要打印NULL非递归实现使用栈模拟递归过程层序遍历使用队列实现广度优先遍历文档说明本文档基于代码实现详细解释了二叉树三种遍历方式的递归思路和执行过程。
