什麼是二元樹，二元樹及其應用

二元樹是一個結點的集合，其中每個結點最多與兩個後繼結點相關聯，分別稱為左側子結點和右側子結點。二元樹中的每個結點並不是全都有兩個子結點，也可能只有一個結點或兩個結點都可能被省略。在二元樹中，沒有子結點的結點稱為葉結點。

包含子結點的結點稱為其子結點的父結點。對於一個定義為二元樹的非空的結點集合，每個結點必須至多有一個父結點，並且必須有一個結點是沒有父結點的。這個沒有父結點的結點稱為二元樹的根結點。一個空的結點集合可以構成一個空的二元樹。

連結串列和二元樹有一些相似之處。二元樹的根對應於連結串列的頭部，二元樹結點的子結點對應於連結串列中的後繼結點，二元樹結點的父結點對應於連結串列中結點的前驅結點。當然，空連結串列的模擬是空的二元樹。

二元樹的實現

二元樹可用於將值儲存到其結點中。因此，二元樹中的結點就是一個結構或類物件，它包含一個用於儲存值的成員，以及另外兩個指向該結點的左側和右側子結點的成員：

struct TreeNode
{
    int value;
    TreeNode *left;
    TreeNode *right;
};

二元樹本身就是由指向根結點的指標所代表的。圖 1 給出了一個二元樹範例，其中未顯示結點中儲存的值。如果該結點不具有相應的子結點，則結點中的 left 指標或 right 指標將設定為 nullptr。

---