點擊下載
本文文檔

當(dāng)前位置：首頁 - 科技 - 知識百科 - 正文

JavaScript二叉樹（二叉搜索樹）的詳細(xì)介紹

來源：懂視網(wǎng) 責(zé)編：小采時間：2020-11-27 19:28:16

JavaScript二叉樹（二叉搜索樹）的詳細(xì)介紹

JavaScript二叉樹（二叉搜索樹）的詳細(xì)介紹:本篇文章給大家?guī)淼膬?nèi)容是關(guān)于JavaScript二叉樹（二叉搜索樹）的詳細(xì)介紹，有一定的參考價值，有需要的朋友可以參考一下，希望對你有所幫助?？赡苡幸徊糠秩藳]有讀過我上一篇寫的二叉堆，所以這里把二叉樹的基本概念復(fù)制過來了，如果讀過的人可以忽略前面針

推薦度：

點擊下載本文 文檔為doc格式

導(dǎo)讀JavaScript二叉樹（二叉搜索樹）的詳細(xì)介紹:本篇文章給大家?guī)淼膬?nèi)容是關(guān)于JavaScript二叉樹（二叉搜索樹）的詳細(xì)介紹，有一定的參考價值，有需要的朋友可以參考一下，希望對你有所幫助。可能有一部分人沒有讀過我上一篇寫的二叉堆，所以這里把二叉樹的基本概念復(fù)制過來了，如果讀過的人可以忽略前面針

本篇文章給大家?guī)淼膬?nèi)容是關(guān)于JavaScript二叉樹（二叉搜索樹）的詳細(xì)介紹，有一定的參考價值，有需要的朋友可以參考一下，希望對你有所幫助。

可能有一部分人沒有讀過我上一篇寫的二叉堆，所以這里把二叉樹的基本概念復(fù)制過來了，如果讀過的人可以忽略前面針對二叉樹基本概念的介紹，另外如果對鏈表數(shù)據(jù)結(jié)構(gòu)不清楚的最好先看一下本人之前寫的js數(shù)據(jù)結(jié)構(gòu)-鏈表

二叉樹

二叉樹(Binary Tree)是一種樹形結(jié)構(gòu)，它的特點是每個節(jié)點最多只有兩個分支節(jié)點，一棵二叉樹通常由根節(jié)點，分支節(jié)點，葉子節(jié)點組成。而每個分支節(jié)點也常常被稱作為一棵子樹。

根節(jié)點：二叉樹最頂層的節(jié)點

分支節(jié)點：除了根節(jié)點以外且擁有葉子節(jié)點

葉子節(jié)點：除了自身，沒有其他子節(jié)點

常用術(shù)語
在二叉樹中，我們常常還會用父節(jié)點和子節(jié)點來描述，比如圖中2為6和3的父節(jié)點，反之6和3是2子節(jié)點

二叉樹的三個性質(zhì)

在二叉樹的第i層上，至多有2^i-1個節(jié)點
i=1時，只有一個根節(jié)點，2^(i-1) = 2^0 = 1
深度為k的二叉樹至多有2^k-1個節(jié)點
i=2時，2^k-1 = 2^2 - 1 = 3個節(jié)點
對任何一棵二叉樹T，如果總結(jié)點數(shù)為n0，度為2(子樹數(shù)目為2)的節(jié)點數(shù)為n2,則n0=n2+1

樹和二叉樹的三個主要差別

樹的節(jié)點個數(shù)至少為1，而二叉樹的節(jié)點個數(shù)可以為0

樹中節(jié)點的最大度數(shù)(節(jié)點數(shù)量)沒有限制,而二叉樹的節(jié)點的最大度數(shù)為2

樹的節(jié)點沒有左右之分，而二叉樹的節(jié)點有左右之分

二叉樹分類

二叉樹分為完全二叉樹(complete binary tree)和滿二叉樹(full binary tree)

滿二叉樹：一棵深度為k且有2^k - 1個節(jié)點的二叉樹稱為滿二叉樹

