~~~
#include<stdio.h>
#include<windows.h>
#include<malloc.h>
#define maxsize 20
typedef int elemtype;
typedef struct node //定義
{
elemtype data;
struct node *lchild;
struct node *rchild;
}btnode;
void createbtnode(btnode *&b,char *str) //創建二叉樹
{
btnode *st[maxsize],*p=NULL;
int top=-1,k,j=0;
char ch;
b=NULL;
ch=str[j];
while(ch!='\0')
{
switch(ch)
{
case '(':top++;st[top]=p;k=1;break;
case ')':top--;break;
case ',':k=2;break;
default:p=(btnode *)malloc(sizeof(btnode));
p->data=ch;p->lchild=p->rchild=NULL;
if(b==NULL)
b=p;
else
{
switch(k)
{
case 1:st[top]->lchild=p;break;
case 2:st[top]->rchild=p;break;
default:printf("錯誤!\n");
}
}
}
j++;
ch=str[j];
}
}
btnode *findnode(btnode *b,elemtype x) //查找節點
{
btnode *p;
if(b==NULL)
return NULL;
else if(b->data==x)
return b;
else
{
p=findnode(b->lchild,x);
if(p!=NULL)
return p;
else?
return findnode(b->rchild,x);
}
}
btnode *lchildnode(btnode *p) //找左孩子
{
return p->lchild;
}
btnode *rchildnode(btnode *p) //找右孩子
{
return p->rchild;
}
int btnodeheight(btnode *b) //求高度
{
int lchildh,rchildh;
if(b==NULL)
return 0;
else
{
lchildh=btnodeheight(b->lchild);
rchildh=btnodeheight(b->rchild);
return(lchildh>rchildh)?(lchildh+1):(rchildh+1);
}
}
void dispbtnode(btnode *b) //輸出二叉樹
{
if(b!=NULL)
{
printf("%c",b->data);
if(b->lchild!=NULL||b->rchild!=NULL)
{
printf("(");
dispbtnode(b->lchild);
if(b->rchild!=NULL)
printf(",");
dispbtnode(b->rchild);
printf(")");
}
}
}
int Nodes(btnode *b)//求二叉樹b的節點個數
{
int num1,num2;
if (b==NULL)?
return 0;
else if (b->lchild==NULL && b->rchild==NULL)?
return 1;
else
{
num1=Nodes(b->lchild);
num2=Nodes(b->rchild);
return (num1+num2+1);
}
}
int LeafNodes(btnode *b)//求二叉樹b的葉子節點個數
{
int num1,num2;
if (b==NULL)?
return 0;
else if (b->lchild==NULL && b->rchild==NULL)?
return 1;
else
{
num1=LeafNodes(b->lchild);
num2=LeafNodes(b->rchild);
return (num1+num2);
}
}
void TravLevel(btnode *b) //層次遍歷
{
btnode *Qu[maxsize];//定義循環隊列
int front,rear;//定義隊首和隊尾指針
front=rear=0;//置隊列為空隊列
if (b!=NULL)?
printf("%c ",b->data);
rear++;//節點指針進入隊列
Qu[rear]=b;
while (rear!=front)//隊列不為空
{
front=(front+1)%maxsize;
b=Qu[front];//隊頭出隊列
if (b->lchild!=NULL)//輸出左孩子,并入隊列
{
printf("%c ",b->lchild->data);
rear=(rear+1)%maxsize;
Qu[rear]=b->lchild;
}
if (b->rchild!=NULL)//輸出右孩子,并入隊列
{
printf("%c ",b->rchild->data);
rear=(rear+1)%maxsize;
Qu[rear]=b->rchild;
}
}?
printf("\n");
}
void PreOrder(btnode *b) //先序遍歷的遞歸算法
{
if (b!=NULL)?
{
printf("%c ",b->data);//訪問根節點
PreOrder(b->lchild);//遞歸訪問左子樹
PreOrder(b->rchild);//遞歸訪問右子樹
}
}
void PreOrder1(btnode *b) //先序遍歷的非遞歸算法
{
btnode *St[maxsize],*p;
int top=-1;
if (b!=NULL)?
{
top++;//根節點入棧
St[top]=b;
while (top>-1)//棧不為空時循環
{
p=St[top];//退棧并訪問該節點
top--;
printf("%c ",p->data);
if (p->rchild!=NULL)//右孩子入棧
{
top++;
St[top]=p->rchild;
}
if (p->lchild!=NULL)//左孩子入棧
{
top++;
St[top]=p->lchild;
}
}
printf("\n");
}
}
void InOrder(btnode *b) //中序遍歷的遞歸算法
{
if (b!=NULL)?
{
InOrder(b->lchild);//遞歸訪問左子樹
printf("%c ",b->data);//訪問根節點
InOrder(b->rchild);//遞歸訪問右子樹
}
}
void InOrder1(btnode *b) //中序遍歷的非遞歸算法
{
btnode *St[maxsize],*p;
int top=-1;
if (b!=NULL)
{
p=b;
while (top>-1 || p!=NULL)
{
while (p!=NULL)
{
top++;
St[top]=p;
p=p->lchild;
}
if (top>-1)
{
p=St[top];
top--;
printf("%c ",p->data);
p=p->rchild;
}
}
printf("\n");
}
}
void PostOrder(btnode *b) //后序遍歷的遞歸算法
{
if (b!=NULL)?
{
PostOrder(b->lchild);//遞歸訪問左子樹
PostOrder(b->rchild);//遞歸訪問右子樹
printf("%c ",b->data);//訪問根節點
}
}
void PostOrder1(btnode *b) //后續遍歷的非遞歸算法
{
btnode *St[maxsize];
btnode *p;
int flag,top=-1;//棧指針置初值
if (b!=NULL)
{
do
{
while (b!=NULL)//將t的所有左節點入棧
{
top++;
St[top]=b;
b=b->lchild;
}
p=NULL;//p指向當前節點的前一個已訪問的節點
flag=1;
while (top!=-1 && flag)
{
b=St[top];//取出當前的棧頂元素
if (b->rchild==p)//右子樹不存在或已被訪問,訪問之
{
printf("%c ",b->data);//訪問*b節點
top--;
p=b;//p指向則被訪問的節點
}
else
{
b=b->rchild;//t指向右子樹
flag=0;
}
}
} while (top!=-1);
printf("\n");
}?
}
void DestroyBTNode(btnode *&b) //銷毀二叉樹
{
if (b!=NULL)
{
DestroyBTNode(b->lchild);
DestroyBTNode(b->rchild);
free(b);
}
}
void main()
{
int hight,n;
char ch,str[100];
btnode *b,*p,*p1,*p2;
printf(" *****************歡迎使用二叉樹基本運算系統*******************\n");
printf("請輸入一個廣義表\n(例如:A(B(D(,I),E(J,K(H))),C(F)))\n");
gets(str);
createbtnode(b,str);
while(1)
{
printf("請選擇:\n");
printf(" 1 求樹的高度\n");
printf(" 2 求節點的孩子\n");
printf(" 3 輸出二叉樹\n");
printf(" 4 求二叉樹的節點數\n");
printf(" 5 求二叉樹的葉子節點數\n");
printf(" 6 層次遍歷序列\n");
printf(" 7 先序遍歷序列\n");
printf(" 8 中序遍歷序列\n");
printf(" 9 后續遍歷序列\n");
printf(" 10 釋放二叉樹并退出\n");
printf(" 11 退出\n");
scanf("%d",&n);
switch(n)
{
case 1:printf("樹的高度為:%d\n",btnodeheight(b));break;
case 2:getchar();printf("請輸入需查找的節點:");
scanf("%c",&ch);
p=findnode(b,ch);
p1=lchildnode(p);
p2=rchildnode(p);
if(p1!=NULL)
printf("左孩子為:%c\n",p1->data);
else
printf("沒有左孩子\n");
if(p2!=NULL)
printf("右孩子為:%c\n",p2->data);
else
printf("沒有右孩子\n");
break;
case 3:dispbtnode(b);
printf("\n");
break;
case 4:printf("二叉樹的節點個數為:%d個\n",Nodes(b));break;
case 5:printf("二叉樹的葉子節點數為%d個\n",LeafNodes(b));break;
case 6:printf("層次遍歷序列:");TravLevel(b);break;
case 7:printf("先序遍歷序列:\n");
printf(" 遞歸算法:");PreOrder(b);printf("\n");
printf(" 非遞歸算法:");PreOrder1(b);break;
case 8:printf("中序遍歷序列:\n");
printf(" 遞歸算法:");InOrder(b);printf("\n");
printf(" 非遞歸算法:");InOrder1(b);break;
case 9:printf("后序遍歷序列:\n");
printf(" 遞歸算法:");PostOrder(b);printf("\n");
printf(" 非遞歸算法:");PostOrder1(b);break;
case 10:DestroyBTNode(b);printf("二叉樹已銷毀!\n");exit(0);break;
case 11:exit(0);
default:printf("輸入錯誤\n");
}
}
}
~~~
