認(rèn)識二叉樹

普通樹與二叉樹的區(qū)別

首先把普通樹與二叉樹（Binary Tree）區(qū)別開來。普通樹能直觀地反映樹狀結(jié)構(gòu)的數(shù)據(jù)以及它們之間的關(guān)系，和我們普通認(rèn)知的樹那樣子的差不多，例如文件夾啊、分類啊、行政管理門類啊、族譜啊之類。而二叉樹，雖然也有個“樹”字，但更多的是為提高排序、搜索、插入、刪除速度而準(zhǔn)備的那么一種數(shù)據(jù)結(jié)構(gòu)。如果要用二叉樹去展示樹狀結(jié)構(gòu)，不是不行，它也可以從普通樹轉(zhuǎn)換為二叉樹，但是那樣的話會很別扭和不直觀，不便于理解。相同的地方是，二叉樹當(dāng)然也是樹結(jié)構(gòu)里面的一種，一般研究樹的方法也可以適用于二叉樹，例如樹的一些概念（根節(jié)點(diǎn)、父子節(jié)點(diǎn)、深度、度等等），還有搜索、遍歷（前序遍歷、中序遍歷、后序遍歷）等等。

二叉樹特點(diǎn)

二叉樹具有以下特點(diǎn)。

• 最大度數(shù)為 2，就是說子節(jié)點(diǎn)數(shù)只能是 0、1、2 這三種情況之一
• 為有序樹
• 比父節(jié)點(diǎn)小的放左邊，小的放右邊（如果相等的呢？好像是放右邊）
• 即使只有一個節(jié)點(diǎn)，也區(qū)分左右

如下例子。

5/ \3 6/ \ 1 4

下面是兩種特殊的二叉樹。

• 滿二叉樹（Full Binary Tree）：所有葉子在最后一層，且度數(shù)為 2。
• 完全二叉樹（Complete Binary Tree），又稱“近乎滿二叉樹”，所有葉子在最后一層或倒數(shù)第二層，且都是左節(jié)點(diǎn)。據(jù)說還有國內(nèi)和國外標(biāo)準(zhǔn)之分，參見這里。

為什么要有二叉樹？

沒有對比就沒有傷害。先看看數(shù)組結(jié)構(gòu)插入元素的時間復(fù)雜度為 O(N)，也就是說在頭部插入一個元素，那么數(shù)組里面所有的元素都要往后（往右邊）移動 N 次。在頭部插入是最壞的情況，開銷最大。刪除同理；再看看 Hash 或者 Map，插入或刪除都很快，時間復(fù)雜度為 O(1)，但致命弱點(diǎn)是無序的；鏈表呢？解決了數(shù)組插入刪除慢的缺點(diǎn)而且可以有序的，問題是查找挺慢的，時間復(fù)雜度為 O(N)。

那有沒有魚與熊掌都能兼顧的數(shù)據(jù)結(jié)構(gòu)呢？有～答案就是優(yōu)秀的“二叉樹”。這篇文章總結(jié)比較精辟，摘錄如下。

• 數(shù)組：按序號訪問元素，連續(xù)存儲，元素可以有序、也可以無序，用下標(biāo)來定位元素，元素的數(shù)量確定(有上限)，按下標(biāo)訪問很快，插入和刪除元素、排序的開銷比較大(元素的移位操作)，數(shù)組元素?zé)o序時，元素的排序速度比較慢(依次比較)，數(shù)組元素有序時，元素的查找速度比較慢(二分查找，比無序時快)。

• 鏈表：插入、刪除方便；元素?cái)?shù)量不受限制。非連續(xù)存儲，元素可以有序、也可以無序；查找、訪問元素的開銷比較大：依次比較每一個元素。元素的數(shù)量不受限制。插入和刪除元素、排序的開銷比較小(修改指針域)。

• 二叉樹：插入、刪除方便，查找快。非連續(xù)存儲，元素一定是有序(建樹時判定在左子樹、還是右子樹上需要有依據(jù))，查找、訪問元素的開銷比較小(比較次數(shù)不超過二叉樹的深度)，元素的數(shù)量不受限制，插入和刪除元素、排序的開銷比較小(修改指針)。

數(shù)組、鏈表、二叉樹各自適用的場合

• 數(shù)組：數(shù)據(jù)集中元素的數(shù)量基本可以確定；不需要頻繁的插入、刪除。
• 鏈表：需要頻繁的插入、刪除元素；不可預(yù)知元素的數(shù)量范圍。
• 二叉樹：需要頻繁的插入、刪除、查找元素。

那么代價呢？肯定有，那就是前期得花一些心智去轉(zhuǎn)換為二叉樹。當(dāng)然還有你的學(xué)習(xí)成本啦～

編碼

樹節(jié)點(diǎn)和樹

是為 TreeNode 也。key/value 字段類似于 Map。
/

*** 節(jié)點(diǎn)*/ class TreeNode {/*** 節(jié)點(diǎn)索引*/key: number;/*** 實(shí)際的內(nèi)容數(shù)據(jù)*/value: any;/*** 左子節(jié)點(diǎn)*/left?: TreeNode;/*** 右子節(jié)點(diǎn)*/right?: TreeNode;/*** 創(chuàng)建一個節(jié)點(diǎn)* * @param key 節(jié)點(diǎn)索引* @param value 實(shí)際的內(nèi)容數(shù)據(jù)*/constructor(key: number, value?: any) {this.key = key;if (value)this.value = value;} }

固然還需要一個樹 BinaryTree 。

/*** 樹*/ class BinaryTree {/*** 根節(jié)點(diǎn)*/public root: TreeNode | undefined;…… }

