樹(shù)
在介紹二叉樹(shù)之前，我們需要先明白什么是樹(shù)，因?yàn)槎鏄?shù)是樹(shù)的其中一種，因?yàn)槲覀冇玫淖疃啵晕覀兇蠖喽荚趯W(xué)習(xí)和了解二叉樹(shù)。
樹(shù)是一種抽象數(shù)據(jù)類型或是實(shí)現(xiàn)這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)，用來(lái)模擬具有樹(shù)狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n（n>0）個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。
樹(shù)具有以下特點(diǎn)：
- 每個(gè)節(jié)點(diǎn)都只有有限個(gè)子節(jié)點(diǎn)或無(wú)子節(jié)點(diǎn)
- 沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)
- 每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)
- 除了根節(jié)點(diǎn)外，每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹(shù)
- 樹(shù)里面沒(méi)有環(huán)路(cycle)
樹(shù)還有一些專用的術(shù)語(yǔ)和概念，我們通過(guò)下邊這個(gè)圖為例來(lái)說(shuō)明。
- 節(jié)點(diǎn)的度： 一個(gè)節(jié)點(diǎn)含有的子樹(shù)的個(gè)數(shù)為該節(jié)點(diǎn)的度（如下圖中 A 節(jié)點(diǎn)的度為 2）
- 樹(shù)的度：一棵樹(shù)中，度最大的那個(gè)節(jié)點(diǎn)度即為樹(shù)的度（下圖中度最大的節(jié)點(diǎn)為 B，其度為 3，所以樹(shù)的度為 3）
- 根節(jié)點(diǎn)：沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)稱為根節(jié)點(diǎn)（如圖中的 A 節(jié)點(diǎn)）
- 葉節(jié)點(diǎn)：度為零的節(jié)點(diǎn)（如圖中的 K,J,F,L,O,P 節(jié)點(diǎn)）
- 分支節(jié)點(diǎn)：度不為零的節(jié)點(diǎn)
- 子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)含有的子樹(shù)的跟節(jié)點(diǎn)稱為該節(jié)點(diǎn)的子節(jié)點(diǎn)（如圖中，B 和 C 為 A 的子節(jié)點(diǎn)）
- 父節(jié)點(diǎn)：如果一個(gè)節(jié)點(diǎn)含有子節(jié)點(diǎn)，那么這個(gè)節(jié)點(diǎn)稱為其子節(jié)點(diǎn)的父節(jié)點(diǎn)（如圖中，A 為 B 和 C 的父節(jié)點(diǎn)）
- 兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互為兄弟節(jié)點(diǎn)（如圖中，B 和 C 互為兄弟節(jié)點(diǎn)）
- 層：根為第1層，根的子節(jié)點(diǎn)為第2層，以此類推
- 深度：對(duì)于任意節(jié)點(diǎn) n ，n 的深度為從根到 n 的唯一路徑長(zhǎng)，根的深度為0
- 高度：對(duì)于任意節(jié)點(diǎn) n ，n 的高度為從 n 到葉節(jié)點(diǎn)的最長(zhǎng)路徑長(zhǎng)，所有葉節(jié)點(diǎn)的高度為0
二叉樹(shù)
樹(shù)的種類有很多，不過(guò)最常用的還是二叉樹(shù)。
二叉樹(shù)，顧名思義，我們就能知道每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，分別稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。當(dāng)然，并不是每個(gè)節(jié)點(diǎn)都有兩個(gè)節(jié)點(diǎn)，也可能有的只有左子節(jié)點(diǎn)，有的只有右子節(jié)點(diǎn)。
二叉樹(shù)中有兩種特殊的類型，滿二叉樹(shù)和完全二叉樹(shù)。
葉子節(jié)點(diǎn)全部都在最底層，除葉子節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)，這種二叉樹(shù)稱作滿二叉樹(shù)（如下圖）。
在一顆二叉樹(shù)中，若除最后一層外的其余層都是滿的，并且最后一層要么是滿的，要么在右邊缺少連續(xù)若干節(jié)點(diǎn)，則此二叉樹(shù)為完全二叉樹(shù)（如下圖）。
二叉樹(shù)的存儲(chǔ)
我們上面已經(jīng)基本了解了什么是二叉樹(shù)，那么我們?cè)谑褂玫臅r(shí)候是怎么來(lái)存儲(chǔ)的呢？
我們首先來(lái)看順序存儲(chǔ)法。我們把根節(jié)點(diǎn)放在索引為 的位置（假設(shè)根節(jié)點(diǎn)的索引為0），那么他的左子節(jié)點(diǎn)的索引會(huì)是
，右子節(jié)點(diǎn)的索引會(huì)是
，而他的父節(jié)點(diǎn)（如果有）索引則為
。這種存儲(chǔ)方法更有利于緊湊存儲(chǔ)和單個(gè)節(jié)點(diǎn)的訪問(wèn)，例如上邊提到的滿二叉樹(shù)和完全二叉樹(shù)就非常適合用這種方法存儲(chǔ)，緊湊排列而不浪費(fèi)空間。因?yàn)檫@種方法需要連續(xù)的存儲(chǔ)空間，所以如果不是完全二叉樹(shù)的話就會(huì)浪費(fèi)不少的存儲(chǔ)空間，這也是這種存儲(chǔ)方法的一個(gè)缺點(diǎn)。
我們?cè)賮?lái)看一下鏈?zhǔn)酱鎯?chǔ)法。鏈?zhǔn)酱鎯?chǔ)法比較簡(jiǎn)單直觀。每個(gè)節(jié)點(diǎn)存儲(chǔ)三個(gè)字段，其中一個(gè)是該節(jié)點(diǎn)的數(shù)據(jù)，另外兩個(gè)是指向左右子節(jié)點(diǎn)的指針。我們只要通過(guò)根節(jié)點(diǎn)，就可以通過(guò)左右子節(jié)點(diǎn)的指針，把整棵樹(shù)都串起來(lái)。這也是我們比較常用的存儲(chǔ)方式。大部分的二叉樹(shù)也都是通過(guò)這種結(jié)構(gòu)實(shí)現(xiàn)的。
二叉樹(shù)的遍歷
前邊說(shuō)了定義和存儲(chǔ)方法，現(xiàn)在我們來(lái)看一下二叉樹(shù)的遍歷（面試常問(wèn)）。
怎樣把二叉樹(shù)的所有節(jié)點(diǎn)都輸出出來(lái)呢，有三種常用的方法，前序遍歷、中序遍歷和后序遍歷。他們的不同在于輸出節(jié)點(diǎn)和它左右子節(jié)點(diǎn)的先后順序。
前序遍歷
前序遍歷是指，對(duì)于二叉樹(shù)的任意節(jié)點(diǎn)，我們首先輸出該節(jié)點(diǎn)，然后輸出它的左子樹(shù)，最后輸出它的右子樹(shù)。
我們來(lái)看一下具體的代碼實(shí)現(xiàn)：
//節(jié)點(diǎn)結(jié)構(gòu)類
class TreeNode
{
int value;
TreeNode left;
TreeNode right;
TreeNode(int value)
{
this.value = value;
}
}
//前序遍歷，遞歸實(shí)現(xiàn)
public void preOrderRe(TreeNode node)
{
System.out.println(node.value);
TreeNode leftNode = node.left;
if(leftNode != null)
{
preOrderRe(leftNode);
}
TreeNode rightNode = node.right;
if(rightNode != null)
{
preOrderRe(rightNode);
}
}
//前序遍歷，借用棧實(shí)現(xiàn)
public void preOrder(TreeNode node)
{
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode nd = node;
while(nd != null || stack.size() > 0)
{
if(nd != null)
{
System.out.println(nd.value);
stack.push(nd);
nd = nd.left;
}
else
{
nd = stack.pop();
nd = nd.right;
}
}
}
中序遍歷
中序遍歷是指，對(duì)于樹(shù)中的任意節(jié)點(diǎn)，我們首先輸出它的左子樹(shù)，然后再輸出它本身，最后輸出它的右子樹(shù)。
我們來(lái)看一下具體的代碼實(shí)現(xiàn)：
//中序遍歷，遞歸實(shí)現(xiàn)
public void midOrderRe(TreeNode node)
{
TreeNode leftNode = node.left;
if(leftNode != null)
{
preOrderRe(leftNode);
}
System.out.println(node.value);
TreeNode rightNode = node.right;
if(rightNode != null)
{
preOrderRe(rightNode);
}
}
//中序遍歷，借用棧實(shí)現(xiàn)
public void midOrder(TreeNode node)
{
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode nd = node;
while(nd != null || stack.size() > 0)
{
if(nd != null)
{
stack.push(nd);
nd = nd.left;
}
else
{
nd = stack.pop();
System.out.println(nd.value);
nd = nd.right;
}
}
}
后序遍歷
后序遍歷是指，對(duì)于樹(shù)中的任意節(jié)點(diǎn)來(lái)說(shuō)，我們首先輸出它的左子樹(shù)，然后再輸出它的右子樹(shù)，最后輸出這個(gè)節(jié)點(diǎn)本身。
我們來(lái)看一下具體的代碼實(shí)現(xiàn)：
//后序遍歷，遞歸實(shí)現(xiàn)
public void postOrderRe(TreeNode node)
{
TreeNode leftNode = node.left;
if(leftNode != null)
{
preOrderRe(leftNode);
}
TreeNode rightNode = node.right;
if(rightNode != null)
{
preOrderRe(rightNode);
}
System.out.println(node.value);
}
//后序遍歷，借用棧實(shí)現(xiàn)
public void postOrder(TreeNode node)
{
Stack<TreeNode> stack = new Stack<TreeNode>();
//構(gòu)造一個(gè)中間棧來(lái)存儲(chǔ)逆后序遍歷的結(jié)果
Stack<TreeNode> output = new Stack<TreeNode>();
TreeNode nd = node;
while(nd != null || stack.size() > 0)
{
if(nd != null)
{
output.push(nd);
stack.push(nd);
nd = nd.right;
}
else
{
nd = stack.pop();
nd = nd.left;
}
}
while(output.size() > 0)
{
System.out.println(output.pop());
}
}
內(nèi)容小結(jié)
以上就是樹(shù)和二叉樹(shù)一些基礎(chǔ)的知識(shí)，我們來(lái)總結(jié)回顧一下。我們講了一種非線性數(shù)據(jù)結(jié)構(gòu)樹(shù)，樹(shù)有幾個(gè)比較常用的概念我們需要了解和掌握：根節(jié)點(diǎn)、葉子節(jié)點(diǎn)、父節(jié)點(diǎn)、子節(jié)點(diǎn)、兄弟節(jié)點(diǎn)，還有節(jié)點(diǎn)的高度、深度、層數(shù)，以及樹(shù)的高度。
我們最常用的樹(shù)就是二叉樹(shù)。二叉樹(shù)每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。我們又介紹了兩種比較特殊的樹(shù)，滿二叉樹(shù)和完全二叉樹(shù)，滿二叉樹(shù)其實(shí)也屬于完全二叉樹(shù)。
二叉樹(shù)的存儲(chǔ)方式有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。順序存儲(chǔ)比較適合完全二叉樹(shù)，會(huì)更充分利用內(nèi)存空間而不會(huì)造成浪費(fèi)。鏈?zhǔn)酱鎯?chǔ)是比較簡(jiǎn)單直觀，也是比較常用的存儲(chǔ)方法。還有非常重要的二叉樹(shù)前、中、后序遍歷，是我們必須要掌握的。
