算法與數(shù)據(jù)結構（六）二叉樹基礎篇

不同于數(shù)組、隊列等線性表的數(shù)據(jù)結構，樹是一種非線性結構。除了樹之外，圖也是一種非線性結構。

二叉樹如下所示。

節(jié)點和邊

在樹中由節(jié)點和連接節(jié)點的邊組成，二叉樹最多有兩個子節(jié)點。關于節(jié)點有幾個概念：

1.父節(jié)點：節(jié)點 1 為節(jié)點 2 和 3 的父節(jié)點；2.子節(jié)點：節(jié)點 4 和 5 為節(jié)點 2 的子節(jié)點；3.兄弟節(jié)點：節(jié)點 2 和 3 為兄弟節(jié)點；4.葉子節(jié)點：沒有子節(jié)點的節(jié)點為葉子節(jié)點，如節(jié)點 4 和 5；5.根節(jié)點：沒有父節(jié)點的節(jié)點為根節(jié)點，如節(jié)點 1。

關于樹的層級有如下幾個概念：

1.節(jié)點的高度：該節(jié)點到葉子節(jié)點的最長路徑，即邊數(shù)；2.節(jié)點的深度：根節(jié)點到該節(jié)點經(jīng)歷的邊數(shù)；3.節(jié)點的層數(shù)：深度 + 1；4.樹的高度：等于根節(jié)點的高度。

以下圖為例，可以幫助理解節(jié)點高度、深度、層的概念。

特殊的二叉樹

如果一個二叉樹葉子節(jié)點都在同一層級，而且除了葉子節(jié)點每個節(jié)點都有兩個子節(jié)點，這種二叉樹叫做滿二叉樹。上文中的圖例即為滿二叉樹。

如果一個二叉樹，最后一層的葉子節(jié)點都在左側，其他層的節(jié)點數(shù)量達到最大，這種二叉樹叫做完全二叉樹。上文圖中我們把節(jié)點 7 去掉，就符合滿二叉樹的條件。

二叉樹的存儲

二叉樹的存儲也離不開最基礎的數(shù)據(jù)結構：

?數(shù)組?鏈表

對于數(shù)組存儲，我們可以使用以下規(guī)則約定每個節(jié)點在數(shù)組中存儲的位置。

1.假設父節(jié)點存儲索引為 i；2.該節(jié)點左子節(jié)點的位置為 2 * i，右子節(jié)點為 2 * i + 1；3.根節(jié)點存儲在 1 號位。

下圖可以幫助理解二叉樹數(shù)組存儲的方式?？梢钥吹剑耆鏄涫褂脭?shù)組存儲能夠充分利用數(shù)組空間。非完全二叉樹則會導致數(shù)組空間的浪費。

對于鏈表存儲，我們使用如下結構進行構建二叉樹。

class Node {    Node leftChild;    Node rightChild;}

二叉樹的遍歷

樹和圖的遍歷分為兩種：

1.深度優(yōu)先遍歷：如果存在層級更深的子節(jié)點，優(yōu)先遍歷該節(jié)點，否則遍歷同層級的其他節(jié)點；2.廣度優(yōu)先遍歷：如果存在同層級的兄弟節(jié)點，優(yōu)先遍歷兄弟節(jié)點，否則遍歷子節(jié)點。

對于樹的深度優(yōu)先遍歷，又分為三種：

1.前序遍歷：訪問當前節(jié)點——訪問左子樹——訪問右子樹；2.中序遍歷：訪問左子樹——訪問當前節(jié)點——訪問右子樹；3.后序遍歷：訪問左子樹——訪問右子樹——訪問當前節(jié)點。

仍以下圖為例，其遍歷序列分別如下：

1.前序遍歷：1, 2, 4, 5, 3, 6, 7；2.中序遍歷：4, 2, 5, 1, 6, 3, 7；3.后序遍歷：4, 5, 2, 6, 7, 3, 1。

三種遍歷的遞歸代碼如下。

void preOrder(Node root) {  if (root == null) return;
  print(root)  preOrder(root.left);  preOrder(root.right);}
void inOrder(Node root) {  if (root == null) return;
  inOrder(root.left);  print(root)  inOrder(root.right);}
void postOrder(Node root) {  if (root == null) return;
  postOrder(root.left);  postOrder(root.right);  print(root)}

總結

本次我們了解了二叉樹的基礎知識，有二叉樹的特征、二叉樹的數(shù)組和鏈表存儲方式、二叉樹的遍歷。有時間我們聊聊二叉樹的應用，它是如何優(yōu)化搜索算法復雜度的。