1.    二叉樹(shù)？

答：二叉樹(shù)是一種樹(shù)型結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有二棵子樹(shù)（即二叉樹(shù)中不存在度大于2的結(jié)點(diǎn)),并且,二叉樹(shù)的子樹(shù)有左右之分,其次序不能任意顛倒。.二叉樹(shù)的基本形態(tài)：(1)空二叉樹(shù)；(2)只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)；(3)右子樹(shù)為空的二叉樹(shù)；4)左子樹(shù)為空的二叉樹(shù)；(5)完全二叉樹(shù)。

二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 包括：

1.順序存儲(chǔ)結(jié)構(gòu)

連續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹(shù)的數(shù)據(jù)元素。例如圖 6.4(b)的完全二叉樹(shù) , 可以向量 (一維數(shù)組 ) bt(1:6)作它的存儲(chǔ)結(jié)構(gòu)，將二叉樹(shù)中編號(hào)為 i的結(jié)點(diǎn)的數(shù)據(jù)元素存放在分量 bt[i]中 ,如圖 6.6(a) 所示。但這種順序存儲(chǔ)結(jié)構(gòu)僅適合于完全二叉樹(shù) ,而一般二叉樹(shù)也按這種形式來(lái)存儲(chǔ) ,這將造成存 貯浪費(fèi)。如和圖 6.4(c)的二叉樹(shù)相應(yīng)的存儲(chǔ)結(jié)構(gòu)圖 6.6(b)所示，圖中以 “0”表示不存在此結(jié)點(diǎn) .

2. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

由二叉樹(shù)的定義得知二叉樹(shù)的結(jié)點(diǎn)由一個(gè)數(shù)據(jù)元素和分別指向左右子樹(shù)的兩個(gè)分支構(gòu)成 ,則表 示二叉樹(shù)的鏈表中的結(jié)點(diǎn)至少包含三個(gè)域 :數(shù)據(jù)域和左右指針域 ,如圖 (b)所示。有時(shí) ,為了便于找 到結(jié)點(diǎn)的雙親 ,則還可在結(jié)點(diǎn)結(jié)構(gòu)中增加一個(gè)指向其雙親受的指針域，如圖 6.7(c)所示。

遍歷二叉樹(shù)：

遍歷二叉樹(shù) (traversing binary tree)的問(wèn)題， 即如何按某條搜索路徑巡訪樹(shù)中每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次，而且僅被訪問(wèn)一次。 其中常見(jiàn)的有三種情況：分別稱之為先 (根 )序遍歷，中 (根 )序遍歷和后 (根 )序遍歷。

   （1）前序遍歷

前序遍歷運(yùn)算：即先訪問(wèn)根結(jié)點(diǎn)，再前序遍歷左子樹(shù)，最后再前序遍歷右子樹(shù)。前序遍歷運(yùn)算訪問(wèn)二叉樹(shù)各結(jié)點(diǎn)是以根、左、右的順序進(jìn)行訪問(wèn)的

（2）中序遍歷

中序遍歷運(yùn)算：即先中前序遍歷左子樹(shù)，然后再訪問(wèn)根結(jié)點(diǎn)，最后再中序遍歷右子樹(shù)。中序遍歷運(yùn)算訪問(wèn)二叉樹(shù)各結(jié)點(diǎn)是以左、根、右的順序進(jìn)行訪問(wèn)的

（3）后序遍歷

后序遍歷運(yùn)算：即先后序遍歷左子樹(shù)，然后再后序遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。后序遍歷運(yùn)算訪問(wèn)二叉樹(shù)各結(jié)點(diǎn)是以左、右、根的順序進(jìn)行訪問(wèn)的