二叉树的创建和递归遍历
#define _CRT_SECURE_NO_WARNINGS 1 //可能会有人对我写的这句话有疑问,问为什么会有这句话,如果有问题的可以去看我的博客VS提示scanf不安全问题
#include<stdio.h>
#include<stdlib.h>
typedef struct BiNode
{
char data;
struct BiNode *lchild;
struct BiNode *rchild;
}BiNode, *BiTree;
int CreatBiTree(BiTree &T)
{
int m;
scanf("%d", &m);
if (m == -1)
T = NULL;
else
{
T = (BiTree)malloc(sizeof(BiNode));
T->data = m;
printf("请输入%d的左孩子", m);
CreatBiTree(T->lchild);
printf("请输入%d的右孩子", m);
CreatBiTree(T->rchild);
}
return 0;
}
void PrintfBiTree1(BiTree T)
{
if (T ==NULL)
return;
printf("%d", T->data);
PrintfBiTree1(T->lchild);
PrintfBiTree1(T->rchild);
}
void PrintfBiTree2(BiTree T)
{
if (T ==NULL)
return;
PrintfBiTree2(T->lchild);
printf("%d", T->data);
PrintfBiTree2(T->rchild);
}
void PrintfBiTree3(BiTree T)
{
if (T ==NULL)
return;
PrintfBiTree3(T->lchild);
PrintfBiTree3(T->rchild);
printf("%d", T->data);
}
int main()
{
BiTree T;
BiTree *p = (BiTree*)malloc(sizeof(BiNode));
printf("请输入根节点的值,当任何节点为-1时代表为空节点\n");
CreatBiTree(T);
printf("二叉树的先序遍历为:");
PrintfBiTree1(T);
printf("\n");
printf("二叉树的中序遍历为:");
PrintfBiTree2(T);
printf("\n");
printf("二叉树的后序遍历为:");
PrintfBiTree3(T);
printf("\n");
system("pause");
}
前几天我写了二叉树的创建和先序遍历的博客,今天又拿起来二叉树的遍历,想把中序遍历和后序遍历吃透,但是当我拿起程序之后,我发现二叉树的中序遍历和后序遍历,和先序遍历其实是一模一样的,只不过是输出数据的顺序有区别,所以你只需要给每种遍历一个函数,在输出的时候将输出的语句顺序调换就可以了。
void PrintfBiTree1(BiTree T)
{
if (T ==NULL)
return;
printf("%d", T->data);
PrintfBiTree1(T->lchild);
PrintfBiTree1(T->rchild);
}
看着PrintfBiTree1我给三个函数排了序号,看输出语句就可以看出这个函数是先序遍历。先输出T的节点数据,然后再输出他的左子树然后右子树,中左右。
void PrintfBiTree2(BiTree T)
{
if (T ==NULL)
return;
PrintfBiTree2(T->lchild);
printf("%d", T->data);
PrintfBiTree2(T->rchild);
}
再看这个它的输出顺序是左中右,自然就是我们常说的中序遍历,所以在写二叉树的递归遍历的时候,写出来一个其他两个只需要调换输出语句就可以了。
这是程序的运行结果。
如果大家对遍历有问题的话可以翻我前几天的博客,对二叉树的创建和先序遍历有详细的讲解。
好了我要去写二叉树的非递归遍历了。