首先本次代码实现的是将已经定义好的数值按二叉树的前序、中序、后序输出(非键盘直接输入!!!!)
本人用到的编辑软件是Mac的Xcode下的C++文件编写,如果用Xcode C文件写时引用(&)方法不能识别,windows用户可以直接在C语言文件下用。
该程序的主要功能实现是用一个数组存放已经规定好要生成二叉树的值,通过引用传入一个值,将这个值作为存放二叉树值的数组下标,然后每次递归一次该值做加加,对应的数组值后移一位然后实现对树的枝进行扩展。(完整代码在最后,需要可直接复制)
首先是结构体定义了
typedef struct BiTnode
{
student data;
struct BiTnode *lchild,*rchild;
}BiTnode,*BiTree;
这次是老师要求的写学生结构体,所以我这里的数据域是定义了一个student结构体,这个结构体中有两个变量,一个是姓名,一个是学号
typedef struct
{
int no;
int sco;
}student;
接下来就是创建二叉树的过程,主要使用到了递归原理(如果递归不熟练的先手动写一次斐波那契数列)
这里引用了树结构体还有就是传入一个定值,为后续遍历数组中树的值用,这里用的是a来表示;
int CreatBiTree(BiTree &B,int &a)
{
student t[maxTSize]={{110,80},{111,85},{112,90},{0,0},{0,0},{113,91},{0,0},{0,0},{114,92},{0,0},{115,90},{0,0},{0,0}};
if(t[a].no==0){
B=NULL;
a++;
}
else
{
B=new BiTnode;
B->data=t[a];
a++;
CreatBiTree(B->lchild,a);
CreatBiTree(B->rchild,a);}
return 0;
}
这里student t[]数组就是用来存放你要生成的二叉树的所有值,你可以自己再添加删减,这里有一个for循环用来判断是否其左孩子或右孩子存在;如果该值为0就说明该分枝不存在所以此时a++,为了数组能继续往后移动,继续扩展树枝。如果该值存在说明该结点又相当于一颗小树继续往后遍历用到递归调用重新在创建新的小树。下面提供简单的生成树效果:
接下来就是前中后序输出了,前中后序主要不同就是根节点输出的顺序决定,根节点先输出就为先序,最后输出根节点就是后序,这里输出也主要是用到递归原理,前序输出就是先输出根节点然后输出左子树接下来是右子树,而左子树又相当于是一个树,先输出根节点然后再输出左子树,右子树同理,不管是什么类型的二叉树,前序输出代码几乎都是这样的:
int PrintxianBiTree(BiTree &B)
{
if (B==NULL){
return 0;}
else
printf("%d %d\t",B->data.no,B->data.sco);
PrintxianBiTree(B->lchild);
PrintxianBiTree(B->rchild);
return 0;
}
中序遍历就是先输出左子树再输出根节点最后输出右子树,输出左子树时又将左子树当成一颗小树,也是先输出小树的左子树,以此类推,代码实现如下:
int PrintzhongBiTree(BiTree &B)
{
if (B==NULL){
return 0;}
else
PrintzhongBiTree(B->lchild);
printf("%d %d\t",B->data.no,B->data.sco);
PrintzhongBiTree(B->rchild);
return 0;
}
后续便利就是先输出左子树接下来输出右子树,最后输出根节点,输出规律一样,代码如下:
int PrinthouBiTree(BiTree &B)
{
if (B==NULL){
return 0;}
else
PrinthouBiTree(B->lchild);
PrinthouBiTree(B->rchild);
printf("%d %d\t",B->data.no,B->data.sco);
return 0;
}
以上就是我自己完成的非键盘直接输入实现二叉树前中后序输出的程序,希望可以帮助到大家,有任何问题可以留言,操作步骤录了视频有需要可以私发你邮箱!
程序源码:
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#define maxTSize 100
typedef int TElemType;
typedef struct
{
int no;
int sco;
}student;
typedef struct BiTnode
{
student data;
struct BiTnode *lchild,*rchild;
}BiTnode,*BiTree;
int CreatBiTree(BiTree &B,int &a)
{
student t[maxTSize]={{110,80},{111,85},{112,90},{0,0},{0,0},{113,91},{0,0},{0,0},{114,92},{0,0},{115,90},{0,0},{0,0}};
if(t[a].no==0){
B=NULL;
a++;
}
else
{
B=new BiTnode;
B->data=t[a];
a++;
CreatBiTree(B->lchild,a);
CreatBiTree(B->rchild,a);}
return 0;
}
int PrintxianBiTree(BiTree &B)
{
if (B==NULL){
return 0;}
else
printf("%d %d\t",B->data.no,B->data.sco);
PrintxianBiTree(B->lchild);
PrintxianBiTree(B->rchild);
return 0;
}
int PrintzhongBiTree(BiTree &B)
{
if (B==NULL){
return 0;}
else
PrintzhongBiTree(B->lchild);
printf("%d %d\t",B->data.no,B->data.sco);
PrintzhongBiTree(B->rchild);
return 0;
}
int PrinthouBiTree(BiTree &B)
{
if (B==NULL){
return 0;}
else
PrinthouBiTree(B->lchild);
PrinthouBiTree(B->rchild);
printf("%d %d\t",B->data.no,B->data.sco);
return 0;
}
int main()
{
BiTree B;
int a=0;
CreatBiTree(B,a);
printf("\n前序遍历为:\n");
PrintxianBiTree(B);
printf("\n中序遍历为:\n");
PrintzhongBiTree(B);
printf("\n后序遍历为:\n");
PrinthouBiTree(B);
return 0;
}