#include <stdio.h>
#include<stdlib.h>
#define null 0
#define maxsize 100
typedef struct tree
{ /*声明树的结构*/
struct tree *left; /*存放左子树的指针*/
struct tree *right; /*存放又子树的指针*/
int data; /*存放节点的内容*/
} treenode, * btree; /*声明二叉树的链表*/
btree q[maxsize];
int count;
/* 在二叉排序树中插入结点*/
btree insertnode(btree root,int node)
{
btree newnode; /*声明新结点指针*/
btree currentnode; /*声明当前结点指针*/
btree parentnode; /*声明父结点指针*/
newnode=(btree)malloc(sizeof(treenode));/*建立新结点的内存空间*/
newnode->data =node; /*结点的内容*/
newnode->left =null; /*设置右指针初值*/
newnode->right =null; /*设置左指针初值*/
if(root==null)
return newnode;
else
{
currentnode=root;
while(currentnode!=null)
{/*寻找要插入的位置*/
parentnode =currentnode;
if(currentnode->data >node )
currentnode=currentnode->left ;
else
currentnode=currentnode->right ;
}
if(parentnode->data >node)
parentnode->left =newnode;
else
parentnode->right =newnode;
return root;
}
}
/*建立二叉树 */
btree createbtree(int *data,int len)
{
btree root=null; /*根结点*/
int i;
for(i=0;i<len;i++)/*建立二叉排序树*/
root=insertnode(root,data[i]);
return root;
}
/* 中序遍历打印二叉排序树*/
void inorderbtree(btree root)
{
btree p=root;
if(p!=null){
inorderbtree(p->left );
printf("%3d",p->data );
inorderbtree(p->right );
}
}
typedef btree ElemType ;
/*typedef char ElemType ; */
/*定义队列结点类型*/
typedef struct QueueNode
{
ElemType data;
struct QueueNode *next;
} QueueNode;
/*定义队列*/
typedef struct linkQueue
{
QueueNode * front;
QueueNode * rear;
}linkQueue;
/*初始化队列*/
void initQueue(linkQueue * q)
{
q->front=q->rear =null;
}
/*判断队列是否为空*/
int QueueEmpty(linkQueue * Q)
{
return (Q->front==null)&&(Q->rear==null);
/*实际上只须判断队头指针是否为空即可*/
}
/*入队操作*/
void EnQueue(linkQueue *Q,ElemType x)
{ /*将元素x插入链队列尾部*/
QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode)); /*申请新结点*/
p->data=x; p->next=null;
if(QueueEmpty(Q)) /*将x插入空队列*/
Q->front=Q->rear=p;
else
{ /*x插入非空队列的尾*/
Q->rear->next=p; /*p链到原队尾结点后*/
Q->rear=p; /*队尾指针指向新的尾*/
}
}
/*出队操作*/
ElemType DeQueue (linkQueue *Q)
{
ElemType x;
QueueNode *p;
if(QueueEmpty(Q))
{
printf("Queue underflow");/*下溢*/
exit(1) ;
}
p=Q->front; /*指向对头结点*/
x=p->data; /*保存对头结点的数据*/
Q->front=p->next; /*将对头结点从链上摘下*/
if(Q->rear==p)/*原队中只有一个结点，删去后队列变空，此时队头指针已为空*/
Q->rear=NULL;
free(p); /*释放被删队头结点*/
return x; /*返回原队头数据*/
}
void visit(btree p)
{
if(p->data!=1)
printf("%3d",p->data);
else
printf("%3c",p->data);
}
//将原二叉树补全使其成为完全二叉树后按层次遍历序列输出
void breadthFirst2(btree root)
{
btree p,tmp;
linkQueue * q;
tmp=(treenode *)malloc(sizeof(treenode));
q=(linkQueue *)malloc(sizeof(linkQueue));
tmp->data=1;
initQueue(q);
p=root;
if(p!=null)
{
EnQueue(q,p);
while(!QueueEmpty(q))
{
p=DeQueue(q);
visit(p);
if(p->data!=1)
{
if(p->left!=null)
EnQueue(q,p->left);
else
EnQueue(q,tmp);
if(p->right!=null)
EnQueue(q,p->right);
else
EnQueue(q,tmp);
}
}
}
}
//层次遍历输出
void breadthFirst(btree root)
{
btree p;
linkQueue * q;
q=(linkQueue *)malloc(sizeof(linkQueue));
initQueue(q);
p=root;
if(p!=null)
{
EnQueue(q,p);
while(!QueueEmpty(q))
{
p=DeQueue(q);
visit(p);
if(p->left!=null)
EnQueue(q,p->left);
if(p->right!=null)
EnQueue(q,p->right);
}
}
}
//用递归算法输出二叉树的叶子结点
void leafprint(btree bt)
{
if(bt)
{
if(bt->left==NULL&&bt->right==NULL)
printf(" %d ",bt->data);
leafprint(bt->left);
leafprint(bt->right);
}
}
//用递归算法求二叉树的叶子节点个数
int leafcount(btree bt)
{
if(bt)
{
leafcount(bt->left);
leafcount(bt->right);
if(bt->left==NULL&&bt->right==NULL)
count++;
}
return count;
}
//用递归算法求二叉树的深度
int deeptree(btree bt)
{
int hl,hr,max;
if(bt)
{
hl=deeptree(bt->left);
hr=deeptree(bt->right);
max=hl>hr?hl:hr;
return max+1;
}
else
return 0;
}
//用非递归算法实现二叉树的先序遍历输出
void xianxu(btree bt)
{
btree p;
int top=-1;
if(bt)
{
top++; //根结点入栈
q[top]=bt;
while(top>-1) //栈不为空时循环
{
p=q[top]; //出栈并访问该结点
top--;
printf(" %d ",p->data);
if(p->right) //右孩子结点入栈
{
top++;
q[top]=p->right;
}
if(p->left) //左孩子结点入栈
{
top++;
q[top]=p->left;
}
}
}
}
//用非递归算法实现二叉树的中线序遍历输出
void zhongxu(btree bt)
{
btree p;
int top=-1;
if(bt)
{
p=bt;
while(top>-1||p)
{
while(p) //扫描*p的所有左结点并入栈
{
top++;
q[top]=p;
p=p->left;
}
if(top>-1)
{
p=q[top]; //出栈*p结点
top--;
printf(" %d ",p->data); //访问之
p=p->right; //扫描*p的右孩子结点
}
}
}
}
//用非递归算法实现二叉树的后序遍历输出
void houxu(btree bt)
{
btree p;
int top=-1,flag; //栈顶指针初始化
if(bt)
{
do
{
while(bt) //将bt的所有左结点入栈
{
top++;
q[top]=bt;
bt=bt->left;
}
p=NULL; //p指向栈顶结点的前一个已访问的结点
flag=1; //设置bt的访问标记为已访问过
while(top>-1&&flag)
{
bt=q[top]; //栈顶元素出栈
if(bt->right==p) //右孩子不存在或右孩子已被访问过
{
printf(" %d ",bt->data); //访问bt结点
top--;
p=bt; //p指向被访问的结点
}
else
{
bt=bt->right; //bt指向右孩子结点
flag=0; //设置未被访问的标记
}
}
}while(top>-1);
}
}
//用递归算法实现二叉树的先序遍历输出
void preorder(btree bt)
{
if(bt)
{
printf(" %d ",bt->data);
preorder(bt->left);
preorder(bt->right);
}
}
//用递归算法实现二叉树的中序遍历输出
void inorder(btree bt)
{
if(bt)
{
inorder(bt->left);
printf(" %d ",bt->data);
inorder(bt->right);
}
}
//用递归算法实现二叉树的后续遍历输出
void postorder(btree bt)
{
if(bt)
{
postorder(bt->left);
postorder(bt->right);
printf(" %d ",bt->data);
}
}
void main()
{
int nodelist[maxsize],i,n;
btree root;
int k;
printf("--------------------------------------------------------\n");
printf("\n* * * * 您好!欢迎您使用二叉树的操作实现系统! * * * *\n");
printf("\n--------------------------------------------------------\n");
printf("*******请选择您要进行的操作*********\n");
do{
printf(" 1.......创建二叉树\n");
printf(" 2.......分别用递归和非递归先序遍历二叉树\n");
printf(" 3.......分别用递归和非递归中序遍历二叉树\n");
printf(" 4.......分别用递归和非递归后序遍历二叉树\n");
printf(" 5.......求二叉树的高度\n");
printf(" 6.......层次遍历二叉树\n");
