面试要点：二叉树的前序、中序、后序遍历的深层理解
目录
1.二叉树的结构：
每一个二叉树均可以分为三部分：1.根节点 2.左子树 3.右子树。
比如上图中的A的左右子树分别是B、C，而E的左右子树为NULL、NULL。通常我们把NULL省略。
2.二叉树的前序遍历：
又叫先根遍历，遍历顺序是根节点、左子树、右子树。
上图的前序遍历：A B D NULL NULL E NULL NULL C NULL NULL
省略NULL后：A B D E C
3.二叉树的中序遍历：
遍历顺序：左子树、根节点、右子树
上图的中序遍历：NULL D NULL B NULL E NULL A NULL C NULL
省略NULL后：D B E A C
4.二叉树的后序遍历：
遍历顺序：左子树、右子树、根节点
上图的中序遍历：NULL NULL D NULL NULL E B NULL NULL C A
省略NULL后：D E B C A
5.二叉树前、中、后序的代码实现：
前序遍历函数：
void prev_order(BTNode* root)//前序遍历
{
if (root == NULL)
{
printf("NULL");
return;
}
printf("%c ", root->data);
prev_order(root->left);
prev_order(root->right);
} 
中序遍历函数：
void on_order(BTNode* root)//中序遍历
{
if (root == NULL)
{
printf("NULL\n");
return;
}
prev_order(root->left);
printf("%c ", root->data);
prev_order(root->right);
} 
后序遍历：
void post_order(BTNode* root)//后序遍历
{
if (root == NULL)
{
printf(" NULL \n");
return;
}
prev_order(root->left);
prev_order(root->right);
printf("%c ", root->data);
} 
完整代码：
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDataType x)//开辟空间存储变量
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
newnode->data = x;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}
void prev_order(BTNode* root)//前序遍历
{
if (root == NULL)
{
printf("NULL");
return;
}
printf("%c ", root->data);
prev_order(root->left);
prev_order(root->right);
}
void on_order(BTNode* root)//中序遍历
{
if (root == NULL)
{
printf("NULL\n");
return;
}
prev_order(root->left);
printf("%c ", root->data);
prev_order(root->right);
}
void post_order(BTNode* root)//后序遍历
{
if (root == NULL)
{
printf(" NULL \n");
return;
}
prev_order(root->left);
prev_order(root->right);
printf("%c ", root->data);
}
int main(void)
{
BTNode* n1 = BuyNode('A');
BTNode* n2 = BuyNode('B');
BTNode* n3 = BuyNode('C');
BTNode* n4 = BuyNode('D');
BTNode* n5 = BuyNode('E');
n1->left = n2;
n1->right = n3;
n2->left = n4;
n2->right = n5;
prev_order(n1);
printf("\n");
on_order(n1);
printf("\n");
post_order(n1);
printf("\n");
return 0;
} 代码运行结果截图：
#C/C++#
腾讯开奖372人在聊
查看7道真题和解析