二叉樹是筆試面試中考試最頻繁的數據結構之一，主要包括，程序建立一個二叉樹，三種次序遍歷二叉樹，返回葉子節點的數目，求二叉樹節點的總數等。建立一個二叉樹節點的數據結構
typedef struct Node
{
int data;
struct Node *left,*right;
}Node;，結構體內包括數據，左子樹，又子樹；
一、建立二叉樹的程序代碼如下
[cpp] Node *CreatBTree() //建立二叉樹
{
Node *t;
int x;
scanf("%d",&x);
if(x==0)
{
t=NULL;
}
else
{
t=(Node*)malloc(sizeof(Node));
t->data=x;
printf("\n請輸入%d結點的左子結點:",t->data );
t->left=CreatBTree();
printf("\n請輸入%d結點的右子結點:",t->data );
t->right=CreatBTree();
}
return t;
}
Node *CreatBTree() //建立二叉樹
{
Node *t;
int x;
scanf("%d",&x);
if(x==0)
{
t=NULL;
}
else
{
t=(Node*)malloc(sizeof(Node));
t->data=x;
printf("\n請輸入%d結點的左子結點:",t->data );
t->left=CreatBTree();
printf("\n請輸入%d結點的右子結點:",t->data );
t->right=CreatBTree();
}
return t;
}
二、前序遍歷二叉樹
[cpp] void preVisit(Node *T)
{
if(T==NULL) return;
else
{
printf("%3d",T->data);
preVisit(T->left);
preVisit(T->right);
}
}
void preVisit(Node *T)
{
if(T==NULL) return;
else
{
printf("%3d",T->data);
preVisit(T->left);
preVisit(T->right);
}
}
三、中序遍歷二叉樹
[cpp] void middVisit(Node *T)
{
if(T==NULL) return;
else
{
middVisit(T->left);
printf("%3d",T->data);
middVisit(T->right);
}
}
void middVisit(Node *T)
{
if(T==NULL) return;
else
{
middVisit(T->left);
printf("%3d",T->data);
middVisit(T->right);
}
}
四、後序遍歷二叉樹
[cpp] void lastVisit(Node *T)
{
if(T==NULL) return;
else
{
lastVisit(T->left);
lastVisit(T->right);
printf("%3d",T->data);
}
}
void lastVisit(Node *T)
{
if(T==NULL) return;
else
{
lastVisit(T->left);
lastVisit(T->right);
printf("%3d",T->data);
}
}
五、返回葉子節點數目
[cpp] int leafnum(Node *T)
{
if (!T)
{
return 0;
}
else if ((!T->left)&&(!T->right))
{
return 1;
}
else
{
return ((leafnum(T->left)+leafnum(T->right)));
}
}
int leafnum(Node *T)
{
if (!T)
{
return 0;
}
else if ((!T->left)&&(!T->right))
{
return 1;
}
else
{
return ((leafnum(T->left)+leafnum(T->right)));
}
}
六、返回節點總數目
[cpp] view plaincopyprint?int Nodenum(Node *T)
{
if (T)
{
return 1+Nodenum(T->left)+Nodenum(T->right);
}
if (T==NULL)
{
return 0;
}
}
int Nodenum(Node *T)
{
if (T)
{
return 1+Nodenum(T->left)+Nodenum(T->right);
}
if (T==NULL)
{
return 0;
}
}
七、測試程序；[cpp] int menu();
void main()
{
Node *T=NULL;
int choice;
do{
choice=menu();
if(choice==1)
{
printf("二叉樹的建立，以輸入“0”表示結束：！\n");
printf("請輸入根結點：\n");
T=CreatBTree();
printf("二叉樹成功建立");
}
else if(choice==2)
{
printf("先序遍歷二叉樹 :\n");
preVisit(T);
}
else if(choice==3)
{
printf("中序遍歷二叉樹:\n");
middVisit(T);
}
else if(choice==4)
{
printf("後序遍歷二叉樹 :\n ");
lastVisit(T);
}
else if(choice==5)
{
int ct=10;
ct=leafnum(T);
printf(" 二叉樹的葉子結點數為 : \n");
printf("%d\n",ct);
}
else if(choice==7)
{
int count=Nodenum(T);
printf("該二叉樹總共有%d個結點。\n",count);
}
else if(choice==8)
exit(0);
}while(choice<=8);
}
int menu();
void main()
{
Node *T=NULL;
int choice;
do{
choice=menu();
if(choice==1)
{
printf("二叉樹的建立，以輸入“0”表示結束：！\n");
printf("請輸入根結點：\n");
T=CreatBTree();
printf("二叉樹成功建立");
}
else if(choice==2)
{
printf("先序遍歷二叉樹 :\n");
preVisit(T);
}
else if(choice==3)
{
printf("中序遍歷二叉樹:\n");
middVisit(T);
}
else if(choice==4)
{
printf("後序遍歷二叉樹 :\n ");
lastVisit(T);
}
else if(choice==5)
{
int ct=10;
ct=leafnum(T);
printf(" 二叉樹的葉子結點數為 : \n");
printf("%d\n",ct);
}
else if(choice==7)
{
int count=Nodenum(T);
printf("該二叉樹總共有%d個結點。\n",count);
}
else if(choice==8)
exit(0);
}while(choice<=8);
}
[cpp] int menu()
{
int choice;
printf("\n");
printf(" 二叉樹 \n");
printf(" ***************************\n");
printf(" * *\n");
printf(" * 主菜單 *\n");
printf(" * 1 建立二叉樹 *\n");
printf(" * 2 先序遍歷二叉樹 *\n");
printf(" * 3 中序遍歷二叉樹 *\n");
printf(" * 4 後序遍歷二叉樹 *\n");
printf(" * 5 二叉樹的葉子結點數 *\n");
printf(" * 7 二叉樹的所有結點數 *\n");
printf(" * 8 退出程序運行 *\n");
printf(" ****************************\n");
printf(" 請輸入您的選擇（1，2，3，4，5，6，7，8): \n");
scanf("%d",&choice);
return choice;
}
int menu()
{
int choice;
printf("\n");
printf(" 二叉樹 \n");
printf(" ***************************\n");
printf(" * *\n");
printf(" * 主菜單 *\n");
printf(" * 1 建立二叉樹 *\n");
printf(" * 2 先序遍歷二叉樹 *\n");
printf(" * 3 中序遍歷二叉樹 *\n");
printf(" * 4 後序遍歷二叉樹 *\n");
printf(" * 5 二叉樹的葉子結點數 *\n");
printf(" * 7 二叉樹的所有結點數 *\n");
printf(" * 8 退出程序運行 *\n");
printf(" ****************************\n");
printf(" 請輸入您的選擇（1，2，3，4，5，6，7，8): \n");
scanf("%d",&choice);
return choice;
}
