<pre name="code" class="cpp">#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include <stdlib.h>
#include <stdio.h>
/*自己来看看一个完整性的二叉树的例子，加深理解*/
#define MAX 100
typedef struct BNode/*二叉树的节点结构*/
{
int data;
struct BNode *l_child;
struct BNode* r_child;
} BNode;
int e,z,i,j,k;//这是一些常用的变量。
BNode *t,*q,*p;
typedef struct//栈的顺序存储结构
{
BNode *a[MAX];
int top;
}sqstack;
typedef struct//循环队列存储结构，用于二叉树的按层次访问
{
BNode *a[MAX];
int front;
int rear;
}squeue;
//这个用于创建一个节点，本来想传递一个参数x作为节点的值，发现这样不好，值是输入的，当作函数参数传递后递归不会用了
BNode *Creat_One()//所以通过scanf从缓冲区扫描比较好
{
BNode *p;
int x;
scanf("%d",&x);
if((p=(BNode*)malloc(sizeof(BNode)))==NULL)//用指针p申请一块内存，因为在堆空间，返回堆空间的地址不会出错
{
printf("创建头节点失败.\n");
return NULL;
}
else
{
p->data=x;
p->l_child=NULL;
p->r_child=NULL;
}
return p;//p所指向的空间是动态申请来的，可以返回。
}
void push(sqstack *s,BNode *x)//这是入栈函数，进一个就指针位置就+1
{
if(s->top==MAX)
{
printf("栈满了.\n");
}
else
{
s->top++;
s->a[s->top]=x;//把x存入
}
}
BNode * pop(sqstack *s)//出栈函数，每次取出一个栈位置指针减去一
{
BNode *x;
if(s->top==0)
{
printf("栈是空的.\n");
}
else
{
x=s->a[s->top];
s->top--;
}
return x;//返回取出的栈的元素
}
/*队列处理函数*///这里是循环队列。省去判断是否假满
void enqueue(squeue *Q,BNode *x)//把x放在队列里面
{
if((Q->rear+1)%MAX==Q->front)//采用取余数省去了判断队列是否假满，空去了一个存储单元
{
printf("队列满了");
}
else
{
Q->a[Q->rear]=x; Q->rear=(Q->rear+1)%MAX;
}
}
BNode *delqueue(squeue*Q)
{ BNode *x;
if(Q->rear==Q->front)
{
printf("队列是空的.\n");
}
else
{
x=Q->a[Q->front];
Q->front=(Q->front+1)%MAX;//防止越界处理 return x;
}
}/*模仿先序递归遍历法建立二叉树*/
BNode *Creat_Bt1()//对比Creat_One函数进行的递归
{ //缺点，递归不断的调用自身，不知道什么什么时候结束，对于每次调用都要对最后的节点复制0程序才知道结束
//输入的数据是2^0+2^1+...2^n个，需要输入0来告诉程序结束的个数是2^(n+1)个
BNode *t; printf("\ndata=");
scanf("%d",&e); if(e==0) t=NULL;
else { t=(BNode*)malloc(sizeof(BNode));
t->data=e; t->l_child=Creat_Bt1();/*获得新的指针值*/
t->r_child=Creat_Bt1(); } return t;}/*非递归*///这是根据二叉树的性质来写的，关键是对性质的理解
/*对于具有N个节点的完全二叉树，如果按照从上到下和从左到有的顺序，
对二叉树的所有节点从1开始按顺序编号 对于任意的序号i的节点有 1.如果i>1，
则序号i的结点的双亲节点的序号是/2 i=1就是根结点无双亲节点 2.如果2i<=n则序号i的结点的左孩子节点的序号是2i,
如果2*i大于n节点无左孩子 3.如果2*i+1<=n序号为i的节点的右孩子的序号2*i+1,否则i的结点无右孩子*/
BNode *Creat_Bt0()
{ BNode *t,*p,*v[20];
printf("\n i data=?");
scanf("%d %d",&i,&e);
while(i!=0&&e!=0)
{
p=(BNode*)malloc(sizeof(BNode));
p->data=e; p->r_child=NULL;
p->l_child=NULL; v[i]=p;
if(i==1)
{
t=p;
}
else { j=i/2; if(i%2==0)
{
v[j]->l_child=p;
} else { v[j]->r_child=p; }
}
printf("\n i data=?");
scanf("%d %d",&i,&e);
} return t;}
/*先根序遍历*/
void preorder(BNode *p)
{ if(p)
{ printf("%3d",p->data);
preorder(p->l_child);
preorder(p->r_child);
}
}
/*中根序遍历，递归*/
void inorder(BNode*p)
{ if(p)
{ inorder(p->l_child);
printf("%3d",p->data);
inorder(p->r_child);
}}
/* 非递归中根遍历*/
void inorder_2(BNode *t)
{ sqstack s; BNode *p;
s.top=0; push(&s,t);
while(s.top!=0)
{ while(s.a[s.top]!=NULL)
{
p=s.a[s.top];
push(&s,p->l_child);
} p=pop(&s); if(s.top!=0)
{ p=pop(&s);
printf("%3d",p->data);
push(&s,p->r_child);
}
}
}
void level(BNode *t)
{ squeue q; BNode *p;
q.front=0; q.rear=0;
enqueue(&q,t);
while(q.rear!=q.front)
{ p=delqueue(&q);
printf("%3d",p->data);
if(p->l_child)enqueue(&q,p->l_child);
if(p->r_child)enqueue(&q,p->r_child);
}
printf("\n");}
int e,z,i,j,k;BNode *t,*q,*p;
void main()
{
do {
printf("\n\n");
printf("\n\n 0.建立二叉树方法0");
printf("\n\n 1.建立二叉树方法1");
printf("\n\n 2.中序递归二叉树");
printf("\n\n 3.中序非递归二叉树");
printf("\n\n 4.按层遍历二叉树");
printf("\n\n 5.结束");
printf("请输入选择：\n");
scanf("%d",&k);
switch(k)
{ case 0:
{
printf("输入负数结束\n");
t=Creat_Bt0(); preorder(t);
break;
}
case 1:
{
printf("依次输入数据，空孩子也要输入0");
t=Creat_Bt1(); preorder(t); break;
}
case 2:
{ printf("中序递归遍历:\n");
inorder(t);
break;
}
case 3:
{
printf("中序非递归遍历:\n");
inorder_2(t);
break;
}
case 4:
{ printf("按层次遍历:\n");
level(t); break; }
case 5:
exit(0);
}
}
while(k>=0&&k<=5); printf("再见\n");
}
