C语言二叉树排序的一道题目

Question

九、（15分）二叉树排序方法如下:
1）将第一个数据放在树根。
2）将随后读入的数据与树根中的数据相比较，若比树根大，则置于右子树，反之则置于左子树，建成一棵二叉树；
3）利用中序遍历打印排序结果。
试用C语言编写二叉树的排序程序，并分析其算法复杂性。

Answer 1

#include<stdio.h>
#include<stdlib.h>
#define Maxsize 100
typedef char elemtype;
typedef struct node
{ elemtype data;
struct node* lchild;
struct node* rchild;
}BTNode;

#include<stdio.h>
#include<stdlib.h>
#define Maxsize 100
typedef char elemtype;

int BTWidth(BTNode *b)
{ struct
{ int lno;
BTNode *p;
}Qu[Maxsize];
int front,rear;
int lnum,max,i,n;
front=rear=0;
if(b!=NULL)
{ rear++;
Qu[rear].p=b;
Qu[rear].lno=1;
while(rear!=front)
{ front++;
b=Qu[front].p;
lnum=Qu[front].lno;
if(b->lchild!=NULL)
{ rear++;
Qu[rear].p=b->lchild;
Qu[rear].lno=lnum+1;
}
if(b->rchild!=NULL)
{ rear++;
Qu[rear].p=b->rchild;
Qu[rear].lno=lnum+1;
}
}
max=0;
lnum=1;
i=0;
while(i<=rear)
{ n=0;
while(i<=rear&&Qu[i].lno==lnum)
{ n++;
i++;
}
lnum=Qu[i].lno;
if(n>max)
max=n;
}
return max;
}
else
return 0;
}

int Btnodedepth(BTNode *b)
{ int h1,h2;
if(!b)return 0;
if(!b->lchild&&!b->rchild)
return 1;
else
{ h1=Btnodedepth(b->lchild);
h2=Btnodedepth(b->rchild);
return 1+(h1>h2?h1:h2);
}
}

int Leafnode(BTNode *b)
{ int h,h1,h2;
if(!b)return 0;
if(!b->lchild&&!b->rchild)
return 1;
else
{ h1=Leafnode(b->lchild);
h2=Leafnode(b->rchild);
h=h1+h2;
return h;
}
}

void disp(BTNode* b)
{ if(b)
{ printf("%c",b->data);
if(b->lchild||b->rchild)
{ printf("(");
disp(b->lchild);
printf(",");
disp(b->rchild);
printf(")");
}
}
}

int creat(BTNode* &b)
{ char ch;
scanf("%c",&ch);
if(ch==',')b=NULL;
else
{ b=(BTNode*)malloc(sizeof(node));
if(!b)exit(0);
b->data=ch;
creat(b->lchild);
creat(b->rchild);
}
return 0;
}

int nodenumber(BTNode* b)
{ if(!b)
return 0;
else
return (nodenumber(b->lchild)+nodenumber(b->rchild)+1);
}

BTNode* FindNode(BTNode* b,elemtype x)
{ int flag1=0,flag2=0;
BTNode *b1,*b2;
if(!b)
return NULL;
if(b->data==x)
{ return b;flag1=1;
}
if(!flag1)
b1=FindNode(b->lchild,x);
if(b1!=NULL)
return b1;
else
b2=FindNode(b->rchild,x);
if(b2!=NULL)
return b2;
else
return NULL;
}

BTNode* LchildNode(BTNode *find)
{ return find->lchild;
}

BTNode* RchildNode(BTNode *find)
{ return find->rchild;
}

void menu()
{ printf("\t\t\t[1]建立二叉树\n\t\t\t[2]深度\n\t\t\t[3]宽度\n\t\t\t[4]树叶\n\t\t\t[5]\
显示元素\n\t\t\t[6]菜单\n\t\t\t[7]所有结点个数\n\t\t\t[8]BTNode* FindNode(BTNode* b,\
elemtype x)\n\t\t\t[9] the lchild and rchild of X which found by [8]\n\t\t\t[0]退出\n");
}
int main()
{ char c,x;
BTNode *root=NULL,*find,*l,*r;
menu();
do
{ printf("功能选择:");
scanf("%c",&c);
getchar();
switch(c)
{ case '1':printf("请输入结点值，','为虚结点，回车结束！！\
\n---先序--请保证数据正确完整如:ABC,,DE,G,,F,,,\n:")\
;creat(root);getchar();break;
case '2':
printf("二叉树深度%d\n",Btnodedepth(root));;break;
case '3':
printf("二叉树宽度%d\n",BTWidth(root));break;
case '4':
printf("二叉树树叶数量%d\n",Leafnode(root));break;
case '5':disp(root);
printf("\n");break;
case '6':menu();break;
case '7':
printf("所有结点个数:%d\n",nodenumber(root));break;
case '8':printf("input X:");
scanf("%c",&x);getchar();
find=FindNode(root,x);
if(find!=NULL)
printf("the element is:%c\n",find->data);
else printf("not found!\n");break;
case '9':
printf("the lchild and rchild of X:\n");
if((l=LchildNode(find))==NULL)
printf("lchild is NULL\n");
else printf("lchild is %c\n",l->data);
if((r=RchildNode(find))==NULL)
printf("rchild is NULL\n");
else printf("rchild is %c\n",r->data);
break;
case '0':break;
default:printf("输入有误\n");break;
}
}while(c!='0');
return 0;
}

中序遍历
http://zhidao.baidu.com/question/36183981.html?si=1
时间复杂度
http://zhidao.baidu.com/question/82193747.html?si=6