一起talk C栗子吧（第三十九回：C語言執行個體--建立一棵二叉樹）

各位看官們，大家好，上一回中咱們說的是“你了解scanf嗎”的例子，這一回咱們說的例子是：建立一棵二叉樹。閑話休提，言歸正轉。讓我們一起talk C栗子吧！

看官們，二叉樹是一種特殊的樹，特殊性就在于它的每個結點最多有兩個孩子。二叉樹在程式中也是一種經常使用的資料結構，比如在排序中也會使用它。

在我們的例子中，使用了一種叫作二叉連結清單的存儲結構來存儲二叉樹。二叉連結清單其實是一個結構體類型的存儲空間，它包含三個成員。具體的定義的如下：

typedef struct _BinTreeNode
 {
    char data;                // the value of node
    struct _BinTreeNode *lc;  // the left child
    struct _BinTreeNode *rc;  // the right child
}Node;
           

從結點的定義中，我們可以看到:

1. 第一個成員用來存儲結點的值；
2. 第二個成員用來存儲結點的左孩子；
3. 第三個成員用來存儲結點的右孩子。

最後的這兩個成員一左一右，很像一個“八”字的叉，而且它們可以把其它的結點連結在一起，是以叫它二叉連結清單很形象。說完二叉連結清單後，我們接下來說一說如何使用二叉連結清單建立一棵二叉樹，詳細的步驟如下：

1. 從終端或者檔案中讀取結點的值；
2. 判斷擷取的值，如果值是‘X’，那麼表示二叉樹中沒有結點，傳回步驟1.如果不是‘X’，進入步驟3；
3. 給結點配置設定存儲空間，并且把步驟1中讀取的值當作該結點的值;
4. 執行步驟1到步驟3,建立該結點的左孩子（這個過程可以通過遞歸實作）；
5. 執行步驟1到步驟4,建立該結點的右孩子（這個過程可以通過遞歸實作）；
6. 反複執行步驟1到5,直到終端中讀取的内容都是‘X’，或者檔案中的内容為空。

看官們，正文中就不寫代碼了，詳細的代碼放到了我的資源中，大家可以點選這裡下載下傳使用。

我們在例子中建立的二叉樹如下圖所示：

例子中，我們使用了一個數組來存放二叉樹中各個結點的值，其中X表示結點的值為空，或者說該結點不存在。大家可以自己修改數組中的值，來建立不同的二叉樹。我們在例子中建立結點時給每個結點配置設定了相應的存儲空間，大家都知道，配置設定完的空間需要釋放掉，不然會有記憶體洩漏。是以，我們專門定義了一個函數:DeatroyBinaryTree來釋放存儲空間。

各位看官，關于建立一棵二叉樹的例子咱們就說到這裡。欲知後面還有什麼例子，且聽下回分解。