BinaryTree 下面 root 屬性表示根節(jié)點(diǎn)，當(dāng)然還有其他的操作方法，下面再講。

插入節(jié)點(diǎn)

詳細(xì)請見代碼和注釋。樹的定義本身就是遞歸定義，所以編碼時候經(jīng)常運(yùn)用到遞歸的思想。總之樹的結(jié)構(gòu)與遞歸之間的關(guān)系非常密切，——不管是現(xiàn)在的插入節(jié)點(diǎn)方法還是后面要提到的查找、遍歷等的操作方法，都能夠得到充分體現(xiàn)密切的關(guān)系。

/*** 插入節(jié)點(diǎn)。* 如果根節(jié)點(diǎn)為空，則插入到根節(jié)點(diǎn)。如果不是，插入到根節(jié)點(diǎn)下面* * @param newNode * @returns */ public insert(newNode: TreeNode): void {if (!this.root) {this.root = newNode;return;}this.insertNode(this.root, newNode); }/*** 實(shí)際的插入方法。這是一個遞歸的方法。* * @param node 被插入的父節(jié)點(diǎn)* @param newNode 插入的子節(jié)點(diǎn)*/ private insertNode(node: TreeNode, newNode: TreeNode): void {if (node.key > newNode.key) { // 比父節(jié)點(diǎn)小，插入在左邊if (node.left) {this.insertNode(node.left, newNode); // 如果非空，則要再一次判斷，插入到子節(jié)點(diǎn)下面return;}node.left = newNode;return;} else {// 比父節(jié)點(diǎn)大，插入在右邊if (node.right) {this.insertNode(node.right, newNode);// 如果非空，則要再一次判斷，插入到子節(jié)點(diǎn)下面return;}node.right = newNode;return;} }

遍歷

二叉樹一般有前序、中序以及后序三種遍歷方法，它們區(qū)別如下。

• 前序遍歷：父結(jié)點(diǎn) —> 左子樹 —> 右子樹
• 中序遍歷：左子樹—> 父結(jié)點(diǎn) —> 右子樹
• 后序遍歷：左子樹 —> 右子樹 —> 父結(jié)點(diǎn)

源碼不粘貼了。測試代碼如下。

// test let rootNode: TreeNode = new TreeNode(3, "B"); let tree: BinaryTree = new BinaryTree(); tree.insert(rootNode); tree.insert(new TreeNode(2, "B")); tree.insert(new TreeNode(1, "A")); tree.insert(new TreeNode(4, "B")); tree.insert(new TreeNode(5, "B"));

結(jié)果如圖所示。

這三種都屬于樹的深度遍歷。另外一種廣度遍歷的二叉樹也有，就是層次遍歷了，參見該文比較詳細(xì)。另外也有非遞歸版本的。

不過有個可以改進(jìn)的地方，就是加入一個 lambda 用于遍歷的時候?qū)嶋H執(zhí)行的邏輯。

查找

這個就是二叉樹驚艷的地方！查找非常快：由于大的在右邊，只需要一直尋找最右邊的就行了。尋找最小的也同理。

public findMax(): number {return this.root ? this.findMaxNode(this.root).key : 0; }public findMaxNode(node: TreeNode): TreeNode {if (node && node.right)return this.findMaxNode(node.right);return node; }public findMin(): number {return this.root ? this.findMinNode(this.root).key : 0; }public findMinNode(node: TreeNode): TreeNode {if (node && node.left)return this.findMinNode(node.left);return node; }

代碼雖超級簡單，——然而是不是深深嘆服于這結(jié)構(gòu)之精妙呢？

刪除節(jié)點(diǎn)

比較麻煩， TODO。

樹的深度和節(jié)點(diǎn)總數(shù)

如源碼所示。

/*** 獲取二叉樹節(jié)點(diǎn)個數(shù)* * @returns 二叉樹節(jié)點(diǎn)個數(shù)*/ public size(): number {return this.root ? this._size(this.root) : 0; }/*** * @param subTree * @returns */ private _size(subTree: TreeNode | undefined): number {if (!subTree)return 0;elsereturn 1 + this._size(subTree.left) + this._size(subTree.right); }/*** 獲取二叉樹層級數(shù)* * @returns 二叉樹層級數(shù)*/ public height(): number {return this.root ? this._height(this.root) : 0; }/*** * @param subTree * @returns */ private _height(subTree: TreeNode | undefined): number {if (!subTree)return 0;else {let i = this._height(subTree.left),j = this._height(subTree.right);return i < j ? (j + 1) : (i + 1);} }

求深度的話有個可讀性更好的版本：

public treeDepth (root: TreeNode) : number {// 一個二叉樹的深度為 左子樹深度和右子樹深度的最大值 + 1return (root === undefined || root.val === null) ? 0 : Math.max(this.treeDepth(root.left), this.treeDepth(root.right)) + 1 }

二叉樹的存儲

不太懂，TODO。

結(jié)語

二叉樹還有其他待學(xué)習(xí)的地方，例如 AVL 平衡二叉樹，非常重要，日后有機(jī)會再講。

本文源碼在：https://gitee.com/sp42_admin/ajaxjs/blob/master/aj-ts/src/data-stru/bin-tree.ts。

參考

• 簡單易懂的二叉樹實(shí)現(xiàn) https://zhuanlan.zhihu.com/p/87482994 非遞歸版本 https://zhuanlan.zhihu.com/p/87953541
• 很全面的二叉樹實(shí)現(xiàn) https://juejin.cn/post/6844903975595016200
• TS 算法集錦 https://github.com/Reaper622/DataStructure-Algorithm-TS

總結(jié)

以上是生活随笔為你收集整理的TypeScript 玩转二叉树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。