樹在計(jì)算機(jī)領(lǐng)域中也有著廣泛的應(yīng)用，例如在編譯程序中，用樹來表示源程序的語法結(jié)構(gòu)；在數(shù)據(jù)庫系統(tǒng)中，可用樹來組織信息；在分析算法的行為時(shí)，可用樹來描述其執(zhí)行過程等等
首先看看樹的一些概念：1.樹（Tree）是n（n>=0）個(gè)結(jié)點(diǎn)的有限集。在任意一棵非空樹中：
?。?）有且僅有一個(gè)特定的稱為根（Root）的結(jié)點(diǎn)；
?。?）當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,T3,…Tm，其中每一個(gè)集合本身又是一棵樹，并且稱為根的子樹（Subtree）。
例如，（a）是只有一個(gè)根結(jié)點(diǎn)的樹；（b）是有13個(gè)結(jié)點(diǎn)的樹，其中A是根，其余結(jié)點(diǎn)分成3個(gè)互不相交的子集：T1={B,E,F,K,L},t2={D,H,I,J,M};T1,T2和T3都是根A的子樹，且本身也是一棵樹。 
2.樹的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支。結(jié)點(diǎn)擁有的子樹數(shù)稱為結(jié)點(diǎn)的度（Degree）。例如，（b）中A的度為3，C的度為1，F(xiàn)的度為0.度為0的結(jié)點(diǎn)稱為葉子（Leaf）或者終端結(jié)點(diǎn)。度不為0的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)。樹的度是樹內(nèi)各結(jié)點(diǎn)的度的最大值。（b）的樹的度為3.結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子（Child）。相應(yīng)的，該結(jié)點(diǎn)稱為孩子的雙親（Parent）。同一個(gè)雙親的孩子之間互稱兄弟（Sibling）。結(jié)點(diǎn)的祖先是從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。反之，以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。
3.結(jié)點(diǎn)的層次（Level）從根開始定義起，根為第一層，跟的孩子為第二層。若某結(jié)點(diǎn)在第l層，則其子樹的根就在第l+1層。其雙親在同一層的結(jié)點(diǎn)互為堂兄弟。例如，結(jié)點(diǎn)G與E，F(xiàn),H,I,J互為堂兄弟。樹中結(jié)點(diǎn)的最大層次稱為樹的深度（Depth）或高度。（b）的樹的深度為4。
4.如果將樹中結(jié)點(diǎn)的各子樹看成從左至右是有次序的（即不能交換），則稱該樹為有序樹，否則稱為無序樹。在有序樹中最左邊的子樹的根稱為第一個(gè)孩子，最右邊的稱為最后一個(gè)孩子。
5.森林（Forest）是m（m>=0）棵互不相交的樹的集合。對樹中每個(gè)結(jié)點(diǎn)而言，其子樹的集合即為森林。
接下來看看二叉樹相關(guān)的概念：
二叉樹（Binary Tree）是另一種樹型結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有兩棵子樹（即二叉樹中不存在度大于2的結(jié)點(diǎn)），并且，二叉樹的子樹有左右之分（其次序不能任意顛倒。）
二叉樹的性質(zhì)：
1.在二叉樹的第i層上至多有2的i-1次方個(gè)結(jié)點(diǎn)(i>=1)。
2.深度為k的二叉樹至多有2的k次方-1個(gè)結(jié)點(diǎn)，(k>=1)。
3.對任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0 = n2 + 1;
一棵深度為k且有2的k次方-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。
深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號從1至n的結(jié)點(diǎn)一一對應(yīng)時(shí)，稱之為完全二叉樹。
下面是完全二叉樹的兩個(gè)特性：
4.具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為Math.floor(log 2 n) + 1
5.如果對一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹（其深度為Math.floor(log 2 n) + 1）的結(jié)點(diǎn)按層序編號（從第1層到第Math.floor(2 n) + 1，每層從左到右），則對任一結(jié)點(diǎn)（1<=i<=n）有：
(1)如果i=1，則結(jié)點(diǎn)i、是二叉樹的根，無雙親；如果i>1，則其雙親parent(i)是結(jié)點(diǎn)Math.floor(i/2)。
(2)如果2i > n，則結(jié)點(diǎn)i無左孩子（結(jié)點(diǎn)i為葉子結(jié)點(diǎn)）；否則其左孩子LChild(i)是結(jié)點(diǎn)2i.
(3)如果2i + 1 > n，則結(jié)點(diǎn)i無右孩子；否則其右孩子RChild(i)是結(jié)點(diǎn)2i + 1; 
二叉樹的存儲結(jié)構(gòu)
1.順序存儲結(jié)構(gòu)
用一組連續(xù)的存儲單元依次自上而下，自左至右存儲完全二叉樹上的結(jié)點(diǎn)元素，即將二叉樹上編號為i的結(jié)點(diǎn)元素存儲在加上定義的一維數(shù)組中下標(biāo)為i-1的分量中?！?”表示不存在此結(jié)點(diǎn)。這種順序存儲結(jié)構(gòu)僅適用于完全二叉樹。
因?yàn)椋谧顗那闆r下，一個(gè)深度為k且只有k個(gè)結(jié)點(diǎn)的單支樹（樹中不存在度為2的結(jié)點(diǎn)）卻需要長度為2的n次方-1的一維數(shù)組。
2.鏈?zhǔn)酱鎯Y(jié)構(gòu)
二叉樹的結(jié)點(diǎn)由一個(gè)數(shù)據(jù)元素和分別指向其左右子樹的兩個(gè)分支構(gòu)成，則表示二叉樹的鏈表中的結(jié)點(diǎn)至少包含三個(gè)域：數(shù)據(jù)域和左右指針域。有時(shí)，為了便于找到結(jié)點(diǎn)的雙親，則還可在結(jié)點(diǎn)結(jié)構(gòu)中增加一個(gè)指向其雙親結(jié)點(diǎn)的指針域。利用這兩種結(jié)構(gòu)所得的二叉樹的存儲結(jié)構(gòu)分別稱之為二叉鏈表和三叉鏈表。
在含有n個(gè)結(jié)點(diǎn)的二叉鏈表中有n+1個(gè)空鏈域，我們可以利用這些空鏈域存儲其他有用信息，從而得到另一種鏈?zhǔn)酱鎯Y(jié)構(gòu)—線索鏈表。
二叉樹的遍歷主要分三種：
先（根）序遍歷：根左右
中（根）序遍歷：左根右
后（根）序遍歷：左右根
二叉樹的順序存儲結(jié)構(gòu)：
二叉樹的鏈?zhǔn)酱鎯π问剑?/p>
// 順序存儲結(jié)構(gòu)
var tree = [1, 2, 3, 4, 5, , 6, , , 7];
// 鏈?zhǔn)酱鎯Y(jié)構(gòu)
function BinaryTree(data, leftChild, rightChild) {
this.data = data || null;
// 左右孩子結(jié)點(diǎn)
this.leftChild = leftChild || null;
this.rightChild = rightChild || null;
}遍歷二叉樹(Traversing Binary Tree)：是指按指定的規(guī)律對二叉樹中的每個(gè)結(jié)點(diǎn)訪問一次且僅訪問一次。
1.先序遍歷二叉樹
1)算法的遞歸定義是：
若二叉樹為空，則遍歷結(jié)束；否則
?、?訪問根結(jié)點(diǎn)；
?、?先序遍歷左子樹(遞歸調(diào)用本算法)；
?、?先序遍歷右子樹(遞歸調(diào)用本算法)。
算法實(shí)現(xiàn)：
// 順序存儲結(jié)構(gòu)的遞歸先序遍歷
var tree = [1, 2, 3, 4, 5, , 6, , , 7]; console.log('preOrder:');
void function preOrderTraverse(x, visit) {
visit(tree[x]);
if (tree[2 * x + 1]) preOrderTraverse(2 * x + 1, visit);
if (tree[2 * x + 2]) preOrderTraverse(2 * x + 2, visit);
}(0, function (value) {
console.log(value);
});
// 鏈?zhǔn)酱鎯Y(jié)構(gòu)的遞歸先序遍歷
BinaryTree.prototype.preOrderTraverse = function preOrderTraverse(visit) {
visit(this.data);
if (this.leftChild) preOrderTraverse.call(this.leftChild, visit);
if (this.rightChild) preOrderTraverse.call(this.rightChild, visit);
};2)非遞歸算法:
設(shè)T是指向二叉樹根結(jié)點(diǎn)的變量，非遞歸算法是： 若二叉樹為空，則返回；否則，令p=T；
(1) p為根結(jié)點(diǎn)；
(2) 若p不為空或者棧不為空；
(3) 若p不為空，訪問p所指向的結(jié)點(diǎn), p進(jìn)棧, p = p.leftChild，訪問左子樹；
(4) 否則；退棧到p，然后p = p.rightChild, 訪問右子樹
(5) 轉(zhuǎn)(2)，直到棧空為止。
代碼實(shí)現(xiàn)：
// 鏈?zhǔn)酱鎯Φ姆沁f歸先序遍歷
// 方法1
BinaryTree.prototype.preOrder_stack = function (visit) {
var stack = new Stack();
stack.push(this);
while (stack.top) {
var p; // 向左走到盡頭
while ((p = stack.peek())) {
p.data && visit(p.data);
stack.push(p.leftChild);
}
stack.pop();
if (stack.top) {
p = stack.pop();
stack.push(p.rightChild);
}
}
}; // 方法2
BinaryTree.prototype.preOrder_stack2 = function (visit) {
var stack = new Stack();
var p = this;
while (p || stack.top) {
if (p) {
stack.push(p);
p.data && visit(p.data);
p = p.leftChild;
} else {
p = stack.pop();
p = p.rightChild;
}
}
};2.中序遍歷二叉樹：
1）算法的遞歸定義是：
若二叉樹為空，則遍歷結(jié)束；否則
?、?中序遍歷左子樹(遞歸調(diào)用本算法)；
?、?訪問根結(jié)點(diǎn)；
?、?中序遍歷右子樹(遞歸調(diào)用本算法)。
// 順序存儲結(jié)構(gòu)的遞歸中序遍歷
var tree = [1, 2, 3, 4, 5, , 6, , , 7];
console.log('inOrder:');
void function inOrderTraverse(x, visit) {
if (tree[2 * x + 1]) inOrderTraverse(2 * x + 1, visit);
visit(tree[x]);
if (tree[2 * x + 2]) inOrderTraverse(2 * x + 2, visit);
}(0, function (value) {
console.log(value);
});
// 鏈?zhǔn)酱鎯Φ倪f歸中序遍歷
BinaryTree.prototype.inPrderTraverse = function inPrderTraverse(visit) {
if (this.leftChild) inPrderTraverse.call(this.leftChild, visit);
visit(this.data);
if (this.rightChild) inPrderTraverse.call(this.rightChild, visit);
};2) 非遞歸算法
T是指向二叉樹根結(jié)點(diǎn)的變量，非遞歸算法是： 若二叉樹為空，則返回；否則，令p=T
?、?若p不為空，p進(jìn)棧， p=p.leftChild ；
?、?否則(即p為空)，退棧到p，訪問p所指向的結(jié)點(diǎn)，p=p.rightChild ；
⑶ 轉(zhuǎn)(1)；
直到棧空為止。
// 方法1
inOrder_stack1: function (visit) {
var stack = new Stack();
stack.push(this);
while (stack.top) {
var p; // 向左走到盡頭
while ((p = stack.peek())) {
stack.push(p.leftChild);
}
stack.pop();
if (stack.top) {
p = stack.pop();
p.data && visit(p.data);
stack.push(p.rightChild);
}
}
}, // 方法2
inOrder_stack2: function (visit) {
var stack = new Stack();
var p = this;
while (p || stack.top) {
if (p) {
stack.push(p);
p = p.leftChild;
} else {
p = stack.pop();
p.data && visit(p.data);
p = p.rightChild;
}
}
},3.后序遍歷二叉樹:
1)遞歸算法
若二叉樹為空，則遍歷結(jié)束；否則
?、?后序遍歷左子樹(遞歸調(diào)用本算法)；
⑵ 后序遍歷右子樹(遞歸調(diào)用本算法) ；
⑶ 訪問根結(jié)點(diǎn) 。
// 順序存儲結(jié)構(gòu)的遞歸后序遍歷
var tree = [1, 2, 3, 4, 5, , 6, , , 7];
console.log('postOrder:');
void function postOrderTraverse(x, visit) {
if (tree[2 * x + 1]) postOrderTraverse(2 * x + 1, visit);
if (tree[2 * x + 2]) postOrderTraverse(2 * x + 2, visit);
visit(tree[x]);
}(0, function (value) {
console.log(value);
});
// 鏈?zhǔn)酱鎯Φ倪f歸后序遍歷
BinaryTree.prototype.postOrderTraverse = function postOrderTraverse(visit) {
if (this.leftChild) postOrderTraverse.call(this.leftChild, visit);
if (this.rightChild) postOrderTraverse.call(this.rightChild, visit);
visit(this.data);
};2) 非遞歸算法
在后序遍歷中，根結(jié)點(diǎn)是最后被訪問的。因此，在遍歷過程中，當(dāng)搜索指針指向某一根結(jié)點(diǎn)時(shí)，不能立即訪問，而要先遍歷其左子樹，此時(shí)根結(jié)點(diǎn)進(jìn)棧。當(dāng)其左子樹遍歷完后再搜索到該根結(jié)點(diǎn)時(shí)，還是不能訪問，還需遍歷其右子樹。所以，此根結(jié)點(diǎn)還需再次進(jìn)棧，當(dāng)其右子樹遍歷完后再退棧到到該根結(jié)點(diǎn)時(shí)，才能被訪問。 因此，設(shè)立一個(gè)狀態(tài)標(biāo)志變量mark：
mark=0表示剛剛訪問此結(jié)點(diǎn)，mark=1表示左子樹處理結(jié)束返回，
mark=2表示右子樹處理結(jié)束返回。每次根據(jù)棧頂?shù)膍ark域決定做何動作
算法實(shí)現(xiàn)思路：
(1) 根結(jié)點(diǎn)入棧，且mark = 0;
(2) 若棧不為空，出棧到node；
(3) 若node的mark = 0，修改當(dāng)前node的mark為1，左子樹入棧；
(4) 若node的mark = 1，修改當(dāng)前node的mark為2，右子樹入棧；
(5) 若node的mark = 2，訪問當(dāng)前node結(jié)點(diǎn)的值；
(6) 直到棧為空結(jié)束。
postOrder_stack: function (visit) {
var stack = new Stack();
stack.push([this, 0]);
while (stack.top) {
var a = stack.pop();
var node = a[0];
switch (a[1]) {
case 0:
stack.push([node, 1]); // 修改mark域
if (node.leftChild) stack.push([node.leftChild, 0]); // 訪問左子樹
break;
case 1:
stack.push([node, 2]);
if (node.rightChild) stack.push([node.rightChild, 0]);
break;
case 2:
node.data && visit(node.data);
break;
default:
break;
}
}
}<html>
<head>
<meta charset="utf-8">
<title>文檔標(biāo)題</title>
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
<meta name="renderer" content="webkit">
<meta name="keywords" content="your keywords">
<meta name="description" content="your description">
<link rel="shortcut icon" type="image/ico" href="/favicon.ico" />
<meta name="viewport" content="width=device-width, initial-scale=1.0"></head><body>
<p class="container"></p>
<script>
// 順序存儲結(jié)構(gòu)
(function () {
// 順序存儲結(jié)構(gòu)的遍歷
var tree = ["a","b","c","d","e","f","g"];
console.log('preOrder:');
+function preOrderTraverse(x, visit) {
visit(tree[x]);
if (tree[2 * x + 1]) preOrderTraverse(2 * x + 1, visit);
if (tree[2 * x + 2]) preOrderTraverse(2 * x + 2, visit);
}(0, function (value) {
console.log(value);
});
console.log('inOrder:');
void function inOrderTraverse(x, visit) {
if (tree[2 * x + 1]) inOrderTraverse(2 * x + 1, visit);
visit(tree[x]);
if (tree[2 * x + 2]) inOrderTraverse(2 * x + 2, visit);
}(0, function (value) {
console.log(value);
});
console.log('postOrder:');
void function postOrderTraverse(x, visit) {
if (tree[2 * x + 1]) postOrderTraverse(2 * x + 1, visit);
if (tree[2 * x + 2]) postOrderTraverse(2 * x + 2, visit);
visit(tree[x]);
}(0, function (value) {
console.log(value);
});
}()); // 求從tree到node結(jié)點(diǎn)路徑的遞歸算法
function findPath(tree, node, path, i) {
var found = false;
void function recurse(tree, i) {
if (tree == node) {
found = true;
return;
}
path[i] = tree;
if (tree.leftChild) recurse(tree.leftChild, i + 1);
if (tree.rightChild && !found) recurse(tree.rightChild, i + 1);
if (!found) path[i] = null;
}(tree, i);
} var global = Function('return this;')();
</script>
</body>
</html>聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com
Copyright ? 2019-2024 51dongshi.com 版權(quán)所有
違法及侵權(quán)請聯(lián)系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市萬商天勤律師事務(wù)所王興未律師提供法律服務(wù)
