目录
0.写在前面
1.前序遍历
步骤详解代码实现
2.中序遍历
步骤详解代码实现
3.后序遍历
步骤详解代码实现
0.写在前面
认识二叉树结构最简单的方式就是遍历二叉树。所谓遍历二叉树就是按照某种特定的规则，对二叉树的每一个节点进行访问，且每个节点只访问一次。
二叉树遍历的规则一般有四种：前序遍历、中序遍历、后序遍历和层序遍历。其中，前三种较为简单且实现方式大同小异。
1.前序遍历：先访问根节点，再遍历左右子树；
2.中序遍历：先遍历左子树，再访问根节点，再遍历右子树；
3.后序遍历：先遍历左子树，再遍历右子树，再访问根节点。
简单记忆：前（根，左，右）、中（左，根，右）、后（左，右，根）。
在遍历二叉树之前，首先得拥有一棵二叉树。因为目前还没有学习如何构建二叉树，所以此处我们用最原始的办法——申请N个节点，将它们手动拼接为二叉树。
typedef int BTDataType;
//二叉树节点的结构typedef struct BTNode{BTDataType data;struct BTNode* left;struct BTNode* right;}BTNode;
//定义一个申请新节点的函数BTNode* BuyBTNode(BTDataType data){BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));if (newNode == NULL){perror("malloc fail");exit(-1);}
newNode->data = data;newNode->left = NULL;newNode->right = NULL;
return newNode;}
int main(){//手动申请节点加连接BTNode* n1 = BuyBTNode(1);BTNode* n2 = BuyBTNode(2);BTNode* n3 = BuyBTNode(3);BTNode* n4 = BuyBTNode(4);BTNode* n5 = BuyBTNode(5);BTNode* n6 = BuyBTNode(6);
n1->left = n2;n1->right = n4;n2->left = n3;n4->left = n5;n4->right = n6;return 0;}
1.前序遍历
前序遍历：先访问根节点，再访问左子树，再访问右子树；
void PrevOrder (BTNode* root)为了更好的理解前序遍历的规则，接下来展示一下详细步骤。
步骤详解1.先访问根节点 （data = 1），再访问左子树；
2.再访问左子树的根节点（data = 2），再访问左子树的左子树；
3.依旧先访问根节点（data = 3），此时 n3 节点的左右子树都为 NULL ，则不再往下递归，回到上一层；接着访问上一层的右子树；
4.因为 n2 节点的右子树为 NULL，所以继续返回上一层；访问上一层的右子树；
5.访问右子树的根节点（data = 4），再访问右子树的左子树；先左子树的根节点（data = 5），n5 节点的左右子树都为 NULL，返回上一层访问右子树（data = 6），同样 n6 节点的左右子树都为 NULL，返回上一层。
至此每个节点都访问完毕，总体的访问顺序是这样的：
按照访问顺序打印的结果应该是（空节点用 NULL 表示）：
代码实现按照前序遍历的逻辑，前序遍历的实现肯定是离不开递归。
void PrevOrder(BTNode* root){if (root == NULL){printf("NULL ");//空节点用 NULL 表示return;}
printf("%d ", root->data);//前序在前PrevOrder(root->left);PrevOrder(root->right);}
运行程序，看结果是否与之前推理的结果一致：int main(){//手动申请节点加连接BTNode* n1 = BuyBTNode(1);BTNode* n2 = BuyBTNode(2);BTNode* n3 = BuyBTNode(3);BTNode* n4 = BuyBTNode(4);BTNode* n5 = BuyBTNode(5);BTNode* n6 = BuyBTNode(6);
n1->left = n2;n1->right = n4;n2->left = n3;n4->left = n5;n4->right = n6;
PrevOrder(n1);return 0;}
2.中序遍历
前中后序三种遍历大同小异，实现代码也几乎相同。
void InOrder(BTNode* root)步骤详解
代码实现void InOrder(BTNode* root){if (root == NULL){printf("NULL ");return;}
PrevOrder(root->left);printf("%d ", root->data);//中序在中PrevOrder(root->right);}
3.后序遍历
步骤详解参考1、2。
代码实现void PostOrder(BTNode* root){if (root == NULL){printf("NULL ");return;}
PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);//后序在后}
到此这篇关于C语言之二叉树的遍历的文章就介绍到这了,更多相关二叉树的遍历内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家！
您可能感兴趣的文章:C语言数据结构之二叉树详解C语言数据结构二叉树先序、中序、后序及层次四种遍历详细了解C语言二叉树的建立与遍历C语言二叉树的三种遍历方式的实现及原理C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查找,统计个数,比较,求深度】C语言非递归后序遍历二叉树C语言数据结构之二叉树的非递归后序遍历算法