在之前的文章中我們有講過樹的相關(guān)知識(shí)，例如，樹的概念、深度優(yōu)先遍歷和廣度優(yōu)先遍歷。這篇文章講述了一個(gè)特殊的樹——二叉樹。

       什么是二叉樹

　　二叉樹是每個(gè)節(jié)點(diǎn)最多只能有兩個(gè)子節(jié)點(diǎn)的樹，如下圖所示：

　　一個(gè)二叉樹具有以下幾個(gè)特質(zhì)：

　　要計(jì)算在每層有多少個(gè)點(diǎn)，可以依據(jù)公式2^(i-1)個(gè)(i是樹的第幾層)；

　　如果這顆二叉樹的深度為k，那二叉樹最多有2^k-1個(gè)節(jié)點(diǎn)；

　　在一個(gè)非空的二叉樹中，若使用n0表示葉子節(jié)點(diǎn)的個(gè)數(shù)，n2是度為2的非葉子節(jié)點(diǎn)的個(gè)數(shù)，那么兩者滿足關(guān)系n0 = n2 + 1。

　　滿二叉樹

　　如果在一個(gè)二叉樹中，除了葉子節(jié)點(diǎn)，其余的節(jié)點(diǎn)的每個(gè)度都是2，則說明該二叉樹是一個(gè)滿二叉樹，

　　如下圖所示：

　　滿二叉樹除了滿足普通二叉樹特質(zhì)，還具有如下幾個(gè)特質(zhì)：

　　每個(gè)層節(jié)點(diǎn)公式2^(n-1)（n為層數(shù)）；

　　深度為k的滿二叉樹一定存在2^k-1個(gè)節(jié)點(diǎn)，葉子節(jié)點(diǎn)的個(gè)數(shù)為2^(k-1)；

　　具有n個(gè)節(jié)點(diǎn)的滿二叉樹的深度為log_2^(n+1)。

　　完全二叉樹

　　如果一個(gè)二叉樹去掉最后一次層是滿二叉樹，且最后一次的節(jié)點(diǎn)是依次從左到右分布的，則這個(gè)二叉樹是一個(gè)完全二叉樹，

　　如下圖所示：

　　二叉樹的存儲(chǔ)

　　存儲(chǔ)二叉樹的常見方式分為兩種，一種是使用數(shù)組存儲(chǔ)，另一種使用鏈表存儲(chǔ)。

　　數(shù)組存儲(chǔ)

　　使用數(shù)組存儲(chǔ)二叉樹，如果遇到完全二叉樹，存儲(chǔ)順序從上到下，從左到右，如下圖所示：

　　如果是一個(gè)非完全二叉樹，如下圖所示：

　　需要先將其轉(zhuǎn)換為完全二叉樹，然后在進(jìn)行存儲(chǔ)，如下圖所示：

　　可以很明顯的看到存儲(chǔ)空間的浪費(fèi)。

　　鏈表存儲(chǔ)

　　使用鏈表存儲(chǔ)通常將二叉樹中的分為3個(gè)部分，如下圖：

　　這三個(gè)部分依次是左子樹的引用，該節(jié)點(diǎn)包含的數(shù)據(jù)，右子樹的引用，存儲(chǔ)方式如下圖所示：

　　與二叉樹相關(guān)的算法

　　以下算法中遍歷用到的樹如下：

　　// tree.js
　　const bt = {
　　val: 'A',
　　left: {
　　val: 'B',
　　left: { val: 'D', left: null, right: null },
　　right: { val: 'E', left: null, right: null },
　　},
　　right: {
　　val: 'C',
　　left: {
　　val: 'F',
　　left: { val: 'H', left: null, right: null },
　　right: { val: 'I', left: null, right: null },
　　},
　　right: { val: 'G', left: null, right: null },
　　},
　　}
　　module.exports = bt

　　深度優(yōu)先遍歷

　　二叉樹的深度優(yōu)先遍歷與樹的深度優(yōu)先遍歷思路一致，思路如下：

　　訪問根節(jié)點(diǎn)；

　　訪問根節(jié)點(diǎn)的left

　　訪問根節(jié)點(diǎn)的right

　　重復(fù)執(zhí)行第二三步

　　實(shí)現(xiàn)代碼如下：

　　const bt = {
　　val: 'A',
　　left: {
　　val: 'B',
　　left: { val: 'D', left: null, right: null },
　　right: { val: 'E', left: null, right: null },
　　},
　　right: {
　　val: 'C',
　　left: {
　　val: 'F',
　　left: { val: 'H', left: null, right: null },
　　right: { val: 'I', left: null, right: null },
　　},
　　right: { val: 'G', left: null, right: null },
　　},
　　}
　　function dfs(root) {
　　if (!root) return
　　console.log(root.val)
　　root.left && dfs(root.left)
　　root.right && dfs(root.right)
　　}
　　dfs(bt)
　　/** 結(jié)果
　　A B D E C F H I G
　　*/

　　廣度優(yōu)先遍歷

　　實(shí)現(xiàn)思路如下：

　　創(chuàng)建隊(duì)列，把根節(jié)點(diǎn)入隊(duì)

