#include "stdio.h"
#include "stdlib.h"
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
BiTree CreateBiTree(){
char ch;
BiTree T;
scanf("%c",&ch);
if(ch=='#') T=NULL;
else{
if(!(T=(BiTree)malloc(sizeof(BiTNode)))) return(0);
T->data=ch;
T->lchild=CreateBiTree();
T->rchild=CreateBiTree();
}
return(T);
}
void preorder(BiTree root){
if(root){
printf("%c",root->data);
preorder(root->lchild);
preorder(root->rchild);
}
}
void inorder(BiTree root){
if(root){
inorder(root->lchild);
printf("%c",root->data);
inorder(root->rchild);
}
}
void postorder(BiTree root){
if(root){
postorder(root->lchild);
postorder(root->rchild);
printf("%c",root->data);
}
}
BiTree findNode(BiTree t,char x){
BiTree p;
if(!t) return(NULL);
else if(t->data==x)return (t);
else{
p=findNode(t->lchild,x);
if(!p)p=findNode(t->rchild,x);
return(p);
}
}
void layer(BiTree t){
BiTree T;
char q[20];
int i=-1,j=-1;
T=t;
if(T!=NULL) {i++; q[i]=T->data;}
while(j<i){
j++;
T=findNode(t,q[j]);
if(T->lchild!=NULL) {i++; q[i]=T->lchild->data;}
if(T->rchild!=NULL) {i++;q[i]=T->rchild->data;}
}
for(j=0;j<=i;j++)printf("%c",q[j]);
}
int counter(BiTNode *t)
{int s;
if(t==NULL) return(0);
else s=counter(t->lchild)+counter(t->rchild)+1;
return(s);
}
int depth(BiTNode *t)
{int dep1,dep2;
if(t==NULL) return(0);
else {dep1=depth(t->lchild);
dep2=depth(t->rchild);
if(dep1>dep2) return(dep1+1);
else return(dep2+1);
}}
BiTNode *findparent(BiTNode *t,BiTNode *q)
{BiTNode *p,*s;
if(t==NULL) s=NULL;
else if(t->lchild==q || t->rchild==q) s=t;
else {p=findparent(t->lchild,q);
if(p==NULL) p=findparent(t->rchild,q);
s=p;
}
return(s);
}
void main(){
BiTNode *T,*p,*q;
char ch; int m,n,h;
printf("请按照先序顺序输入您要建立的二叉树(空孩子用#表示）：\n");
T=CreateBiTree();
while(1)
{
printf(" 1.遍历此二叉树 \n");
printf(" 2.查找出某结点的父结点 \n");
printf(" 3.求二叉树的高度 \n");
printf(" 4.求二叉树的结点总数 \n");
printf(" 0.结束 \n");
printf("请选择编号（0—4):");
scanf("%d",&n);
printf("\n");
switch(n){
case 1:
printf("先序遍历此二叉树 ");
preorder(T);
printf(" \n中序遍历此二叉树 ");
inorder(T);
printf(" \n后序遍历此二叉树 ");
postorder(T);
printf(" \n层次遍历此二叉树 ");
layer(T);
printf("\n\n");break;
case 2:
printf("请输入结点数值(该数值为您已经建立的二叉树中除根结点以外的):\n");
scanf("%s",&ch);
q=findNode(T,ch);
p=findparent(T,q);
if(p!=NULL)
{printf("结点的父结点值为:\n");
printf("%c\n\n",p->data);}
else
printf("该结点无父结点\n");break;
case 3:
h=depth(T);
printf("该二叉树的高度为：%d\n\n",h);break;
case 4:
m=counter(T);
printf("该二叉树的结点总数为:%d\n\n",m);break;
case 0:
exit(0);
}
}
}
/**//*运行结果：
请按照先序顺序输入您要建立的二叉树(空孩子用#表示）：
ABD##E##C#F##
1.遍历此二叉树
2.查找出某结点的父结点
3.求二叉树的高度
4.求二叉树的结点总数
0.结束
请选择编号（0—4):1
先序遍历此二叉树 ABDECF
中序遍历此二叉树 DBEACF
后序遍历此二叉树 DEBFCA
层次遍历此二叉树 ABCDEF
1.遍历此二叉树
2.查找出某结点的父结点
3.求二叉树的高度
4.求二叉树的结点总数
0.结束
请选择编号（0—4):2
请输入结点数值(该数值为您已经建立的二叉树中除根结点以外的):
F
结点的父结点值为:
C
1.遍历此二叉树
2.查找出某结点的父结点
3.求二叉树的高度
4.求二叉树的结点总数
0.结束
请选择编号（0—4):3
该二叉树的高度为：3
1.遍历此二叉树
2.查找出某结点的父结点
3.求二叉树的高度
4.求二叉树的结点总数
0.结束
请选择编号（0—4):4
该二叉树的结点总数为:6
1.遍历此二叉树
2.查找出某结点的父结点
3.求二叉树的高度
4.求二叉树的结点总数
0.结束
请选择编号（0—4):0
Press any key to continue
*/
posted on 2005-11-25 20:20
halCode 阅读(1585)
评论(0) 编辑 收藏 引用 所属分类:
算法/数据结构