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

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

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

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

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

二叉樹常見術(shù)語

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

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

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

Tip

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

二叉樹基本操作

1.   初始化二叉樹

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

binary_tree.cpp

/* 初始化二叉樹 */
// 初始化節(jié)點(diǎn)
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é)點(diǎn)

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

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

binary_tree.cpp

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

Note

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

常見二叉樹類型

1.   完美二叉樹

「完美二叉樹 perfect binary tree」除了最底層外，其余所有層的節(jié)點(diǎn)都被完全填滿。在完美二叉樹中，葉節(jié)點(diǎn)的度為 0 ，其余所有節(jié)點(diǎn)的度都為 2 ；若樹高度為 ? ，則節(jié)點(diǎn)總數(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é)點(diǎn)未被填滿，且最底層節(jié)點(diǎn)盡量靠左填充。

圖 7-5   完全二叉樹

3.   完滿二叉樹

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

圖 7-6   完滿二叉樹

4.   平衡二叉樹

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

圖 7-7   平衡二叉樹

二叉樹的退化

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

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

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

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

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