完全二叉樹：完全二叉樹是指最后一層左邊是滿的，右邊可能滿也可能不滿，然后其余層都是滿的二叉樹稱為完全二叉樹(滿二叉樹也是一種完全二叉樹)

二叉搜索樹

二叉搜索樹滿足以下的幾個性質(zhì)：

若任意節(jié)點的左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值；

若任意節(jié)點的右子樹不空，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值；

任意節(jié)點的左、右子樹也需要滿足左邊小右邊大的性質(zhì)

我們來舉個例子來深入理解以下

一組數(shù)據(jù)：12,4,18,1,8,16,20
由下圖可以看出，左邊的圖滿足了二叉樹的性質(zhì)，它的每個左子節(jié)點都小于父節(jié)點，右子節(jié)點大于其父節(jié)點，同時左子樹的節(jié)點都小于根節(jié)點，右子樹的節(jié)點都大于根節(jié)點

二叉搜索樹主要的幾個操作：

查找（search）

插入（insert）

遍歷（transverse）

二叉樹搜索樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)

通過下圖，可以知道二叉搜索樹的節(jié)點通常包含4個域，數(shù)據(jù)元素，分別指向其左，右節(jié)點的指針和一個指向父節(jié)點的指針?biāo)鶚?gòu)成，一般把這種存儲結(jié)構(gòu)稱為三叉鏈表。
圖片描述

用代碼初始化一個二叉搜索樹的結(jié)點：

一個指向父親節(jié)點的指針 parent

一個指向左節(jié)點的指針 left

一個指向右節(jié)點的指針 right

一個數(shù)據(jù)元素，里面可以是一個key和value

 class BinaryTreeNode {
 constructor(key, value){
 this.parent = null;
 this.left = null;
 this.right = null;
 this.key = key;
 this.value = value;
 }
 }

接著我們再用代碼去初始化一個二叉搜索樹

在二叉搜索樹中我們會維護(hù)一個root指針，這個就相當(dāng)于鏈表中的head指針，在沒有任何節(jié)點插入的時候它指向空，在有節(jié)點插入以后它指向根節(jié)點。

 class BinarySearchTree {
 constructor() {
 this.root = null;
 }
 }

創(chuàng)建節(jié)點

 static createNode(key, value) {
 return new BinarySearchTree(key, value);
 }

插入操作

看下面這張圖，13是我們要插入的節(jié)點，它插入的具體步驟：

跟根節(jié)點12做比較，比12大，所以我們確定了，這個節(jié)點是往右子樹插入的
而根節(jié)點的右邊已經(jīng)有節(jié)點，那么跟這個節(jié)點18做比較，結(jié)果小于18所以往18的左節(jié)點找位置
而18的左節(jié)點也已經(jīng)有節(jié)點了，所以繼續(xù)跟這個節(jié)點做比較，結(jié)果小于16
剛好16的左節(jié)點是空的(left=null)，所以13這個節(jié)點就插入到了16的左節(jié)點

通過上面的描述，我們來看看代碼是怎么寫的

定義兩個指針，分別是p和tail，最初都指向root，p是用來指向要插入的位置的父節(jié)點的指針，而tail是用來查找插入位置的，所以最后它會指向null，用上圖舉個例子，p最后指向了6這個節(jié)點，而tail最后指向了null（tail為null則說明已經(jīng)找到了要插入的位置）

循環(huán)，tail根據(jù)我們上面分析的一步一步往下找位置插入，如果比當(dāng)前節(jié)點小就往左找，大則往右找，一直到tail找到一個空位置也就是null

如果當(dāng)前的root為null，則說明當(dāng)前結(jié)構(gòu)中并沒有節(jié)點，所以插入的第一個節(jié)點直接為跟節(jié)點，即this.root = node

