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