二叉數

圖的一種特例。為一遞歸數據類型，由一個根節點引出，每個節點有兩支，每支也是一棵二叉數。

基本介紹

• 中文名：二叉數
• 解釋：圖的一種特例
• 性質：遞歸數據類型
• 結構：樹型結構

結構

它是一種樹型結構，簡單地說，形如下面的圖形稱為二叉樹。它是數據結構的知識 除空二叉樹外，有一個唯一的根接點，左、右子樹都是二叉樹。 可以得知：

1、 二叉樹的每個結點至多只有二棵子樹（即不存在結點的度大於2的結點）。

2、 二叉樹的子樹有左右之分，其次序不能任意顛倒。

性質

1、 在二叉樹的第i層上至多有2i-1個結點（i>=1）。

2、深度為k的二叉樹最多有2k-1個結點。

3、 對任何一棵二叉樹T，如果其終端結點數為n0個，度為2的結點數為n2個，則n0=n2+1個。

滿二叉樹

滿二叉樹：是指一棵深度為K且有2k-1個結點的二叉樹。

遍歷方法

（先序）先根遍歷：（根左右）先訪問根，再訪問左子樹，最後訪問右子樹，則可得如下的序列：abcdef

（中序）中根遍歷：（左根右）先訪問左子樹，再訪問根，最後訪問右子樹，則可得如下的序列：cbdaef

（後序）後根遍歷：（左右根）先訪問左子樹，再訪問右子樹，最後訪問根，則可得如下的序列：cdbfea

練習

1、表達式(1+34)*5-56/7 的後綴表達式為（ ）。

A） 1+34*5-56/7

B） -*+1 34 5/56 7

C） 1 34 +5*56 7/-

D） 1 34 5* +56 7/-

E） 1 34+5 56 7-*/

解：表達式(1+34)*5-56/7 的後綴表達式即為該表達式對應的二叉樹的後序遍歷。 所以，首先按運算優先權關係畫出(1+34)*5-56/7的二叉樹，然後再用後序遍歷得出結果。