一、二叉树的遍历与建立
首先我们拥有如下二叉树:
要了解二叉树遍历,我们得先了解二叉树的三种遍历方式:前序遍历,中序遍历,后序遍历
1.前序遍历
前序遍历:根,左子树,右子树
遍历的结果就是:1 2 4 8 N N 9 N N 5 10 N N 11 N N 3 6 N N 7 N N
2.中序遍历
中序遍历:左子树 根 右子树
遍历的结果:N 8 N 4 N 9 N 2 N 10 N 5 N 11 N N 6 N 5 N 7 N
3.后序遍历
后续遍历:左子树 右子树 根
遍历的结果:N N 8 N N 9 4 N N 10 N N 11 5 2 N N 6 N N 7 3 1
注意:N是NULL(即不存在次节点)
4.手撕一棵二叉树
那么我们如何用代码实现这样的遍历并打印,我们先可以写一个二叉树
typedef struct BinTreeNode
{
struct BinTreeNode* left;
struct BinTreeNode* right;
int val;
}BTNode;
然后我们创建相应的节点:
BTNode* BuyBTNode(int val)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->val = val;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}
然后我们手撕一棵二叉树
BTNode* CreateTree()
{
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 n1;
}
这样们就创建好一个二叉树了,接下来我们来写如何遍历吧!
5.用函数来完成遍历
1)前序遍历:
void PreOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
printf("%d ", root->val);
PreOrder(root->left);
PreOrder(root->right);
}
按照 根 左子树 右子树 打印如果不为空就继续递归 打印根数据 然后 左子树 最后 右子树 如果为空就打印N然后返回
2)中序遍历
按照 左子树 根 右子树 大体思路如上
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
InOrder(root->left);
printf("%d ", root->val);
InOrder(root->right);
}
3)后序遍历
按照:左子树 右子树 根
void PostOrder(BTNode* root);
{
if (root == NULL)
{
printf("N ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->val);
}
下面我们来进行一下测试:
首先二叉树如图,我们不然得到
前序遍历:1 2 3 N N N 4 5 N N 6 N N
中序遍历:N 3 N 2 N 1 N 5 N 4 N 6 N
后序遍历:N N 3 N 2 N N 5 N N 6 4 2
我们把上面的代码整合一下
#include<stdio.h>
#include<stdlib.h>
typedef struct BinTreeNode
{
struct BinTreeNode* left;
struct BinTreeNode* right;
int val;
}BTNode;
BTNode* BuyBTNode(int val)
{
BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->val = val;
newnode->left = NULL;
newnode->right = NULL;
return newnode;
}
BTNode* CreateTree()
{
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 n1;
}
void PreOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
printf("%d ", root->val);
PreOrder(root->left);
PreOrder(root->right);
}
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
InOrder(root->left);
printf("%d ", root->val);
InOrder(root->right);
}
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->val);
}
int main()
{
BTNode* root = CreateTree();
printf("前序遍历:");
PreOrder(root);
printf("\n");
printf("中序遍历:");
InOrder(root);
printf("\n");
printf("后序遍历:");
PostOrder(root);
printf("\n");
return 0;
}
运行结果:
我们发现结果与我们预期的一致,所以我们完成了二叉树的遍历
标签:遍历,NULL,BTNode,二叉树,printf,数据结构,root,left From: https://blog.csdn.net/2301_80017277/article/details/136974841