#include <stdlib.h>
#define max 100
typedef struct node{ //二叉樹結構
char data;
struct node *lc,*rc; //左右子樹
}bt,*list;
/*
二叉樹
A
/ \
B C
/ \ \
D E F
/ / \
K G H
input
ABDK000E00C0FG00H00
ouput
ABDKECFGH
KDBEACGFH
KDEBGHFCA
*/
int creat(list*root){ //創建壹棵二叉樹，root使用的是二維指針
char n;
scanf(" %c",&n); //註%C前面加空格是為了起間隔作用 scanf不讀入空格
if (n=='0') //0為間隔
{
*root=NULL; return 0; //輸入結束
}
*root=(list)malloc(sizeof(bt));
if (!*root) return 0;
(*root)->data=n;
creat(&(*root)->lc);
creat(&(*root)->rc);
return 1;
}
int pre(list root){ //先序遍歷
if (!root) return 0;
printf("%c",root->data);
pre(root->lc);
pre(root->rc);
return 1;
}
int mid(list root){ //中序遍歷
if (!root) return 0;
mid(root->lc);
printf("%c",root->data);
mid(root->rc);
return 1;
}
int bh(list root){ //後序遍歷
if (!root) return 0;
bh(root->lc);
bh(root->rc);
printf("%c",root->data);
return 1;
}
int sum(list root,int *cnt){ //求結點的個數sum
if(root){
(*cnt)++;
sum(root->lc,cnt);
sum(root->rc,cnt);
return 1;
}
return 0;
}
int sumleaf(list root,int *cnt){ //求葉子節點的個數
if (root)
{
if ((!root->lc)&&(!root->rc))
{ (*cnt)++; }
sumleaf(root->lc,cnt);
sumleaf(root->rc,cnt);
return 1;
}
return 0;
}
int deep(list root,int *cnt){ //求深度
if (!root)
{
*cnt=0; return 0;
}
int m,n;
n=m=*cnt;
deep(root->lc,&m);
deep(root->rc,&n);
*cnt=m+1;
if(m<n) *cnt=n+1;
return 1;
}
int floor(list root){ //層次遍歷
if(root)
{
list s[max]; int front,rear; //用隊進行存儲
front=-1; rear=0; s[rear]=root; //初始化
while (rear!=front) //當隊為空時結束
{
printf("%c",s[++front]->data);
if (s[rear]->lc)
{s[1+rear]=s[rear]->lc; rear++; } //將左子樹存入隊列中
if (s[rear]->rc)
{s[1+rear]=s[rear]->rc; rear++; } //將右子書存入隊列中
}
return 1;
}
return 0;
}
int scop(list *r,list *p){ //樹的復制
if(*r){
*p=(list)malloc(sizeof(bt));
if(*p){
(*p)->data=(*r)->data;
scop(&(*r)->lc,&(*p)->lc);
scop(&(*r)->rc,&(*p)->rc);
return 1;
}
}
*p=NULL;
return 0;
}
int sepect(list root,list *p,char e){ //查找節點返回指針*p p為二級指針
if(root){
if (root->data==e)
{ *p=root; return 1;
}
sepect(root->lc,p,e);
sepect(root->rc,p,e);
}
return 0;
}
void main(){
list b,s,m;
int n,t=1;
char ch='\0';
printf("***********Bitree************\n");
while(t){ //循環操作
printf("input a tree(int):\n");
s=m=b=NULL; //二叉樹的初始化
creat(&b);
//按三種遍歷輸出二叉樹
printf("\npre "); pre(b);
printf("\nmid "); mid(b);
printf("\nbh "); bh(b); printf("\n");
//求節點數目，葉子節點的個數，深度
n=0; sum(b,&n); printf("sumdata: %d\n",n);
n=0; sumleaf(b,&n); printf("sumleaf: %d\n",n);
n=0; deep(b,&n); printf("deep: %d\n",n);
//二叉樹的復制
scop(&b,&s);
printf("\nscopy tree:\npre ");
pre(s); printf("\nmid ");
mid(s); printf("\nbh ");
bh(s); printf("\n");
//查找節點
printf("sepect a data:\n");
scanf(" %c",&ch); //註%C前面加空格是為了起間隔作用 scanf不讀入空格
sepect(b,&m,ch);
if(m)
printf("sepect : %c \n",m->data);
else
printf("Error,no this data: %c\n",ch);
//繼續則輸入 1，退出輸入 0
printf("continue input 1,break input 0:\n");
scanf("%d",&t);
}
}