將插入后的節(jié)點的parent指針指向父節(jié)點

 insert(node){
 let p = this.root;
 let tail = this.root;
 
 // 循環(huán)遍歷，去找到對應(yīng)的位置
 while(tail) {
 p = tail;
 // 要插入的節(jié)點key比當(dāng)前節(jié)點小
 if (node.key < tail.key){
 tail.left = tail.left;
 }
 // 要插入的節(jié)點key比當(dāng)前節(jié)點大
 else {
 tail.right = tail.right;
 }
 }
 
 // 沒有根節(jié)點，則直接作為根節(jié)點插入
 if(!p) {
 this.root = node;
 return;
 }
 
 // p是最后一個節(jié)點，也就是我們要插入的位置的父節(jié)點
 // 比父節(jié)點大則往右邊插入
 if(p.key < node.key){
 p.right = node;
 }
 // 比父節(jié)點小則往左邊插入
 else {
 p.left = node;
 }
 
 // 指向父節(jié)點
 node.parent = p;

 }

查找

查找就很簡單了，其實和插入差多，都是去別叫左右節(jié)點的大小，然后往下找

如果root = null, 則二叉樹中沒有任何節(jié)點，直接return，或者報個錯什么的。

循環(huán)查找

 search(key) {
 let p = this.root;
 if(!p) {
 return;
 }
 
 while(p && p.key !== key){
 if(p.key<key){
 p = p.right;
 }else{
 p = p.left;
 }
 }
 
 return p;
 }

遍歷

中序遍歷(inorder)：先遍歷左節(jié)點，再遍歷自己，最后遍歷右節(jié)點，輸出的剛好是有序的列表

前序遍歷(preorder)：先自己，再遍歷左節(jié)點，最后遍歷右節(jié)點

后序遍歷(postorder)：先左節(jié)點，再右節(jié)點，最后自己

最常用的一般是中序遍歷，因為中序遍歷可以得到一個已經(jīng)排好序的列表，這也是為什么會用二叉搜索樹排序的原因

根據(jù)上面對中序遍歷的解釋，那么代碼就變的很簡單，就是一個遞歸的過程，遞歸停止的條件就是節(jié)點為null

先遍歷左節(jié)點-->yield* this._transverse(node.left)

遍歷自己 --> yield* node

遍歷左節(jié)點 --> yield* this._transverse(node.right)

 transverse() {
 return this._transverse(this.root);
 }
 
 *_transverse(node){
 if(!node){
 return;
 }
 yield* this._transverse(node.left);
 yield node;
 yield* this._transverse(node.right)
 }

看上面這張圖，我們簡化的來看一下，先訪問左節(jié)點4，再自己12，然后右節(jié)點18，這樣輸出的就剛好是一個12，4，8

補充：這個地方用了generater，所以返回的一個迭代器。可以通過下面這種方式得到一個有序的數(shù)組，這里的前提就當(dāng)是已經(jīng)有插入的節(jié)點了

 const tree = new BinaryTree();
 //...中間省略插入過程
 
 // 這樣就返回了一個有序的數(shù)組 
 var arr = [...tree.transverse()].map(item=>item.key);

完整代碼

class BinaryTreeNode {
 constructor(key, value) {
 // 指向父節(jié)點
 this.p = null;

 // 左節(jié)點
 this.left = null;

 // 右節(jié)點
 this.right = null;

 // 鍵
 this.key = key;

 // 值
 this.value = value;
 }
}

class BinaryTree {
 constructor() {
 this.root = null;
 }

 static createNode(key, value) {
 return new BinaryTreeNode(key, value);
 }

 search(key) {
 let p = this.root;
 if (!p) {
 return;
 }

 while (p && p.key !== key) {
 if (p.key < key) {
 p = p.right;
 } else {
 p = p.left;
 }
 }

 return p;
 }

 insert(node) {
 // 尾指針的父節(jié)點指針
 let p = this.root;

 // 尾指針
 let tail = this.root;

 while (tail) {
 p = tail;
 if (node.key < tail.key) {
 tail = tail.left;
 } else {
 tail = tail.right;
 }
 }

 if (!p) {
 this.root = node;
 return;
 }

 // 插入
 if (p.key < node.key) {
 p.right = node;
 } else {
 p.left = node;
 }

 node.p = p;
 }

 transverse() {
 return this.__transverse(this.root);
 }

 *__transverse(node) {
 if (!node) {
 return;
 }
 yield* this.__transverse(node.left);
 yield node;
 yield* this.__transverse(node.right);
 }
}