JavaScript數(shù)據(jù)結(jié)構(gòu)和算法之二叉樹(shù)詳解
二叉樹(shù)的概念
二叉樹(shù)（Binary Tree）是n（n>=0）個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集（空二叉樹(shù)），或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的、分別稱為根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。
二叉樹(shù)的特點(diǎn)
每個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，所以二叉樹(shù)中不存在度大于2的結(jié)點(diǎn)。二叉樹(shù)中每一個(gè)節(jié)點(diǎn)都是一個(gè)對(duì)象，每一個(gè)數(shù)據(jù)節(jié)點(diǎn)都有三個(gè)指針，分別是指向父母、左孩子和右孩子的指針。每一個(gè)節(jié)點(diǎn)都是通過(guò)指針相互連接的。相連指針的關(guān)系都是父子關(guān)系。
二叉樹(shù)節(jié)點(diǎn)的定義
二叉樹(shù)節(jié)點(diǎn)定義如下：
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
};
二叉樹(shù)的五種基本形態(tài)
空二叉樹(shù)
只有一個(gè)根結(jié)點(diǎn)
根結(jié)點(diǎn)只有左子樹(shù)
根結(jié)點(diǎn)只有右子樹(shù)
根結(jié)點(diǎn)既有左子樹(shù)又有右子樹(shù)
擁有三個(gè)結(jié)點(diǎn)的普通樹(shù)只有兩種情況：兩層或者三層。但由于二叉樹(shù)要區(qū)分左右，所以就會(huì)演變成如下的五種形態(tài)：
特殊二叉樹(shù)
斜樹(shù)
如上面倒數(shù)第一副圖的第2、3小圖所示。
滿二叉樹(shù)
在一棵二叉樹(shù)中，如果所有分支結(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有葉子都在同一層上，這樣的二叉樹(shù)稱為滿二叉樹(shù)。如下圖所示：
完全二叉樹(shù)
完全二叉樹(shù)是指最后一層左邊是滿的，右邊可能滿也可能不滿，然后其余層都是滿的。一個(gè)深度為k，節(jié)點(diǎn)個(gè)數(shù)為 2^k - 1 的二叉樹(shù)為滿二叉樹(shù)（完全二叉樹(shù)）。就是一棵樹(shù)，深度為k，并且沒(méi)有空位。
完全二叉樹(shù)的特點(diǎn)有：
葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層。
最下層的葉子一定集中在左部連續(xù)位置。
倒數(shù)第二層，若有葉子結(jié)點(diǎn)，一定都在右部連續(xù)位置。
如果結(jié)點(diǎn)度為1，則該結(jié)點(diǎn)只有左孩子。
同樣結(jié)點(diǎn)樹(shù)的二叉樹(shù)，完全二叉樹(shù)的深度最小。
注意：滿二叉樹(shù)一定是完全二叉樹(shù)，但完全二叉樹(shù)不一定是滿二叉樹(shù)。
算法如下：
bool is_complete(tree *root)
{
queue q;
tree *ptr;
// 進(jìn)行廣度優(yōu)先遍歷（層次遍歷），并把NULL節(jié)點(diǎn)也放入隊(duì)列
q.push(root);
while ((ptr = q.pop()) != NULL)
{
q.push(ptr->left);
q.push(ptr->right);
}
// 判斷是否還有未被訪問(wèn)到的節(jié)點(diǎn)
while (!q.is_empty())
{
ptr = q.pop();
// 有未訪問(wèn)到的的非NULL節(jié)點(diǎn)，則樹(shù)存在空洞，為非完全二叉樹(shù)
if (NULL != ptr)
{
return false;
}
}
return true;
}
二叉樹(shù)的性質(zhì)
二叉樹(shù)的性質(zhì)一：在二叉樹(shù)的第i層上至多有2^(i-1)個(gè)結(jié)點(diǎn)(i>=1)
二叉樹(shù)的性質(zhì)二：深度為k的二叉樹(shù)至多有2^k-1個(gè)結(jié)點(diǎn)(k>=1)
二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)
二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)就是用一維數(shù)組存儲(chǔ)二叉樹(shù)中的各個(gè)結(jié)點(diǎn)，并且結(jié)點(diǎn)的存儲(chǔ)位置能體現(xiàn)結(jié)點(diǎn)之間的邏輯關(guān)系。
二叉鏈表
既然順序存儲(chǔ)方式的適用性不強(qiáng)，那么我們就要考慮鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)啦。二叉樹(shù)的存儲(chǔ)按照國(guó)際慣例來(lái)說(shuō)一般也是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的。
二叉樹(shù)每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子，所以為它設(shè)計(jì)一個(gè)數(shù)據(jù)域和兩個(gè)指針域是比較自然的想法，我們稱這樣的鏈表叫做二叉鏈表。
二叉樹(shù)的遍歷
二叉樹(shù)的遍歷(traversing binary tree)是指從根結(jié)點(diǎn)出發(fā)，按照某種次序依次訪問(wèn)二叉樹(shù)中所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問(wèn)一次且僅被訪問(wèn)一次。
二叉樹(shù)的遍歷有三種方式，如下：
（1）前序遍歷（DLR），首先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)。簡(jiǎn)記根-左-右。
（2）中序遍歷（LDR），首先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)。簡(jiǎn)記左-根-右。
（3）后序遍歷（LRD），首先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。簡(jiǎn)記左-右-根。
前序遍歷：
若二叉樹(shù)為空，則空操作返回，否則先訪問(wèn)根結(jié)點(diǎn)，然后前序遍歷左子樹(shù)，再前序遍歷右子樹(shù)。
遍歷的順序?yàn)椋篈 B D H I E J C F K G
//先序遍歷
function preOrder(node){
if(!node == null){
putstr(node.show()+ " ");
preOrder(node.left);
preOrder(node.right);
}
}
中序遍歷：
若樹(shù)為空，則空操作返回，否則從根結(jié)點(diǎn)開(kāi)始（注意并不是先訪問(wèn)根結(jié)點(diǎn)），中序遍歷根結(jié)點(diǎn)的左子樹(shù)，然后是訪問(wèn)根結(jié)點(diǎn)，最后中序遍歷右子樹(shù)。
遍歷的順序?yàn)椋篐 D I B E J A F K C G
//使用遞歸方式實(shí)現(xiàn)中序遍歷
function inOrder(node){
if(!(node == null)){
inOrder(node.left);//先訪問(wèn)左子樹(shù)
putstr(node.show()+ " ");//再訪問(wèn)根節(jié)點(diǎn)
inOrder(node.right);//最后訪問(wèn)右子樹(shù)
}
}
后序遍歷：
若樹(shù)為空，則空操作返回，否則從左到右先葉子后結(jié)點(diǎn)的方式遍歷訪問(wèn)左右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。
遍歷的順序?yàn)椋篐 I D J E B K F G C A
//后序遍歷
function postOrder(node){
if(!node == null){
postOrder(node.left);
postOrder(node.right);
putStr(node.show()+ " ");
}
}
實(shí)現(xiàn)二叉查找樹(shù)
二叉查找樹(shù)（BST）由節(jié)點(diǎn)組成，所以我們定義一個(gè)Node節(jié)點(diǎn)對(duì)象如下：
function Node(data,left,right){
this.data = data;
this.left = left;//保存left節(jié)點(diǎn)鏈接
this.right = right;
this.show = show;
}
function show(){
return this.data;//顯示保存在節(jié)點(diǎn)中的數(shù)據(jù)
}
查找最大和最小值
查找BST上的最小值和最大值非常簡(jiǎn)單，因?yàn)檩^小的值總是在左子節(jié)點(diǎn)上，在BST上查找最小值，只需遍歷左子樹(shù)，直到找到最后一個(gè)節(jié)點(diǎn)
查找最小值
function getMin(){
var current = this.root;
while(!(current.left == null)){
current = current.left;
}
return current.data;
}
該方法沿著B(niǎo)ST的左子樹(shù)挨個(gè)遍歷，直到遍歷到BST最左的節(jié)點(diǎn)，該節(jié)點(diǎn)被定義為：
current.left = null;
這時(shí)，當(dāng)前節(jié)點(diǎn)上保存的值就是最小值
查找最大值
在BST上查找最大值只需要遍歷右子樹(shù)，直到找到最后一個(gè)節(jié)點(diǎn)，該節(jié)點(diǎn)上保存的值就是最大值。
function getMax(){
var current = this.root;
while(!(current.right == null)){
current = current.right;
}
return current.data;
}
- JavaScript數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)的刪除算法示例
- JavaScript數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)的查找算法示例
- JavaScript數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)的遍歷算法示例
- JavaScript數(shù)據(jù)結(jié)構(gòu)之二叉樹(shù)的計(jì)數(shù)算法示例
- JavaScript數(shù)據(jù)結(jié)構(gòu)與算法之二叉樹(shù)遍歷算法詳解【先序、中序、后序】
- JavaScript數(shù)據(jù)結(jié)構(gòu)與算法之二叉樹(shù)插入節(jié)點(diǎn)、生成二叉樹(shù)示例
- JavaScript數(shù)據(jù)結(jié)構(gòu)與算法之二叉樹(shù)實(shí)現(xiàn)查找最小值、最大值、給定值算法示例
- JavaScript數(shù)據(jù)結(jié)構(gòu)與算法之檢索算法實(shí)例分析【順序查找、最大最小值、自組織查詢】
- JavaScript數(shù)據(jù)結(jié)構(gòu)與算法之二叉樹(shù)添加/刪除節(jié)點(diǎn)操作示例
相關(guān)文章
javascript 學(xué)習(xí)筆記（一）DOM基本操作
主要是為了使自己更加熟練操作DOM，記錄自己的點(diǎn)滴，規(guī)范自己的代碼！希望大家共同進(jìn)步！2011-04-04
在組件上使用 wx:for 控制屬性綁定一個(gè)數(shù)組，即可使用數(shù)組中各項(xiàng)的數(shù)據(jù)重復(fù)渲染該組件。這篇文章主要介紹了微信小程序wx:for循環(huán)的相關(guān)知識(shí),需要的朋友可以參考下2018-10-10
關(guān)于base64加密/解密...2006-12-12
JavaScript實(shí)現(xiàn)多維數(shù)組、對(duì)象數(shù)組排序,其實(shí)用的就是原生的sort()方法,用于對(duì)數(shù)組的元素進(jìn)行排序。今天我們就來(lái)詳細(xì)探討下sort（）方法2014-10-10
好多朋友剛開(kāi)始接觸網(wǎng)絡(luò)，不懂后綴為js的文件，是什么文件，其實(shí)這個(gè)擴(kuò)展名為.js的文件就是javascript文件2007-12-12
querySelector() 方法僅僅返回匹配指定選擇器的第一個(gè)元素。如果你需要返回所有的元素，請(qǐng)使用 querySelectorAll() 方法替代2016-12-12
下面小編就為大家?guī)?lái)一篇前端js文件合并的三種方式推薦。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-05-05
這篇文章主要介紹了詳解JavaScript的策略模式編程,包括函數(shù)和類(lèi)作為策略的情況以及多環(huán)境下的策略模式,需要的朋友可以參考下2015-06-06
詳解JavaScript實(shí)現(xiàn)異步Ajax
本文詳細(xì)講解了JavaScript實(shí)現(xiàn)異步Ajax的方法，文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-05-05
這篇文章主要介紹了用JavaScript顯示瀏覽器客戶端信息的超相近教程,包含了從返回桌面瀏覽器客戶端內(nèi)核信息到移動(dòng)端瀏覽器以及其使用的系統(tǒng)版本信息等內(nèi)容,傾力推薦!需要的朋友可以參考下2015-06-06