|
- UID
- 852722
|
#include<stdio.h>
#include<stdlib.h>
#define ELEMTP int
struct node
{
ELEMTPdata;
structnode *lc,*rc;
};
struct node *root;
int m=0;
main()
{
intcord;
structnode* creat();
voidpreorderz(struct node *t);
voidinorder(struct node *t);
voidpostorder(struct node *t);
voiddeletes(struct node *t,struct node *p,struct node *f);
do
{
printf("\n 主菜单 \n");
printf(" 1 建立二叉树 \n");
printf(" 2 先序非递归遍历 \n");
printf(" 3 中序递归遍历 \n");
printf(" 4 后序递归遍历，求叶节点数 \n");
printf(" 5 删除节点 \n");
printf(" 6 结束程序运行 \n");
printf("---------------------------------------\n");
printf("请输入您的选择(1, 2,3, 4, 5, 6)");
scanf("%d",&cord);
switch(cord)
{
case1:
{
root=creat(); // 建立二叉树
printf("建立二叉树程序以执行完，\n");
printf("请返回主菜单，用遍历算法验证程序的正确性 \n");
}break;
case2:
{
preorderz(root);
}break;
case3:
{
inorder(root);
}break;
case4:
{
postorder(root);
}break;
case5:
{
//deletes(root)
}
case6:
{
printf("二叉树程序执行完，再见！\n");
exit(0);
}
}
}while(cord<=6);
}
struct node* creat()
{
structnode *t,*q,*s[30];
inti,j,x;
printf("i,x=");
scanf("%d%d",&i,&x);//i是按满二叉树编号，x节点应有的序号，x是节点的数据
while((i!=0)&&(x!=0))
{
q=(structnode*)malloc(sizeof(struct node));
q->data=x;
q->lc=NULL; q->rc=NULL;
s=q;
if(i==1)
t=q; //t代表树根节点
else
{
j=i/2;//双亲节点的编号
if((i%2)==0)
s[j]->lc=q;
else
s[j]->rc=q;
}
printf("i,x=");
scanf("%d%d",&i,&x);
}
return(t);
}
/*void preorderz(struct node* p)//前序非递归算法
{
structnode *q,*s[30]; //s辅助栈
inttop,bools;
q=p;top=0; //栈顶指针
bools=1; //bools=1为真值继续循环；bools=0为假时栈空，结束循环
do
{
while(q!=NULL)
{
printf("%6d",q->data); //访问节点
top++;
s[top]=q;
q=q->lc;
}
if(top==0)
bools=0;
else
{
q=s[top];
top--;
q=q->rc;
}
}while(bools);
printf("\n");
}//////////////////////////结束preorderz*/
void preorderz(struct node* p)//前序递归遍历
{
if(p!=NULL)
{
printf("%6d",p->data);
inorder(p->lc);
inorder(p->rc);
}
}
void inorder(struct node* p)//中序非递归遍历
{
structnode *s[30],*q;
inttop,bools;
q=p;top=0;
bools=1;
do
{
while(q!=NULL)
{
top++;
s[top]=q;
q=q->lc;
}
if(top==0)
bools=0;
else
{
q=s[top];
top--;
printf("%6d",q->data);
q=q->rc;
}
}while(bools);
}
/*void inorder(struct node* p)
{
if(p!=NULL)
{
inorder(p->lc);
printf("%6d",p->data);
inorder(p->rc);
}
}//////////////////////////结束inorder*/
void postorder(struct node* p)
{
structnode *s[30],*s2[30],*q;
inttop,bools;
q=p;top=0;
bools=1;
do
{
while(q!=NULL)
{
top++;
s[top]=q;
s2[top]=1;
q=q->lc;
}
if(top==0)
bools=0;
else
{
if(s2[top]==1)
{
s2[top]=2;
q=s[top];
q=q->rc;
}
else
{
q=s[top];
s2[top]=0;
top--;
printf("%6d",q->data);
q=NULL;
}
}
}while(bools);
}
void deletes(struct node *t,struct node*p,struct node *f)
{
structnode *s,*q;
intbools=1;
if(p->lc==NULL)
s=p->rc;
elseif(p->rc==NULL)
{
s=p->rc;
while(s->lc!=NULL)
{
q=s;
s=s->rc;
}
if(q==p)
q->rc=s->rc;
else
q->lc=s->rc;
p->data=s->data;
free(s);
bools=0;
}
if(bools==1)
{
if(f==NULL)
t=s;
elseif(f->lc==p)
f->lc=s;
else
f->rc=s;
free(p);
}
}
/*void postorder(struct node* p)
{
if(p!=NULL)
{
postorder(p->lc);
postorder(p->rc);
printf("%6d",p->data);
if(p->lc==NULL&&p->rc==NULL)
m++; //统计叶子节点
}
}//////////////////////////结束postorder*/ |
|
