樹在計算機領域中也有著廣泛的應用，例如在編譯程序中，用樹來表示源程序的語法結構；在數據庫系統中，可用樹來組織信息；在分析算法的行為時，可用樹來描述其執行過程等等
首先看看樹的一些概念：1.樹（Tree）是n（n>=0）個結點的有限集。在任意一棵非空樹中：
（1）有且僅有一個特定的稱為根（Root）的結點；
（2）當n>1時，其余結點可分為m(m>0)個互不相交的有限集T1,T2,T3,…Tm，其中每一個集合本身又是一棵樹，并且稱為根的子樹（Subtree）。
例如，（a）是只有一個根結點的樹；（b）是有13個結點的樹，其中A是根，其余結點分成3個互不相交的子集：T1={B,E,F,K,L},t2={D,H,I,J,M};T1,T2和T3都是根A的子樹，且本身也是一棵樹。 
2.樹的結點包含一個數據元素及若干指向其子樹的分支。結點擁有的子樹數稱為結點的度（Degree）。例如，（b）中A的度為3，C的度為1，F的度為0.度為0的結點稱為葉子（Leaf）或者終端結點。度不為0的結點稱為非終端結點或分支結點。樹的度是樹內各結點的度的最大值。（b）的樹的度為3.結點的子樹的根稱為該結點的孩子（Child）。相應的，該結點稱為孩子的雙親（Parent）。同一個雙親的孩子之間互稱兄弟（Sibling）。結點的祖先是從根到該結點所經分支上的所有結點。反之，以某結點為根的子樹中的任一結點都稱為該結點的子孫。
3.結點的層次（Level）從根開始定義起，根為第一層，跟的孩子為第二層。若某結點在第l層，則其子樹的根就在第l+1層。其雙親在同一層的結點互為堂兄弟。例如，結點G與E，F,H,I,J互為堂兄弟。樹中結點的最大層次稱為樹的深度（Depth）或高度。（b）的樹的深度為4。
4.如果將樹中結點的各子樹看成從左至右是有次序的（即不能交換），則稱該樹為有序樹，否則稱為無序樹。在有序樹中最左邊的子樹的根稱為第一個孩子，最右邊的稱為最后一個孩子。
5.森林（Forest）是m（m>=0）棵互不相交的樹的集合。對樹中每個結點而言，其子樹的集合即為森林。
接下來看看二叉樹相關的概念：
二叉樹（Binary Tree）是另一種樹型結構，它的特點是每個結點至多只有兩棵子樹（即二叉樹中不存在度大于2的結點），并且，二叉樹的子樹有左右之分（其次序不能任意顛倒。）
二叉樹的性質：
1.在二叉樹的第i層上至多有2的i-1次方個結點(i>=1)。
2.深度為k的二叉樹至多有2的k次方-1個結點，(k>=1)。
3.對任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點數為n2，則n0 = n2 + 1;
一棵深度為k且有2的k次方-1個結點的二叉樹稱為滿二叉樹。
深度為k的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應時，稱之為完全二叉樹。
下面是完全二叉樹的兩個特性：
4.具有n個結點的完全二叉樹的深度為Math.floor(log 2 n) + 1
5.如果對一棵有n個結點的完全二叉樹（其深度為Math.floor(log 2 n) + 1）的結點按層序編號（從第1層到第Math.floor(2 n) + 1，每層從左到右），則對任一結點（1<=i<=n）有：
(1)如果i=1，則結點i、是二叉樹的根，無雙親；如果i>1，則其雙親parent(i)是結點Math.floor(i/2)。
(2)如果2i > n，則結點i無左孩子（結點i為葉子結點）；否則其左孩子LChild(i)是結點2i.
(3)如果2i + 1 > n，則結點i無右孩子；否則其右孩子RChild(i)是結點2i + 1; 
二叉樹的存儲結構
1.順序存儲結構
用一組連續的存儲單元依次自上而下，自左至右存儲完全二叉樹上的結點元素，即將二叉樹上編號為i的結點元素存儲在加上定義的一維數組中下標為i-1的分量中。“0”表示不存在此結點。這種順序存儲結構僅適用于完全二叉樹。
因為，在最壞情況下，一個深度為k且只有k個結點的單支樹（樹中不存在度為2的結點）卻需要長度為2的n次方-1的一維數組。
2.鏈式存儲結構
二叉樹的結點由一個數據元素和分別指向其左右子樹的兩個分支構成，則表示二叉樹的鏈表中的結點至少包含三個域：數據域和左右指針域。有時，為了便于找到結點的雙親，則還可在結點結構中增加一個指向其雙親結點的指針域。利用這兩種結構所得的二叉樹的存儲結構分別稱之為二叉鏈表和三叉鏈表。
在含有n個結點的二叉鏈表中有n+1個空鏈域，我們可以利用這些空鏈域存儲其他有用信息，從而得到另一種鏈式存儲結構—線索鏈表。
二叉樹的遍歷主要分三種：
先（根）序遍歷：根左右
中（根）序遍歷：左根右
后（根）序遍歷：左右根
二叉樹的順序存儲結構：
二叉樹的鏈式存儲形式：
// 順序存儲結構
var tree = [1, 2, 3, 4, 5, , 6, , , 7];
// 鏈式存儲結構
function BinaryTree(data, leftChild, rightChild) {
this.data = data || null;
// 左右孩子結點
this.leftChild = leftChild || null;
this.rightChild = rightChild || null;
}遍歷二叉樹(Traversing Binary Tree)：是指按指定的規律對二叉樹中的每個結點訪問一次且僅訪問一次。
1.先序遍歷二叉樹
1)算法的遞歸定義是：
若二叉樹為空，則遍歷結束；否則
⑴ 訪問根結點；
⑵ 先序遍歷左子樹(遞歸調用本算法)；
⑶ 先序遍歷右子樹(遞歸調用本算法)。
算法實現：
// 順序存儲結構的遞歸先序遍歷
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);
});
// 鏈式存儲結構的遞歸先序遍歷
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)非遞歸算法:
設T是指向二叉樹根結點的變量，非遞歸算法是： 若二叉樹為空，則返回；否則，令p=T；
(1) p為根結點；
(2) 若p不為空或者棧不為空；
(3) 若p不為空，訪問p所指向的結點, p進棧, p = p.leftChild，訪問左子樹；
(4) 否則；退棧到p，然后p = p.rightChild, 訪問右子樹
(5) 轉(2)，直到棧空為止。
代碼實現：
// 鏈式存儲的非遞歸先序遍歷
// 方法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）算法的遞歸定義是：
若二叉樹為空，則遍歷結束；否則
⑴ 中序遍歷左子樹(遞歸調用本算法)；
⑵ 訪問根結點；
⑶ 中序遍歷右子樹(遞歸調用本算法)。
// 順序存儲結構的遞歸中序遍歷
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);
});
// 鏈式存儲的遞歸中序遍歷
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是指向二叉樹根結點的變量，非遞歸算法是： 若二叉樹為空，則返回；否則，令p=T
⑴ 若p不為空，p進棧， p=p.leftChild ；
⑵ 否則(即p為空)，退棧到p，訪問p所指向的結點，p=p.rightChild ；
⑶ 轉(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)遞歸算法
若二叉樹為空，則遍歷結束；否則
⑴ 后序遍歷左子樹(遞歸調用本算法)；
⑵ 后序遍歷右子樹(遞歸調用本算法) ；
⑶ 訪問根結點 。
// 順序存儲結構的遞歸后序遍歷
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);
});
// 鏈式存儲的遞歸后序遍歷
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) 非遞歸算法
在后序遍歷中，根結點是最后被訪問的。因此，在遍歷過程中，當搜索指針指向某一根結點時，不能立即訪問，而要先遍歷其左子樹，此時根結點進棧。當其左子樹遍歷完后再搜索到該根結點時，還是不能訪問，還需遍歷其右子樹。所以，此根結點還需再次進棧，當其右子樹遍歷完后再退棧到到該根結點時，才能被訪問。 因此，設立一個狀態標志變量mark：
mark=0表示剛剛訪問此結點，mark=1表示左子樹處理結束返回，
mark=2表示右子樹處理結束返回。每次根據棧頂的mark域決定做何動作
算法實現思路：
(1) 根結點入棧，且mark = 0;
(2) 若棧不為空，出棧到node；
(3) 若node的mark = 0，修改當前node的mark為1，左子樹入棧；
(4) 若node的mark = 1，修改當前node的mark為2，右子樹入棧；
(5) 若node的mark = 2，訪問當前node結點的值；
(6) 直到棧為空結束。
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>文檔標題</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>
// 順序存儲結構
(function () {
// 順序存儲結構的遍歷
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結點路徑的遞歸算法
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>聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com
Copyright ? 2019-2025 51dongshi.com 版權所有
違法及侵權請聯系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市萬商天勤律師事務所王興未律師提供法律服務
