#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 閱讀(1589)
評論(0) 編輯 收藏 引用 所屬分類:
算法/數據結構