二叉樹的應用—二叉樹遍歷的應用

在各類的遍歷算法中，訪問結點的數據域信息，即操作Visite（bt->data）具有更一般的意義，需根據具體問題，對bt 數據進行不同的操作。下面介紹幾個遍歷操作的典型應用。

1．查找數據元素

Search（bt，x）在bt 為二叉樹的根結點指針的二叉樹中查找數據元素x。查找成功時返回該結點的指針；查找失敗時返回空指針。

算法實現如下，注意遍歷算法中的Visite(bt->data)等同於其中的一組操作步驟。
BiTree Search（BiTree bt，elemtype x）
{/*在bt 為根結點指針的二叉樹中查找數據元素x*/
BiTree p;
if (bt->data==x) return bt; /*查找成功返回*/
if (bt->lchild!=NULL) return(Search(bt->lchild,x));
/*在bt->lchild 為根結點指針的二叉樹中查找數據元素x*/
if (bt->rchild!=NULL) return(Search(bt->rchild,x));
/*在bt->rchild 為根結點指針的二叉樹中查找數據元素x*/
return NULL; /*查找失敗返回*/
}
算法6.21

2．統計出給定二叉樹中葉子結點的數目

（1）順序存儲結構的實現
int CountLeaf1（SqBiTree bt，int k）
{/*一維數組bt[2k-1]為二叉樹存儲結構，k 為二叉樹深度，函數值為葉子數。*/
total=0;
for(i=1;i<=2k-1;i++)
{ if (bt[i]!=0)
{ if ((bt[2i]==0 && bt[2i+1]==0) || (i>(2k-1)/2))
total++;
}
}
return(total);
}
算法6.22

（2）二叉鍊表存儲結構的實現
int CountLeaf2（BiTree bt）
{/*開始時，bt 為根結點所在鏈結點的指針，返回值為bt 的葉子數*/
if (bt==NULL) return(0);
if (bt->lchild==NULL && bt->rchild==NULL) return(1);
return(CountLeaf2(bt->lchild)+CountLeaf2(bt->rchild));
}
算法6.23

3．創建二叉樹二叉鍊表存儲，並顯示。

設創建時，按二叉樹帶空指針的先序次序輸入結點值，結點值類型為字符型。輸出按中序輸出。

CreateBinTree（BinTree *bt）是以二叉鍊表為存儲結構建立一棵二叉樹T 的存儲，bt為指向二叉樹T 根結點指針的指針。設建立時的輸入序列為：AB0D00CE00F00。建立如圖6.3 (b)所示的二叉樹存儲。

InOrderOut（bt）為按中序輸出二叉樹bt 的結點。算法實現如下，注意在創建算法中，遍歷算法中的Visite(bt->data)被讀入結點、申請空間存儲的操作所代替；在輸出算法中，遍歷算法中的Visite(bt->data)被c 語言中的格式輸出語句所代替。

void CreateBinTree(BinTree *T)
{/*以加入結點的先序序列輸入，構造二叉鍊表*/
char ch;
scanf("\n%c",&ch);
if (ch=='0') *T=NULL; /*讀入0 時，將相應結點置空*/
else {*T=(BinTNode*)malloc(sizeof(BinTNode)); /*生成結點空間*/
(*T)->data=ch;
CreateBinTree(&(*T)->lchild); /*構造二叉樹的左子樹*/
CreateBinTree(&(*T)->rchild); /*構造二叉樹的右子樹*/
}
}
void InOrderOut(BinTree T)
{/*中序遍歷輸出二叉樹T 的結點值*/
if (T)
{ InOrderOut(T->lchild); /*中序遍歷二叉樹的左子樹*/
printf("%3c",T->data); /*訪問結點的數據*/
InOrderOut(T->rchild); /*中序遍歷二叉樹的右子樹*/
}
}
main()
{BiTree bt;
CreateBinTree(&bt);
InOrderOut(bt);
}
算法6.24

4．表達式運算

我們可以把任意一個算數表達式用一棵二叉樹表示，圖6.15 所示為表達式3x2+x-1/x+5的二叉樹表示。在表達式二叉樹中，每個葉結點都是操作數，每個非葉結點都是運算符。對於一個非葉子結點，它的左、右子樹分別是它的兩個操作數。

對該二叉樹分別進行先序、中序和後序遍歷，可以得到表達式的三種不同表示形式。

前綴表達式+-+*3*xxx/1x5
中綴表達式3*x*x+x-1/x+5
後綴表達式3xx**x+1x/-5+

中綴表達式是經常使用的算術表達式，前綴表達式和後綴表達式分別稱為波蘭式和逆波蘭式，它們在編譯程序中有著非常重要的作用。