前言

我們知道dom結構也是以樹的形式存在的，所以了解樹的這種數據結構對於我們分析前端代碼還是很重要的。

（當然這裡跟前端沾邊也是為了吸引大家學習的興趣，真相其實是我就單純的想寫這一章...(｡•ˇ‸ˇ•｡) ...）

廢話不多說，我們先從二叉排序樹開始學起吧。

二叉排序樹（BST Binary Search Tree）

什麼是二叉排序樹？

簡單來說，就是每一個點只能最多有兩個子節點。它有下面三個屬性：

• 若左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
• 若右子樹不空，則右子樹上所有結點的值均大於或等於它的根結點的值；
• 左、右子樹也分別為二叉排序樹，這點很重要，希望大家記住。

對於這顆樹來說，23是它的根節點。而一個父節點的兩個子節點分別稱為左節點跟右節點。在

二叉樹中，左邊的節點一定都小於23，右邊節點都大於等於23。

實現BST

BST由節點組成。所以先來看看節點的實現：

functionNode(data,left,right){this.data=data;this.left=left;this.right=right;this.show=function(){returnthis.data;}}

這個節點裡，傳入的data就是節點的數據。 left，right分別為左右子節點。

現在需要定義一個二叉查找樹（下面簡稱BST）的類，這個類有一個根節點root，和一個插入函數insert

functionBST(){this.root=null;this.insert=insert;}

難點在於這個插入函數，先拋開這個函數是如何寫的，我們先來想想BST是如何長成的。假設我需要在BST裡依次插入23,45,16,37,3,99,22這些數字，那麼插入的順序如下：

1. 第一個數字為根節點，即this.root = 23
2. 第二個數字為45，對比23，如果比23大，放在23的右邊節點。此時BST如下：

3.第三個數字為16，對比23，比23小，成為23的左節點。此時BST如下：

4.第四個數字為37，先對比23，比23大，放在右邊。右邊再看23的右節點有值，是45，

37比45小，所以放在45的左邊。

5.第五個數字為3，對比23，比23小，放左邊，再看左邊23的左節點16，3比16小，

所以放在16的左邊。

6.第六個數字為99，對比23，比23大，看23的右節點45，比45大，放在45的右節點

7. 第七個數字為22，對比23，比23小，看23的左節點16，比16大，放在16的右節點。

8.如果最後一個數字是100，對比23，比23大，看23的右節點45，比45大，再看45的右節點99，比99大，所以放在99的右節點處。

以上，就是一顆BST生成的過程。

接下來我們用計算機的語言描述一下上述過程:（以插入右邊節點為例）

1. 針對第一個節點，直接將它設置成根節點。
2. 設置一個指針parent用於追踪當前的父節點。
3. 節點跟當前的parent進行對比，如果> parent, 看parent.right 是否有值，沒有的話，成功找到當前節點n的位置，即parent.right = n，此時終止程序。
4. 如果parent.right有值，這麼這個parent.right就會成為最新的parent，在重複3步驟。

下面我們用JS來實現一下上述過程：

JS代碼實現

functioninsert(data){varn=newNode(data,null,null);if(!this.root){this.root=n;}else{//使用current的指針來探索子節點varcurrent=this.root;while(true){varparent=current;if(data<parent.data){current=current.left;if(!current){parent.left=n;break;}}else{current=current.right;if(!current){parent.right=n;break;}}}}}

這樣我們這個BST的類就完成啦~~

運行上面的代碼：

varnums=newBST();nums.insert(23);nums.insert(45);nums.insert(16);nums.insert(37);nums.insert(3);nums.insert(99);nums.insert(100);console.log(nums)

在將結果nums打印出來,如果你得到了這樣的數據結構，那麼恭喜你，你的BST生成成功啦。

( >﹏<。)～

遍歷

遍歷分為前序，中序，以及後序遍歷，他們的命名是以根節點的訪問次序劃分的：

前序遍歷：根節點->左子樹->右子樹中序遍歷：左子樹->根節點->右子樹後序遍歷：左子樹->右子樹->根節點

以我們剛剛生成的BST為例：

前序遍歷：23 16 3 22 45 37 99

中序遍歷：3 16 22 23 37 45 99 （這時候就會發現：臥槽，6的飛起啊，這不就是升序的排列麼）

後序遍歷：3 22 16 37 99 45 23

怎麼理解呢？以中序遍歷為例，由於中序遍歷遵循：左子樹->根節點->右子樹

所以這顆樹的排列順序為16（左子樹） -> 23(根節點) -> 45(右子樹)

/ /

3 22 37 99

在看左子樹，開篇的時候我們說過，左右字數都依舊是BST，所以對於左右子樹，都還是遵循這個排序：左子樹->根節點->右子樹；

那麼，對於左字樹來說，排序順序為3 -> 16 -> 22, 對於右字樹，排列順序是37 -> 45 -> 99。

連起來就是3 16 22 23 37 45 99。

前序跟後序同理。

下一篇，我們將了解如何使用算法完成這三種遍歷，而且要從遞歸函數講起，大家可以先自己思考一下~

本文有幫助的話，點個贊鼓勵一下作者唄ლ(＾ω＾ლ)

參考資料：

1、《數據結構與算法JS描述》