二叉树可以分为左子树,右子树和根节点。同时左子树和右子树又可以分为新的左子树和右子树加上新的根节点,以此类推。
二叉树的前序,中序,后序遍历也叫前根遍历,中根遍历,后根遍历或者前序遍历,中序遍历,后序遍历,代码实现采用递归。
一棵二叉树如下: (无孩子节点处为NULL,如D,E的左右孩子和C的右边孩子为NULL)。
前根遍历:顺序是根,左子树,右子树:A B D NULL NULL E NULL NULL C F NULL NULL NULL
中根遍历:顺序是左子树,根,右子树:NULL D NULL B NULL E NULL A NULL F NULL C NULL
后根遍历:顺序是左子树,右子树根,:NULL NULL D NULL NULL E B NULL NULL F NULL C A
代码展示:
#include "stdio.h"
#include "stdlib.h"
typedef int BinaryTreeData;
struct BinaryTreeNode {
BinaryTreeData val;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
};
//创建树节点
struct BinaryTreeNode* BinaryTreeCreatNode(BinaryTreeData x)
{
struct BinaryTreeNode* Node = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
if (Node == NULL)
{
printf("malloc fail");
exit(-1);
}
Node->val = x;
Node->left = Node->right = NULL;
return Node;
}
//二叉树前序遍历
void preorder(struct BinaryTreeNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%c ", root->val);
preorder(root->left);
preorder(root->right);
}
//二叉树中序遍历
void inorder(struct BinaryTreeNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
inorder(root->left);
printf("%c ", root->val);
inorder(root->right);
}
//二叉树后序遍历
void postorder(struct BinaryTreeNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
postorder(root->left);
postorder(root->right);
printf("%c ", root->val);
}
int main()
{
struct BinaryTreeNode* A = BinaryTreeCreatNode('A');
struct BinaryTreeNode* B = BinaryTreeCreatNode('B');
struct BinaryTreeNode* C = BinaryTreeCreatNode('C');
struct BinaryTreeNode* D = BinaryTreeCreatNode('D');
struct BinaryTreeNode* E = BinaryTreeCreatNode('E');
struct BinaryTreeNode* F = BinaryTreeCreatNode('F');
A->left = B;
B->left = D;
A->right = C;
B->right = E;
C->left = F;
preorder(A);//前序遍历
printf("\n");
inorder(A);//中序遍历
printf("\n");
postorder(A);//后序遍历
printf("\n");
return 0;
}
结果展示: