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

/* 二叉樹(shù)節(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)被稱(chēng)為這兩個(gè)子節(jié)點(diǎn)的「父節(jié)點(diǎn) parent node」。當(dāng)給定一個(gè)二叉樹(shù)的節(jié)點(diǎn)時(shí)，我們將該節(jié)點(diǎn)的左子節(jié)點(diǎn)及其以下節(jié)點(diǎn)形成的樹(shù)稱(chēng)為該節(jié)點(diǎn)的「左子樹(shù) left subtree」，同理可得「右子樹(shù) right subtree」。

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

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

二叉樹(shù)常見(jiàn)術(shù)語(yǔ)

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

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

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

Tip

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

二叉樹(shù)基本操作

1.   初始化二叉樹(shù)

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

binary_tree.cpp

/* 初始化二叉樹(shù) */
// 初始化節(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)

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

圖 7-3   在二叉樹(shù)中插入與刪除節(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ì)改變二叉樹(shù)的原有邏輯結(jié)構(gòu)，而刪除節(jié)點(diǎn)通常意味著刪除該節(jié)點(diǎn)及其所有子樹(shù)。因此，在二叉樹(shù)中，插入與刪除操作通常是由一套操作配合完成的，以實(shí)現(xiàn)有實(shí)際意義的操作。

常見(jiàn)二叉樹(shù)類(lèi)型

1.   完美二叉樹(shù)

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

圖 7-4   完美二叉樹(shù)

2.   完全二叉樹(shù)

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

圖 7-5   完全二叉樹(shù)

3.   完滿(mǎn)二叉樹(shù)

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

圖 7-6   完滿(mǎn)二叉樹(shù)

4.   平衡二叉樹(shù)

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

圖 7-7   平衡二叉樹(shù)

二叉樹(shù)的退化

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

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

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

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

表 7-1   二叉樹(shù)的最佳與最差情況