樹(shù)
8.1 樹(shù)的相關(guān)術(shù)語(yǔ)
- 位于樹(shù)頂部的節(jié)點(diǎn)叫做根節(jié)點(diǎn)
- 內(nèi)部節(jié)點(diǎn)(至少有一個(gè)子節(jié)點(diǎn))和外部節(jié)點(diǎn)(沒(méi)有子節(jié)點(diǎn))
- 節(jié)點(diǎn)的深度，取決于它祖先節(jié)點(diǎn)的個(gè)數(shù)
- 樹(shù)的高度取決于所有節(jié)點(diǎn)深度的最大值
- 鍵是樹(shù)中對(duì)節(jié)點(diǎn)的稱呼
8.2 二叉樹(shù)和二叉搜索樹(shù)
- 二叉樹(shù)的節(jié)點(diǎn)最多只能有兩個(gè)子節(jié)點(diǎn)
- 一個(gè)是左側(cè)子節(jié)點(diǎn)
- 一個(gè)是右側(cè)子節(jié)點(diǎn)
- ==有助于寫(xiě)出更高效的向樹(shù)中插入，查找和刪除節(jié)點(diǎn)的算法==
- 二叉搜索樹(shù)是二叉樹(shù)的一種
- 只允許在左側(cè)節(jié)點(diǎn)存儲(chǔ)比父節(jié)點(diǎn)小的值
- 在右側(cè)節(jié)點(diǎn)存儲(chǔ)比父節(jié)點(diǎn)大的值
// 創(chuàng)建二叉搜索樹(shù)類
function BinarySearchTree() {
// 聲明Node類來(lái)表示樹(shù)中的每個(gè)節(jié)點(diǎn)
var Node = function (key) {
this.key = key;
this.left = null;
this.right = null;
};
// 根元素
var root = null;
/*
insert(key): 向樹(shù)中插入一個(gè)新的鍵
search(key): 在樹(shù)中查找一個(gè)鍵颜凯，存在返回true,否則false
inOrderTraverse: 通過(guò)中序遍歷方式遍歷所有節(jié)點(diǎn)
preOrderTraverse: 通過(guò)先序遍歷方式遍歷所有節(jié)點(diǎn)
postOrderTraverse:通過(guò)后序遍歷方式遍歷所有節(jié)點(diǎn)
min:返回樹(shù)中最小的值/鍵
max:返回樹(shù)中最大的值/鍵
remove(key):從樹(shù)中移除某個(gè)鍵
*/
var insertNode = function (node, newNode) {
if (newNode.key < node.key) {
if (node.left === null) {
node.left = newNode;
} else {
insertNode(node.left, newNode);
}
} else {
if (node.right === null) {
node.right = newNode;
} else {
insertNode(node.right, newNode);
}
}
};
// insert(key)
this.insert = function (key) {
var newNode = new Node(key);
if (root === null) {
root = newNode;
} else {
insertNode(root, newNode);
}
};
}
8.3 樹(shù)的遍歷
中序遍歷就是從最小到最大的順序訪問(wèn)所有節(jié)點(diǎn)簿盅。
應(yīng)用于對(duì)樹(shù)進(jìn)行排序操作
this.inOrderTraverse = function(callback) {
inOrderTraverseNode(root, callback);
};
function inOrderTraverseNode(node, callback) {
if (node !== null) {
inOrderTraverseNode(node.left, callback);
callback(node.key);
inOrderTraverseNode(node.right, callback);
}
}
先序遍歷是以優(yōu)先于后代節(jié)點(diǎn)的順序訪問(wèn)每個(gè)節(jié)點(diǎn)
應(yīng)用于打印一個(gè)結(jié)構(gòu)化的文檔
this.preOrderTraverse = function (callback) {
preOrderTraverseNode(root, callback);
};
function preOrderTraverseNode(node, callback) {
if (node !== null) {
callback(node.key);
preOrderTraverseNode(node.left, callback);
preOrderTraverseNode(node.right, callback);
}
}
后序遍歷是先訪問(wèn)節(jié)點(diǎn)的后代節(jié)點(diǎn)驱敲，再訪問(wèn)節(jié)點(diǎn)本身
應(yīng)用于計(jì)算一個(gè)目錄和它的子目錄中所有文件所占空間的大小
this.postOrderTraverse = function (callback) {
postOrderTraverseNode(root, callback);
};
function postOrderTraverseNode(node, callback) {
if (node !== null) {
postOrderTraverseNode(node.left, callback);
postOrderTraverseNode(node.right, callback);
callback(node.key);
}
}
function printNode(val) {
console.log(val);
}
// 使用二叉搜索樹(shù)類
var tree = new BinarySearchTree();
tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.insert(20);
tree.insert(18);
tree.insert(25);
tree.insert(6);
// 中序遍歷肋坚，從小到大
// tree.inOrderTraverse(printNode);
// 先序遍歷
// tree.preOrderTraverse(printNode);
// 后序遍歷
tree.postOrderTraverse(printNode);
搜索樹(shù)中的值
在樹(shù)中项棠，有三種經(jīng)常執(zhí)行的搜索類型
最大值柄延、最小值蚀浆、搜索特定的值
// 最小值
var minNode = function (node) {
if (node) {
while (node && node.left !== null) {
node = node.left
}
return node.key;
}
return null;
};
this.min = function () {
return minNode(root);
};
// 最大值
var maxNode = function (node) {
if (node) {
while (node && node.right !== null) {
node = node.right;
}
return node.key;
}
return null;
};
this.max = function () {
return maxNode(root);
}
// 搜索一個(gè)特定的值
var searchNode = function (node, key) {
if (node === null) {
return false;
}
if (key < node.key) {
return searchNode(node.left, key);
} else if (key > node.key) {
return searchNode(node.right, key);
} else {
return true;
}
};
this.search = function (key) {
return searchNode(root, key);
};
// 移除一個(gè)節(jié)點(diǎn)
var removeNode = function (node, key) {
if (node === null) {
return null;
}
if (key < node.key) {
node.left = removeNode(node.left, key);
return node;
} else if (key > node.key) {
node.right = removeNode(node.right, key);
return node;
} else { // 鍵等于node.key
// 第一種情況——一個(gè)外部節(jié)點(diǎn)(無(wú)子節(jié)點(diǎn))
if (node.left === null && node.right === null) {
node = null;
return node;
}
// 第二種情況——一個(gè)只有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)
if (node.left === null) {
node = node.right;
return node;
} else if (node.right === null) {
node = node.left;
return node;
}
// 第三種情況——一個(gè)有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)
var aux = findMinNode(node.right);
node.key = aux.key;
node.right = removeNode(node.right, axu.key);
return node;
}
};
function findMinNode(node) {
if (node) {
while (node && node.left !== null) {
node = node.left;
}
return node;
}
return null;
}
this.remove = function (key) {
root = removeNode(root, key);
};
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
