實現二叉樹的基本操作：建立、遍歷、計算深度、結點數、葉子數等。
輸入C，先序創建二叉樹，#表示空節點；
輸入H：計算二叉樹的高度；
輸入L：計算二叉樹的葉子個數；
輸入N：計算二叉樹節點總個數；
輸入1：先序遍歷二叉樹；
輸入2：中序遍歷二叉樹；
輸入3：後續遍歷二叉樹；
輸入F：查找值=x的節點的個數；
輸入P：以縮格文本形式輸出所有節點。
很簡單就不需要多解釋了，代碼貼上
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
/*二叉樹的鏈式存儲表示*/
typedef char DataType; /*應由用戶定義DataType的實際類型*/
typedef struct node
{
DataType data;
node *lchild, *rchild; /*左右孩子指針*/
} BinTNode; /*結點類型*/
typedef BinTNode *BinTree;
int sum=0;
void DisplayBinTree(BinTree T); /*用格文本形式表示二叉樹*/
void CreateBinTree(BinTree *T); /*構造二叉鏈表*/
void Preorder(BinTree T); /*前序遍歷二叉樹*/
void Inorder(BinTree T); /*中序遍歷二叉樹*/
void Postorder(BinTree T); /*後序遍歷二叉樹*/
int nodes(BinTree T); /*計算總結點數*/
int leafs(BinTree T); /*計算總葉子數*/
int hight(BinTree T); /*計算二叉樹的高度*/
int find(BinTree T,char x); //查找值=x的節點的個數；
int main()
{
BinTree T;
char flg;
while(cin>>flg)
switch(flg)
{
case'C':
getchar();
CreateBinTree(&T);
cout<<"Created success!"<<endl;
break;
case'H':
cout<<"Height="<<hight(T)<<"."<<endl;
break;
case'L':
cout<<"Leaf="<<leafs(T)<<"."<<endl;
break;
case'N':
cout<<"Nodes="<<nodes(T)<<"."<<endl;
break;
case'1':
printf("Preorder is:");
Preorder(T);
cout<<"."<<endl;
break;
case'2':
printf("Inorder is:");
Inorder(T);
cout<<"."<<endl;
break;
case'3':
printf("Postorder is:");
Postorder(T);
cout<<"."<<endl;
break;
case'F':
char x;
int ko;
getchar();
cin>>x;
ko=find(T,x);
cout<<"The count of "<<x<<" is "<<ko<<"."<<endl;
break;
case'P':
cout<<"The tree is:"<<endl;
DisplayBinTree(T);
break;
default:
cout<<"輸入有誤，請重新輸入"<<endl;
}
}
/*構造二叉鏈表*/
void CreateBinTree(BinTree *T)
{
char ch;
if ((ch=getchar())=='#')
*T=NULL;
else
{
/*讀入非空格*/
*T=(BinTNode *)malloc(sizeof(BinTNode));/*生成結點*/
(*T)->data=ch;
CreateBinTree(&(*T)->lchild ); /*構造左子樹*/
CreateBinTree(&(*T)->rchild ); /*構造右子樹*/
}
}
/*用縮格文本形式表示二叉樹*/
void DisplayBinTree(BinTree T)
{
BinTree stack[100],p;
int level[100],top,n,i;
if (T)
{
top=1;
stack[top]=T;
level[top]=0;
while(top>0)
{
p=stack[top];
n=level[top];
for (i=1; i<=n; i++)
cout<<" ";
printf("%c\n",p->data);
top--;
if (p->rchild!=NULL)
{
top++;
stack[top]=p->rchild;
level[top]=n+2;
}
if (p->lchild!=NULL)
{
top++;
stack[top]=p->lchild;
level[top]=n+2;
}
}
}
}
/*計算總結點數*/
int nodes(BinTree T)
{
if(T)
{
if( (T->lchild==NULL)&&(T->rchild==NULL))
return 1;
else
return nodes(T->lchild)+nodes(T->rchild)+1;
}
return 0;
}
/*計算總葉子數*/
int leafs(BinTree T)
{
if(T)
{
if ((T->lchild==NULL)&&(T->rchild==NULL))
return 1;
else
return leafs(T->lchild)+leafs(T->rchild);
}
return 0;
}
/*計算樹的高度*/
int hight(BinTree T)
{
if(T)
{
if ((T->lchild==NULL)&&(T->rchild==NULL))
return 1;
else if((T->lchild==NULL)&&(T->rchild))
return 1+hight(T->rchild);
else if((T->lchild)&&(T->rchild==NULL))
return 1+hight(T->lchild);
else
return hight(T->lchild)+hight(T->rchild);
}
return 0;
}
/*前序遍歷二叉樹*/
void Preorder(BinTree T)
{
if(T)
{
printf("%c ",T->data); /*訪問結點*/
Preorder(T->lchild);
Preorder(T->rchild);
}
}
/*中序遍歷二叉樹*/
void Inorder(BinTree T)
{
if(T)
{
Inorder(T->lchild);
printf("%C ",T->data);
Inorder(T->rchild);
}
}
/*後序遍歷二叉樹*/
void Postorder(BinTree T)
{
if(T)
{
Postorder(T->lchild);
Postorder(T->rchild);
printf("%C ",T->data);
}
}
int find(BinTree T,char x)
{
if(T)
{
if((T->data)==x)
sum++;
find(T->lchild,x);
find(T->rchild,x);
}
return sum;
}
