C语言实现二叉树存储

Question

怎么实现将内容存储到二叉树我用了以下结构
struct tree
{
int num;
struct tree *nextleft;
struct tree *nextright;
};
我想先输入一个头(head)然后分2个孩子
然后2个孩子分别又进行左右子孩子这样一直下去
如果我一个左一个右的话他这样输下去是不会是满二叉树的,这样一行只有一个孩子(如下图看1这个标志代表孩子)
..........1...........
......1.......0.......
....0...1...0....0....
上面那个图只我自己的程序设计出来的，我想设计出满二叉树怎么存储存储不来－ －！

Answer 1

//dev c++

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
typedef struct node
{
int data;//节点信息
int no;
struct node *lchild;//左孩子
struct node *rchild;//右孩子
}BTnode;

void Init(BTnode *&b)//初始化
{b=NULL;}

static int count=1;
int Insert(BTnode *&b,int m)//插入操作
{
BTnode *q;
if(count==1)
{b=(BTnode*)malloc(sizeof(BTnode));
b->data=m;
b->no=count;
b->lchild=b->rchild=NULL;
count++;
}
else if(b!=NULL)
{if(b->no!=count/2)
{
if(Insert(b->lchild,m)==0)return 0;
if(Insert(b->rchild,m)==0)return 0;
}
else
{
q=(BTnode*)malloc(sizeof(BTnode));
q->data=m;
q->no=count;
q->lchild=q->rchild=NULL;
if(count%2==0)b->lchild=q;
else b->rchild=q;
count++;
return 0;
}
}

}

static char s[1024][1024],a[1024];
static int n;
int output(BTnode *&b,int i)//层次输出
{
if(n<i)n=i;
BTnode *p=b;
if(p!=NULL)
{
itoa(p->data,a,10);
strcpy(s[i],a);
output(p->lchild,2*i+1);
output(p->rchild,2*(i+1));
}
else strcpy(s[i],"N");
}

void xianxu(BTnode*&b)//先序
{
BTnode *p=b;
if(p!=NULL)
{
printf("%d ",p->data);
xianxu(p->lchild);
xianxu(p->rchild);
}
}

void zhongxu(BTnode *&b)//中序
{
BTnode *p=b;
if(p!=NULL)
{
zhongxu(p->lchild);
printf("%d ",p->data);
zhongxu(p->rchild);
}
}

void houxu(BTnode *&b)//后序
{
BTnode *p=b;
if(p!=NULL)
{
houxu(p->lchild);
houxu(p->rchild);
printf("%d ",p->data);
}
}

void menu()
{
BTnode *b;
Init(b);
int i,j,k,y,m;
while(1)
{
printf("*****************************************\n\n");
printf("*************二叉数功能菜单**************\n");
printf("*************1.插入整数 ************\n");
printf("*************2.层次输出二叉树************\n");
printf("*************3.先序遍历 ************\n");
printf("*************4.中序遍历 ************\n");
printf("*************5.后序遍历 ************\n");
printf("*************6.退出 ************\n\n");
printf("*****************************************\n\n");
printf("请选择：");
scanf("%d",&y);
switch(y)
{
case 1:printf("\n请输入整数：");scanf("%d",&m);Insert(b,m);break;
case 2:i=0;output(b,i);printf("N代表空节点\n");
for(int j=0;j<=n;j++)
{
printf("%s ",s[j]);
for(k=1;(int)pow(2,k)-2<j;k++);
if((int)pow(2,k)-2==j)printf("\n");
}
break;
case 3:xianxu(b);break;
case 4:zhongxu(b);break;
case 5:houxu(b);break;
case 6:exit(0);break;
default:printf("\n输入错误！");break;
}
printf("\n\n");
}
}

int main()
{
menu();
system("pause");
}