模板
教程
環境
性能
功能
管理
二叉樹的集合操作
以下程序源代碼：
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define NULL 0
#define DataType char
typedef struct BinTreeNode *PBinTreeNode;
typedef PBinTreeNode *PBinTree;
struct BinTreeNode
{ DataType info;
PBinTreeNode llink;
PBinTreeNode rlink;
};
PBinTreeNode Create_BinTree(void);
PBinTree Create_BinTreeRoot(void)
{PBinTree pbtree;
pbtree=(PBinTree)malloc(sizeof(struct BinTreeNode));
if(pbtree==NULL) pbtree=(PBinTree)realloc(pbtree,sizeof(struct BinTreeNode));
*pbtree=Create_BinTree();
return (pbtree);
}
PBinTreeNode Create_BinTreeNode(void)
{PBinTreeNode pbnode;
pbnode=(PBinTreeNode)malloc(sizeof(struct BinTreeNode));
if(pbnode==NULL) pbnode=(PBinTreeNode)realloc(pbnode,sizeof(struct BinTreeNode));
else pbnode->llink=pbnode->rlink=(PBinTreeNode)NULL;
return (pbnode);
}
int isalphabet(char i)
{
if (i >= 'a' && i <='z' || i >= 'A' && i <='Z' || i=='@')
return 1;
else return 0;
}
PBinTreeNode Create_BinTree(void)
{PBinTreeNode pbnode ;
DataType i;
printf("Please input a char:\t");
fflush(stdin);
scanf("%c",&i);
fflush(stdin);
while(!isalphabet(i))
{
printf("Sorry, your input char is not in alphabet, please input again:");
scanf("%c",&i);
fflush(stdin);
}
if(i=='@') pbnode= NULL;
else
{
pbnode = (PBinTreeNode)malloc(sizeof(struct BinTreeNode));
if(pbnode == NULL)
{
printf("Out of space!\n");
return pbnode ;
}
pbnode->info=i;
pbnode->llink=Create_BinTree();
pbnode->rlink=Create_BinTree();
}
return pbnode;
}
void outputTree(PBinTreeNode pbnode,int totalSpace)
{int i;
if(pbnode!=NULL)
{
totalSpace+=5;
outputTree(pbnode->rlink,totalSpace);
for(i=0;i<totalSpace;i++) printf(" ");
printf("%c\n",pbnode->info);
outputTree(pbnode->llink,totalSpace);
}
}
void preOrder(PBinTreeNode pbnode)
{
if(pbnode==NULL) return ;
printf("%c\t",pbnode->info);
preOrder(pbnode->llink);
preOrder(pbnode->rlink);
}
void inOrder(PBinTreeNode pbnode)
{
if(pbnode== NULL) return;
inOrder(pbnode->llink);
printf("%c\t",pbnode->info);
inOrder(pbnode->rlink);
}
void postOrder(PBinTreeNode pbnode)
{
if(pbnode == NULL) return ;
postOrder(pbnode->llink);
postOrder(pbnode->rlink);
printf("%c\t", pbnode->info);
}
void leaves(PBinTreeNode pbnode)
{
if(pbnode->llink != NULL && pbnode->rlink == NULL)
leaves(pbnode->llink);
if(pbnode->rlink != NULL && pbnode->llink == NULL)
leaves(pbnode->rlink);
if(pbnode->llink != NULL && pbnode->rlink != NULL)
{
leaves(pbnode->llink);
leaves(pbnode->rlink);
}
if(pbnode->llink == NULL && pbnode->rlink == NULL)
{
printf("%c\t",pbnode->info);
return;
}
}
void freeAllNodes(PBinTreeNode pbnode)
{
if(pbnode->llink != NULL && pbnode->rlink == NULL)
freeAllNodes(pbnode->llink);
if(pbnode->rlink != NULL && pbnode->llink == NULL)
freeAllNodes(pbnode->rlink);
if(pbnode->llink != NULL && pbnode->rlink != NULL)
{
freeAllNodes(pbnode->llink);
freeAllNodes(pbnode->rlink);
}
if(pbnode->llink == NULL && pbnode->rlink == NULL)
{
free(pbnode->llink);
free(pbnode->rlink);
pbnode = NULL;
return ;
}
}
int main()
{PBinTree pbtree;
int i;
int totalSpace = 0;
printf("Please input char to the binatree,@ to exit current node:\n");
pbtree = Create_BinTreeRoot();
printf("Display the binatree data directly:\n");
outputTree(*pbtree,totalSpace);
printf("Please choose the mode you want to operate with the binatree:\n");
printf("1.display 2.preOrder 3.inOrder 4.postOrder 5.leaves 6.free nodes 0 to exit:");
scanf("%d",&i);
while(i>6 || i<0)
{
printf("\nYou choice is illegal please input again:\n");
printf("1.display 2.preOrder 3.inOrder 4.postOrder 5.leaves 6.free nodes 0 to exit:");
scanf("%d",&i);
}
while(i!=0)
{
while(i > 6 || i<0)
{
printf("\nYou choice is illegal please input again:\n");
printf("1.display 2.preOrder 3.inOrder 4.postOrder 5.leaves 6.free nodes 0 to exit:");
scanf("%d",&i);
}
while(i !=0)
{
while(i > 6 || i<0)
{
printf("\nYou choice is illegal please input again:\n");
printf("1.display 2.preOrder 3.inOrder 4.postOrder 5.leaves 6.free nodes 0 to exit:");
scanf("%d",&i);
}
while(i !=6)
{
while(i > 6 || i<0)
{
printf("\nYou choice is illegal please input again:\n");
printf("1.display 2.preOrder 3.inOrder 4.postOrder 5.leaves 6.free nodes 0 to exit:");
scanf("%d",&i);
}
switch(i)
{
case 0 :
printf("\nDealing with the last job, to free all nodes...\n");
freeAllNodes(*pbtree);
printf("All node have been freed suclearcase/" target="_blank" >ccessfully\n");
exit(1);
getch();
case 1 :
printf("\nDisplay binatree:\n");
outputTree(*pbtree,totalSpace);
break;
case 2 :
printf("\nData in preOrder:\n");
preOrder(*pbtree);
printf("\n\n");
break;
case 3 :
printf("\nData in inOrder:\n");
inOrder(*pbtree);
printf("\n\n");
break;
case 4 :
printf("\nData in postOrder:\n");
postOrder(*pbtree);
printf("\n\n");
break;
case 5:
printf("\nLeaves:\n");
leaves(*pbtree);
printf("\n\n");
}
printf("Please choose the mode you want to operate with the binatree:\n");
printf("1.display 2.preOrder 3.inOrder 4.postOrder 5.leaves 6.free nodes 0 to exit:");
scanf("%d",&i);
}
if(i==6)
{
printf("\nFree all nodes:\n");
freeAllNodes(*pbtree);
printf("All node have been freed successfully.");
}
printf("\n\nNow creating a new binatree...\n");
printf("Please input char to the binatree,@ to exit current node:\n");
pbtree = Create_BinTreeRoot();
printf("Display the binatree data directly:\n");
outputTree(*pbtree,totalSpace);
printf("Please choose the mode you want to operate with the binatree:\n");
printf("1.display 2.preOrder 3.inOrder 4.postOrder 5.leaves 6.free nodes 0 to exit:");
scanf("%d",&i);
}
}
printf("\nDealing with the last job, to free all nodes\n");
freeAllNodes(*pbtree);
printf("All node have been freed successfully\n");
getch();
return 0;
}
----------------------------------以下是程序的詳細分析過程-----------------------------------
二叉樹的集合操作
一． 問題的描述和分析
編寫一段程序，對二叉樹進行復合操作，包括創建一棵二叉樹，顯示二叉樹的樹型結構，對創建的二叉樹進行先根、中根、后根三種方式進行遍歷，并且打印出葉子結點，并且可以隨時刪除我們創建的二叉樹，然后用循環語句將上述的操作封裝起來，使之能夠進行可重復、連續的操作。
二．算法的設計
要實現上述的功能，我們首先要深刻的了解二叉樹的數據結構，然后依據它的特點，著手如何去創建一棵二叉樹，然后，用不同的方法對這棵二叉樹進行不同的遍歷，實現其它的功能，包括用戶友好界面的實現等等一系列的后續操作。
三．數據結構的設計
本程序要用到的數據類型
struct BinTreeNode
{ DataType info;
PBinTreeNode llink;
PBinTreeNode rlink;
};
然后定義我們需要的指針類型
typedef struct BinTreeNode *PBinTreeNode; 定義指向二叉樹結點的指針類型
typedef PBinTreeNode *PBinTree; 定義指向樹型結點的指針類型
四. 程序需要用到的自定義函數
1．創建一個二叉樹根節點
PBinTree Create_BinTreeRoot(void)
2．創建一個二叉樹的節點
PBinTreeNode Create_BinTreeNode(void)
3．創建一棵二叉樹
PBinTreeNode Create_BinTree(void)
4．用先根的方法遍歷一棵二叉樹
void preOrder(PBinTreeNode pbnode)
5．用中根的方法遍歷一棵二叉樹
void inOrder(PBinTreeNode pbnode)
6．用后根的方法遍歷一棵二叉樹
void postOrder(PBinTreeNode pbnode)
7．打印出我們創建的二叉樹的樹型結構
void outputTree(PBinTreeNode pbnode,int totalSpace)
8．打印出二叉樹的葉子結點
void leaves(PBinTreeNode pbnode)
9．釋放我們所申請的所有結點空間
void freeAllNodes(PBinTreeNode pbnode)
10．判斷我們輸入的是否是合格的字符，我們把它們定義為a-z或者是A-Z之間的字符，用‘@’字符作為結束當前結點的標識符
int isalphabet(char i)
五．具體程序的實現
1． PBinTreeNode Create_BinTreeNode(void)
我們定義一個指向二叉樹結點類型的指針PBinTreeNode，然后，申請一個二叉樹結點大小的空間，
對左右子結點賦為空（鑒于visual C++類別的嚴格定義，我們這里把它賦值為(PBinTreeNode)NULL—-注解）
2．創建一個二叉樹根節點
定義一個指向二叉樹結點的指針的指針即：BinTreeNode ** pbtree, 或者是：PBinTreeNode *pbtree;
用于存放樹的根結點，同時，將我們創建的二叉樹的地址傳給它即：*pbtree=Create_BinTree();
3． 創建一棵二叉樹
首先我們定義一個DataType類型的變量i,用于存放我們輸入的字符（即作為緩沖區），并用scanf函數去接收它，由于使用scanf函數時，會出現吸收我們輸入的回車字符，并將會車作為接收的字符的情況發生，為了避免這種情況，我們用函數fflush(stdin)將緩沖區的字符全部沖掉，然后再吸收我們輸入的字符，就可以完全避免此類問題的發生。
我們定義我們輸入的字符是從a-z或者是A-Z，用字符@為我們結束當前結點左或者右結點的字符，然后遞歸調用左右子樹，此時我們將一棵二叉樹全整的創建出來了。
4．用先根的方法遍歷一棵二叉樹
先訪問根結點，打印出它里面的信息，然后遞歸調用左子樹和右子樹。
5．用中根的方法遍歷一棵二叉樹
先遞歸調用左子樹，打印出里面的信息，在打印出根結點信息，然后遞歸調用右子樹，打印出里面的信息。
6．用后根的方法遍歷一棵二叉樹
先遞歸調用左子樹，打印出里面的內容，然后遞歸調用右子樹，打印出里面的內容，然后是根結點的內容
7. 打印出我們創建的二叉樹的樹型結構
先遞歸調用右子樹，如果結點不為空的話，空格數加5，如果為空的話，就打印出右子樹的內容，然后遞歸調用左子樹
8．打印出二叉樹的葉子結點
如果當前結點的左右子樹都為空的話，就打印出此結點的信息，如果左子樹不為空的話，遞歸調用左子樹，如果右子樹不為空的話，遞歸調用右子樹。
9．釋放我們所申請的所有結點空間
如果當前的左子樹不為空，則遍歷左子樹，如果右子樹不為空的話，則遍歷右子樹，如果都不位空的話，分別調用左右子樹，如果左右都為空的話，就釋放左右結點空間，并將當前結點置為空。
10．主函數的安排：
先創建好我們要的二叉樹，之后，我們就可以對此而二樹進行多種操作，我們定義了6種集合操作，并對用戶輸入的信息進行檢測，正確的提示出錯信息，如果選擇的是我們定義的操作之一的話，對應的我們設置出不同的case語句。
如果我們選擇的是釋放所有的結點空間的話，我們需要屏蔽掉所有的菜單信息，提示用戶重新創建一棵二叉樹，并對它進行重新操作。
如果我們選擇退出，但是沒有選擇釋放掉所有的節點空間時，我們需要考慮到此類的情形，應調用void freeAllNodes(PBinTreeNode pbnode)自動的釋放掉所有的結點空間，正常的退出。
六．界面設計
當用戶還沒有創建二叉樹時，提示用戶輸入數據：
Please input char to the binatree, @ to exit current node:
Please input a char:
當用戶，創建了二叉樹之后，出現控制菜單：
Please choose the mode you want to operate with the binatree:
1.display 2.preOrder 3.inOrder 4.postOrder 5.leaves 6.free nodes 0 to exit:
七．程序的調試：
1． 測試完全二叉樹的情形：
輸入（每輸入一個字符回車一次）：A B C @ @ D @ @ E F @ @ G @ @
自動的打印出樹型結構：
Display the binatree data directly:
G
E
F
A
D
B
C
三種遍歷方式和葉子結點，測試如下：
先根：
Data in preOrder:
A B C D E F G
中根：
Data in inOrder:
C B D A F E G
后根：
Data in postOrder:
C D B F G E A
打印葉子結點：
Leaves:
C D F G
釋放所有結點空間：
Free all nodes:
All node have been freed successfully.
自動提示創建一棵新的二叉樹：
Now creating a new binatree...
Please input char to the binatree, @ to exit current node:
Please input a char:
2測試非完全二叉樹的情形
輸入（每輸入一個字符回車一次）：A B C D @ @ @ @ @
自動的打印出樹型結構：
A
B
C
D
三種遍歷方式和葉子結點，測試如下：
先根：
Data in preOrder:
A B C D
中根：
Data in inOrder:
D C B A
后根：
Data in postOrder:
D C B A
打印葉子結點：
Leaves:
D
釋放所有結點空間：
Free all nodes:
All node have been freed successfully.
自動提示創建一棵新的二叉樹：
Now creating a new binatree...
Please input char to the binatree, @ to exit current node:
Please input a char:
如果我們想結束此次的操作，退出本程序，就可以輸入0，程序自動的釋放所有的結點空間：
Please choose the mode you want to operate with the binatree:
1.display 2.preOrder 3.inOrder 4.postOrder 5.leaves 6.free nodes 0 to exit:0
Dealing with the last job, to free all nodes
All node have been freed successfully