　　把對(duì)頭出隊(duì)并訪問

　　把隊(duì)頭的left和right依次入隊(duì)

　　重復(fù)執(zhí)行2、3步，直到隊(duì)列為空

　　實(shí)現(xiàn)代碼如下：

　　function bfs(root) {
　　if (!root) return
　　const queue = [root]
　　while (queue.length) {
　　const node = queue.shift()
　　console.log(node.val)
　　node.left && queue.push(node.left)
　　node.right && queue.push(node.right)
　　}
　　}
　　bfs(bt)
　　/** 結(jié)果
　　A B C D E F G H I
　　*/

　　先序遍歷

　　二叉樹的先序遍歷實(shí)現(xiàn)思想如下：

　　訪問根節(jié)點(diǎn);

　　對(duì)當(dāng)前節(jié)點(diǎn)的左子樹進(jìn)行先序遍歷；

　　對(duì)當(dāng)前節(jié)點(diǎn)的右子樹進(jìn)行先序遍歷；

　　如下圖所示：

　　遞歸方式實(shí)現(xiàn)如下：

　　const bt = require('./tree')
　　function preorder(root) {
　　if (!root) return
　　console.log(root.val)
　　preorder(root.left)
　　preorder(root.right)
　　}
　　preorder(bt)
　　/** 結(jié)果
　　A B D E C F H I G
　　*/

　　迭代方式實(shí)現(xiàn)如下：

　　// 非遞歸版
　　function preorder(root) {
　　if (!root) return
　　// 定義一個(gè)棧，用于存儲(chǔ)數(shù)據(jù)
　　const stack = [root]
　　while (stack.length) {
　　const node = stack.pop()
　　console.log(node.val)
　　/* 由于棧存在先入后出的特性，所以需要先入右子樹才能保證先出左子樹 */
　　node.right && stack.push(node.right)
　　node.left && stack.push(node.left)
　　}
　　}
　　preorder(bt)
　　/** 結(jié)果
　　A B D E C F H I G
　　*/

　　中序遍歷

　　二叉樹的中序遍歷實(shí)現(xiàn)思想如下：

　　對(duì)當(dāng)前節(jié)點(diǎn)的左子樹進(jìn)行中序遍歷；

　　訪問根節(jié)點(diǎn);

　　對(duì)當(dāng)前節(jié)點(diǎn)的右子樹進(jìn)行中序遍歷；

　　如下圖所示：

　　遞歸方式實(shí)現(xiàn)如下：

　　const bt = require('./tree')
　　// 遞歸版
　　function inorder(root) {
　　if (!root) return
　　inorder(root.left)
　　console.log(root.val)
　　inorder(root.right)
　　}
　　inorder(bt)
　　/** 結(jié)果
　　D B E A H F I C G
　　*/

　　迭代方式實(shí)現(xiàn)如下：

　　// 非遞歸版
　　function inorder(root) {
　　if (!root) return
　　const stack = []
　　// 定義一個(gè)指針
　　let p = root
　　// 如果棧中有數(shù)據(jù)或者p不是null，則繼續(xù)遍歷
　　while (stack.length || p) {
　　// 如果p存在則一致將p入棧并移動(dòng)指針
　　while (p) {
　　// 將 p 入棧，并以移動(dòng)指針
　　stack.push(p)
　　p = p.left
　　}
　　const node = stack.pop()
　　console.log(node.val)
　　p = node.right
　　}
　　}
　　inorder(bt)
　　/** 結(jié)果
　　D B E A H F I C G
　　*/

　　后序遍歷

　　二叉樹的后序遍歷實(shí)現(xiàn)思想如下：

　　對(duì)當(dāng)前節(jié)點(diǎn)的左子樹進(jìn)行后序遍歷；

　　對(duì)當(dāng)前節(jié)點(diǎn)的右子樹進(jìn)行后序遍歷；

　　訪問根節(jié)點(diǎn);

　　如下圖所示：

　　遞歸方式實(shí)現(xiàn)如下：　

　const bt = require('./tree')
　　// 遞歸版
　　function postorder(root) {
　　if (!root) return
　　postorder(root.left)
　　postorder(root.right)
　　console.log(root.val)
　　}
　　postorder(bt)
　　/** 結(jié)果
　　D E B H I F G C A
　　*/

　　迭代方式實(shí)現(xiàn)如下：

　　// 非遞歸版
　　function postorder(root) {
　　if (!root) return
　　const outputStack = []
　　const stack = [root]
　　while (stack.length) {
　　const node = stack.pop()
　　outputStack.push(node)
　　// 這里先入left需要保證left后出，在stack中后出，就是在outputStack棧中先出
　　node.left && stack.push(node.left)
　　node.right && stack.push(node.right)
　　}
　　while (outputStack.length) {
　　const node = outputStack.pop()
　　console.log(node.val)
　　}
　　}
　　postorder(bt)
　　/** 結(jié)果
　　D E B H I F G C A
　　*/

　　關(guān)于二叉樹及各種遍歷算法相關(guān)內(nèi)容已講述完畢。