溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文實例講述了JavaScript實現二叉樹定義、遍歷及查找的方法。分享給大家供大家參考，具體如下：
二叉樹（binary tree）
在寫這篇文章之前說一下數據結構和算法這個系列，這個系列包含了很多東西，比如啥子排序，線性表，廣義表，樹，圖這些大家都是知道的，但是這些東西我們學了之后工作中能用到的又有多少呢，據我所知絕大部分公司，一線碼農，屌絲，程序猿是用不到這些東西，既然這樣為啥子我還要強調這個系列呢，本人覺得算法和數據結構是程序的基本功，前提想脫離一線碼農，普通程序猿行列，說得通俗一點就是讓自己變的更牛逼。其次語言都是想通的，只要是掌握了一門語言學習其他語言就如同順水推舟，不費一點力氣。另外還有一點就是我會一直把這個系列寫下去， 雖然網上一搜一大筐，已經寫爛了，但是我寫作的目的有兩個，第一和大家分享， 第二可以讓自己更深入的理解。好了，其他的不多說了，最近復習了一下二叉樹， 就先寫這個，后面會依次的加上排序， 線性表，廣義表。。。。等等
二叉樹
一說到二叉樹我們肯定會問，什么是二叉樹，二叉樹是個啥子東東，拿來有啥子用嘛，我們為啥子要學習它嘛？ 如果當初你在學習二叉樹的時候你沒有問過自己這些問題，那么你對它的了解也僅僅也只是了解。那我們現在來說說什么是二叉樹，二叉樹就是一種數據結構， 它的組織關系就像是自然界中的樹一樣。官方語言的定義是：是一個有限元素的集合,該集合或者為空、或者由一個稱為根的元素及兩個不相交的、被分別稱為左子樹和右子樹的二叉樹組成。至于為啥子要學習它，媽媽總是說，孩子，等你長大了就明白了。
二叉樹的性質
性質1：二叉樹第i層上的節點數目最多為2i-1(i≥1);
性質2：深度為k的二叉樹至多有2k-1個結點(k≥1)。
性質3： 在任意-棵二叉樹中，若葉子結點（即度為0的結點）的個數為n0，度為1的結點數為n1，度為2的結點數為n2，則no=n2+1。
二叉樹的存儲結構與構建
二叉樹的存儲方式有兩種，一種順序存儲，比如:
var binaryTree = ['a', 'b', 'c', 'd', 'e', 'f', 'h', 'i']; 這就是一顆二叉樹，假設binaryTree[i]是二叉樹的一個節點，那么它的左孩子節點 leftChild = binaryTree[i*2+1]那么相應的右孩子節點 rightChild = binaryTree[i*2+2]; 一般情況下順序存儲的這種結構用的較少，另外一種存儲方式就是鏈式存儲，下面我會用代碼來詳細描述二叉樹式結構的構建與存儲方式，構建二叉樹也有兩種方式一種是遞歸方式構建，這種很簡單，另一種是非遞歸方法構建，這種呢相對于前一種復雜一點點，不過也不用擔心，我在代碼中加上詳細的注釋，一步一步的走下去。我們現在就以26個英文字母來構建二叉樹
在構建二叉樹之前我們會用到一個節點對象，節點對象如下：（注意：關于javascript的面向對象，原型，語法特點我會放在javascript語言知識點這個系列）
/*
*二叉樹的節點對象
*/
function Node() {
this.text = ''; //節點的文本
this.leftChild = null; //節點的左孩子引用
this.rightChild = null; //節點右孩子引用
}
遞歸構建二叉樹
在構建好二叉樹節點之后我們緊接著用遞歸來構建二叉樹
var charecters = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'];
function buildTree(node, i) {
var leftIndex = 2*i+1, //左孩子節點的索引
rightIndex = 2*i+2; //右孩子節點的索引
if(leftIndex < charecters.length) { //判斷索引的長度是否超過了charecters數組的大小
var childNode = new Node(); //創建一個新的節點對象
childNode.text = charecters[leftIndex]; //給節點賦值
node.leftChild = childNode; //給當前節點node加入左孩子節點
buildTree(childNode, leftIndex); //遞歸創建左孩子
}
if(rightIndex < charecters.length) { //下面注釋參照上面的構建左孩子的節點
var childNode = new Node();
childNode.text = charecters[rightIndex];
node.rightChild = childNode;
buildTree(childNode, rightIndex);
}
}
//下面構造二叉樹
var node = new Node();
node.text = charecters[0];
buildTree(node, 0); //索引i是從0開始構建
非遞歸構建二叉樹
下面是以非遞歸方式構建二叉樹：
var root;
function createBinaryTree() {
var len = charecters.length, //數組的長度
index = 0, //索引從0開始
nodes = new Array(); //創建一個臨時數組，用于存放二叉樹節點
//循環創建二叉樹節點存放到數組中
for (var i = 0 ; i < charecters.length ; i++) {
var node = new Node();
node.text = charecters[i];
nodes.push(node);
}
//循環建立二叉樹子節點的引用
while(index < len) {
var leftIndex = 2*index+1, //當前節點左孩子索引
rightIndex = 2*index+2; //當前節點右孩子索引
//給當前節點添加左孩子
nodes[index].leftChild = nodes[leftIndex];
//給當前節點添加右孩子
nodes[index].rightChild = nodes[rightIndex];
index++;
}
root = nodes[0];
}
二叉樹的三種遍歷
好了，現在我們已經成功構建了二叉樹的鏈式結構，在構建了二叉樹的鏈式結構后我們進入二叉樹的最基本的遍歷了，遍歷有三種最基本的遍歷，我不說想必大家都知道，先序遍歷，中序遍歷和后續遍歷。雖然這三種遍歷遞歸方式都比較簡單，但非遞歸方式就不是那么容易了，當時我在實現的時候都卡了半天，真的是說起來容易做起來難啊，在實現遍歷前我們首先要來實現的是棧，因為在非遞歸遍歷的時候會用到棧，那到底什么是棧呢，這里我就簡單介紹下吧，有興趣的朋友可以去維基百科有權威的定義，棧和隊列也是一種數據結構，棧存放數據的時候是先進先出，而隊列是先進后出。
實現棧的對象
下面用javascript來實現棧的對象
function Stack() {
var stack = new Array(); //存放棧的數組
//壓棧
this.push = function(o) {
stack.push(o);
};
//出棧
this.pop = function() {
var o = stack[stack.length-1];
stack.splice(stack.length-1, 1);
return o;
};
//檢查棧是否為空
this.isEmpty = function() {
if(stack.length <= 0) {
return true;
}
else {
return false;
}
};
}
//使用方式如下
var stack = new Stack();
stack.push(1); //現在棧中有一個元素
stack.isEmpty(); //false , 棧不為空
alert(stack.pop()); //出棧, 打印1
stack.isEmpty(); //true, 此時棧為空，因為在調用了stack.pop()之后元素出棧了，所以為空
1. 先序遍歷
在實現了棧對象以后我們首先來進行先序遍歷的遞歸方式
function firstIteration(node) {
if(node.leftChild) { //判斷當前節點是否有左孩子
firstIteration(node.leftChild); //遞歸左孩子
}
if(node.rightChild) { //判斷當前節點是否有右孩子
firstIteration(node.rightChild); //遞歸右孩子
}
}
//遞歸遍歷二叉樹
firstIteration(root);
先序遍歷的非遞歸方式
上面的代碼大家可以在firstIteration()方法中加個alert()函數來驗證是否正確。那么下面就要說說先序遍歷的非遞歸方式，遍歷思想是這樣的：先訪問根節點在訪問左節點， 最后訪問右節點。從根節點一直往下訪問找左孩子節點，直到最后一個左孩子節點（將這條路徑保存到棧中），然后再訪問最后一個左孩子的兄弟節點（右孩子節點），之后回溯到上一層（將棧中的元素取出 就是出棧），又開始從該節點（回溯到上一層的節點）一直往下訪問找左孩子節點... 直到棧中的元素為空，循環結束。
function notFirstIteration(node) {
var stack = new Stack(), //開辟一個新的棧對象
resultText = ''; //存放非遞歸遍歷之后的字母順序
stack.push(root); //這個root在上面非遞歸方式構建二叉樹的時候已經構建好的
var node = root;
resultText += node.text;
while(!stack.isEmpty()) {
while(node.leftChild) { //判斷當前節點是否有左孩子節點
node = node.leftChild; //取當前節點的左孩子節點
resultText += node.text; //訪問當前節點
stack.push(node); //將當前節點壓入棧中
}
stack.pop(); //出棧
node = stack.pop().rightChild; //訪問當前節點的兄弟節點（右孩子節點）
if(node) { //當前節點的兄弟節點不為空
resultText += node.text; //訪問當前節點
stack.push(node); //將當前節點壓入棧中
}
else { //當前節點的兄弟節點為空
node = stack.pop(); //在回溯到上一層
}
}
}
//非遞歸先序遍歷
notFirstIteration(root);
2. 中序遍歷
只要把思路理清楚了現實起來其實還是挺容易的，只要我們熟悉了一種二叉樹的非遞歸遍歷方式，其他幾種非遞歸方式就容易多了，照著葫蘆畫瓢，下面是中序遍歷的遞歸方式，中序遍歷的思想是：先訪問左孩子節點，在訪問根節點，最后訪問右節點
var strText = "";
function secondIteration(node) {
//訪問左節點
if(node.leftChild) {
if(node.leftChild.leftChild) {
secondIteration(node.leftChild);
}
else {
strText += node.leftChild.text;
}
}
//訪問根節點
strText += node.text;
//訪問右節點
if(node.rightChild) {
if(node.rightChild.leftChild) {
secondIteration(node.rightChild);
}
else {
strText += node.rightChild.text;
}
}
}
secondIteration(root);
alert(strText);
中序遍歷的非遞歸方式
思想是：1. 從根節點一直往下找左孩子節點，直到找到最后一個左孩子節點（用棧將此路徑保存，但不訪問）2.訪問最后一個左孩子節點，然后再訪問根節點（要先彈出棧，就是在棧中取上一層節點）3.在訪問當前節點（最后一個左孩子節點）的兄弟節點（右孩子節點），這里要注意如果兄弟節點是一個葉節點就直接訪問，否則是兄弟節點是一顆子樹的話不能馬上訪問，要先來重復 1， 2，3步驟， 直到棧為空，循環結束
function notSecondIteration() {
var resultText = '',
stack = new Stack(),
node = root;
stack.push(node);
while(!stack.isEmpty()) {
//從根節點一直往下找左孩子節點直到最后一個左孩子節點，然后保存在棧中
while(node.leftChild) {
node = node.leftChild;
stack.push(node);
}
//彈出棧
var tempNode = stack.pop();
//訪問臨時節點
resultText += tempNode.text;
if(tempNode.rightChild) {
node = tempNode.rightChild;
stack.push(node);
}
}
alert(resultText);
}
3. 后續遍歷
最后就還剩下一種遍歷方式，二叉樹的后續遍歷，后續遍歷的思想是：先訪問左孩子節點，然后在訪問右孩子節點，最后訪問根節點
后續遍歷的遞歸方式
var strText = '';
function lastIteration(node) {
//首先訪問左孩子節點
if(node.leftChild) {
if(node.leftChild.leftChild) {
lastIteration(node.leftChild);
}
else {
strText += node.leftChild.text;
}
}
//然后再訪問右孩子節點
if(node.rightChild) {
if(node.rightChild.rightChild) {
lastIteration(node.rightChild);
}
else {
strText += node.rightChild.text;
}
}
//最后訪問根節點
strText += node.text;
}
//中序遞歸遍歷
lastIteration(root);
alert(strText);
后續非遞歸遍歷
后續非遞歸遍歷的思想是：1.從根節點一直往下找左孩子節點，直到最后一個左孩子節點（將路徑保存到棧中，但不訪問）2.彈出棧訪問最后一個左孩子節點 3.進入最后一個左孩子節點的兄弟節點，如果兄弟節點是葉節點就訪問它，否則將該節點重復 1， 2步驟, 直到棧中的元素為空，循環結束。3.訪問根節點
function notLastIteration() {
var strText = '',
stack = new Stack();
nodo = root;
stack.push(node);
while(!stack.isEmpty()) {
while(node.leftChild) {
node = node.leftChild;
stack.push(node);
}
//彈出棧
var tempNode = stack.pop();
//訪問左孩子節點
strText += tempNode.text;
//訪問右孩子節點
if(tempNode.rightChild) {
if(tempNode.rightChild.leftChild || tempNode.rightChild.rightChild) { //判斷最后一個左孩子節點的兄弟節點是否為頁節點
stack.push(tempNode.rightChild);
}
else {
strText += tempNode.rightChild.text;
}
}
}
alert(strText);
}
更多關于JavaScript相關內容感興趣的讀者可查看本站專題：《JavaScript數據結構與算法技巧總結》、《JavaScript數學運算用法總結》、《JavaScript排序算法總結》、《JavaScript遍歷算法與技巧總結》、《JavaScript查找算法技巧總結》及《JavaScript錯誤與調試技巧總結》
希望本文所述對大家JavaScript程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
