圖 7-7   平衡二叉樹圖 7-6   完滿二叉樹圖 7-5   完全二叉樹「二叉樹 binary tree」是一種非線性數(shù)據(jù)結(jié)構(gòu)，代表著祖先與后代之間的派生關(guān)系，體現(xiàn)著“一分為二”的分治邏輯。與鏈表類似，二叉樹的基本單元是節(jié)點，每個節(jié)點包含：值、左子節(jié)點引用、右子節(jié)點引用。

/* 二叉樹節(jié)點結(jié)構(gòu)體 */
struct TreeNode {
    int val;          // 節(jié)點值
    TreeNode *left;   // 左子節(jié)點指針
    TreeNode *right;  // 右子節(jié)點指針
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

每個節(jié)點都有兩個引用（指針），分別指向「左子節(jié)點 left-child node」和「右子節(jié)點 right-child node」，該節(jié)點被稱為這兩個子節(jié)點的「父節(jié)點 parent node」。當(dāng)給定一個二叉樹的節(jié)點時，我們將該節(jié)點的左子節(jié)點及其以下節(jié)點形成的樹稱為該節(jié)點的「左子樹 left subtree」，同理可得「右子樹 right subtree」。

在二叉樹中，除葉節(jié)點外，其他所有節(jié)點都包含子節(jié)點和非空子樹。如圖 7-1 所示，如果將“節(jié)點 2”視為父節(jié)點，則其左子節(jié)點和右子節(jié)點分別是“節(jié)點 4”和“節(jié)點 5”，左子樹是“節(jié)點 4 及其以下節(jié)點形成的樹”，右子樹是“節(jié)點 5 及其以下節(jié)點形成的樹”。

圖 7-1   父節(jié)點、子節(jié)點、子樹

二叉樹常見術(shù)語

二叉樹的常用術(shù)語如圖 7-2 所示。

• 「根節(jié)點 root node」：位于二叉樹頂層的節(jié)點，沒有父節(jié)點。
• 「葉節(jié)點 leaf node」：沒有子節(jié)點的節(jié)點，其兩個指針均指向 None 。
• 「邊 edge」：連接兩個節(jié)點的線段，即節(jié)點引用（指針）。
• 節(jié)點所在的「層 level」：從頂至底遞增，根節(jié)點所在層為 1 。
• 節(jié)點的「度 degree」：節(jié)點的子節(jié)點的數(shù)量。在二叉樹中，度的取值范圍是 0、1、2 。
• 二叉樹的「高度 height」：從根節(jié)點到最遠(yuǎn)葉節(jié)點所經(jīng)過的邊的數(shù)量。
• 節(jié)點的「深度 depth」：從根節(jié)點到該節(jié)點所經(jīng)過的邊的數(shù)量。
• 節(jié)點的「高度 height」：從最遠(yuǎn)葉節(jié)點到該節(jié)點所經(jīng)過的邊的數(shù)量。

圖 7-2   二叉樹的常用術(shù)語

Tip

請注意，我們通常將“高度”和“深度”定義為“走過邊的數(shù)量”，但有些題目或教材可能會將其定義為“走過節(jié)點的數(shù)量”。在這種情況下，高度和深度都需要加 1 。

二叉樹基本操作

1.   初始化二叉樹

與鏈表類似，首先初始化節(jié)點，然后構(gòu)建引用（指針）。

binary_tree.cpp

/* 初始化二叉樹 */
// 初始化節(jié)點
TreeNode* n1 = new TreeNode(1);
TreeNode* n2 = new TreeNode(2);
TreeNode* n3 = new TreeNode(3);
TreeNode* n4 = new TreeNode(4);
TreeNode* n5 = new TreeNode(5);
// 構(gòu)建引用指向（即指針）
n1->left = n2;
n1->right = n3;
n2->left = n4;
n2->right = n5;

2.   插入與刪除節(jié)點

與鏈表類似，在二叉樹中插入與刪除節(jié)點可以通過修改指針來實現(xiàn)。圖 7-3 給出了一個示例。

圖 7-3   在二叉樹中插入與刪除節(jié)點

binary_tree.cpp

/* 插入與刪除節(jié)點 */
TreeNode* P = new TreeNode(0);
// 在 n1 -> n2 中間插入節(jié)點 P
n1->left = P;
P->left = n2;
// 刪除節(jié)點 P
n1->left = n2;

Note

需要注意的是，插入節(jié)點可能會改變二叉樹的原有邏輯結(jié)構(gòu)，而刪除節(jié)點通常意味著刪除該節(jié)點及其所有子樹。因此，在二叉樹中，插入與刪除操作通常是由一套操作配合完成的，以實現(xiàn)有實際意義的操作。

常見二叉樹類型

1.   完美二叉樹

「完美二叉樹 perfect binary tree」除了最底層外，其余所有層的節(jié)點都被完全填滿。在完美二叉樹中，葉節(jié)點的度為 0 ，其余所有節(jié)點的度都為 2 ；若樹高度為 ? ，則節(jié)點總數(shù)為 2?+1?1 ，呈現(xiàn)標(biāo)準(zhǔn)的指數(shù)級關(guān)系，反映了自然界中常見的細(xì)胞分裂現(xiàn)象。

圖 7-4   完美二叉樹

2.   完全二叉樹

如圖 7-5 所示，「完全二叉樹 complete binary tree」只有最底層的節(jié)點未被填滿，且最底層節(jié)點盡量靠左填充。

圖 7-5   完全二叉樹

3.   完滿二叉樹

如圖 7-6 所示，「完滿二叉樹 full binary tree」除了葉節(jié)點之外，其余所有節(jié)點都有兩個子節(jié)點。

圖 7-6   完滿二叉樹

4.   平衡二叉樹

如圖 7-7 所示，「平衡二叉樹 balanced binary tree」中任意節(jié)點的左子樹和右子樹的高度之差的絕對值不超過 1 。

圖 7-7   平衡二叉樹

二叉樹的退化

當(dāng)二叉樹的每層節(jié)點都被填滿時，達(dá)到“完美二叉樹”；而當(dāng)所有節(jié)點都偏向一側(cè)時，二叉樹退化為“鏈表”。

• 完美二叉樹是理想情況，可以充分發(fā)揮二叉樹“分治”的優(yōu)勢。
• 鏈表則是另一個極端，各項操作都變?yōu)榫€性操作，時間復(fù)雜度退化至 O(n) 。

圖 7-8   二叉樹的最佳與最差結(jié)構(gòu)

如表 7-1 所示，在最佳和最差結(jié)構(gòu)下，二叉樹的葉節(jié)點數(shù)量、節(jié)點總數(shù)、高度等達(dá)到極大或極小值。

表 7-1   二叉樹的最佳與最差情況