目录
前言
在上一章学习了链式二叉树的前中后序遍历的解析
数据结构 ——— 链式二叉树的前中后序遍历解析-CSDN博客
接下来要学习的是代码实现链式二叉树的前中后序遍历访问
链式二叉树示意图
手搓一个链式二叉树
代码演示：
// 数据类型
typedef int BTDataType;
// 二叉树节点的结构
typedef struct BinaryTreeNode
{
BTDataType data; //每个节点的数据
struct BinaryTreeNode* left; //指向左子树的指针
struct BinaryTreeNode* right; //指向右子树的指针
}BTNode;
// 申请新节点
BTNode* BuyNode(BTDataType x)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
// 判断是否申请成功
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
// 初始化
newnode->data = x;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}
BTNode* CreatBinaryTree()
{
BTNode* n1 = BuyNode(1);
assert(n1);
BTNode* n2 = BuyNode(2);
assert(n2);
BTNode* n3 = BuyNode(3);
assert(n3);
BTNode* n4 = BuyNode(4);
assert(n4);
BTNode* n5 = BuyNode(5);
assert(n5);
BTNode* n6 = BuyNode(6);
assert(n6);
n1->left = n2;
n1->right = n4;
n2->left = n3;
n4->left = n5;
n4->right = n6;
return n1;
}先构建二叉树每个节点的结构，再手动添加并修改指向，以上面的示意图为例
链式二叉树的前序遍历
前序遍历访问顺序：根 -> 左子树 -> 右子树
代码演示：
void PrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return ;
}
// 根 -> 左子树 -> 右子树
printf("%d ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}代码解析：
不论左右子树，当 root 走到 NULL 时就返回
否则就根据前序遍历的顺序再利用递归结构进行遍历
大致走读代码：
因为是前序遍历，所以先打印根的数据
再利用递归传递根的左子树，把传递的左子树节点再次当作根节点打印
再利用递归传递当前根的左子树，直到左子树为空时就返回
但是不是完全结束函数，而是返回上一层，传递当前根的右子树………………
代码验证：
链式二叉树的中序遍历
中序遍历访问顺序：左子树 -> 根 -> 右子树
代码演示：
void MiddleOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
// 左子树 -> 根 -> 右子树
MiddleOrder(root->left);
printf("%d ", root->data);
MiddleOrder(root->right);
}代码解析：
代码的逻辑类似于前序递归遍历，不同的是要根据中序遍历的访问顺序进行遍历
代码验证：
链式二叉树的后序遍历
后序遍历访问顺序：左子树 -> 右子树 -> 根
代码演示：
void AfterOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
// 左子树 -> 右子树 -> 根
AfterOrder(root->left);
AfterOrder(root->right);
printf("%d ", root->data);
}代码解析：
过程类似前中序一样，根据后续的遍历访问顺序进行访问
代码验证：