資訊專欄INFORMATION COLUMN
摘要：存在好幾種方式來表示這種數據結構。下面的示意圖展示了鄰接表數據結構。在關聯矩陣中矩陣的行表示頂點列表示邊。廣度優先搜索算法和深度優先搜索算法基本上是相同的只有一點不同那就是待訪問頂點列表的數據結構。
1 樹
一個樹結構包含一系列存在父子關系的節點。每個節點都有一個父節點(除了頂部的第一個節點)以及零個或多個子節點。位于樹頂部的節點叫作根節點(11)。它沒有父節點。樹中的每個元素都叫作節點,節點分 為內部節點和外部節點。至少有一個子節點的節點稱為內部節點。沒有子元素的節點稱為外部節點或葉節點。節點的一個屬性是深度,節點的深度取決于它的祖先節點的數量。樹的高度取決于所有節點深度的最大值。一棵樹也可以被分解成層級。根節點在第0層,它 的子節點在第1層,以此類推。
1.1 二叉樹和二叉搜索樹二叉樹中的節點最多只能有兩個子節點:一個是左側子節點,另一個是右側子節點。這些定義有助于我們寫出更高效的向樹中插入、查找和刪除節點的算法。
對于二叉搜索樹，我們一般需要實現如下方法：
insert(key): 向書中插入一個新的鍵。
search(key): 在樹中查找一個鍵，如果節點存在，則返回true，否則返回false。
inOrderTraverse: 通過中序遍歷方式遍歷所有節點。
preOrderTraverse: 通過先序遍歷方式遍歷所有節點。
postOrderTraverse: 通過后序遍歷方式遍歷所有節點。
min: 返回樹中最小的鍵/值。
max: 返回樹中最大的健/值。
remove(key): 從樹中移除某個鍵。
1.1.1 二叉搜索樹的遍歷二叉搜索樹(BST)是二叉樹的一種,但是它只允許你在左側節點存儲(比父節點)小的值, 在右側節點存儲(比父節點)大(或者等于)的值。
中序遍歷是一種以上行順序訪問BST所有節點的遍歷方式,也就是以從最小到最大的順序訪問所有節點。中序遍歷的一種應用就是對樹進行排序操作。
先序遍歷是以優先于后代節點的順序訪問每個節點的。先序遍歷的一種應用是打印一個結構化的文檔。先序遍歷和中序遍歷的不同點是,先序遍歷會先訪問節點本身,然后再訪問它的左側子節點，最后是右側子節點。
后序遍歷則是先訪問節點的后代節點,再訪問節點本身。后序遍歷的一種應用是計算一個目錄和它的子目錄中所有文件所占空間的大小。
樹中有三種經常執行的搜索類型，最小值，最大值，搜索特定的值。
1.1.2 二叉搜索樹的實現與基本使用下面的minNode方法允許我們從樹中任意一個節點開始尋找最小的鍵。我們可以使用它來找到一棵 樹或它的子樹中最小的鍵。因此,我們在調用minNode方法的時候傳入樹的根節點(行{1}), 因為我們想要找到整棵樹的最小鍵。
可以把代碼中的幾個內部方法也寫成二叉樹結構的屬性，這樣可以靈活引用。這里我們就不具體修改了。
function BinarySearchTree() {
function Node(key) {
this.key = key;
this.left = null;
this.right = null;
}
this.root = null;
if ((typeof this.insert !== "function") && (typeof this.insert !== "string")) {
//內部私有方法，用于插入節點
function insertNode(node, newNode) {
if (node.key > newNode.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);
}
}
}
BinarySearchTree.prototype.insert = function(key) {
var newNode = new Node(key);
if (this.root === null) {
this.root = newNode;
} else {
insertNode(this.root, newNode);
}
};
BinarySearchTree.prototype.inOrderTraverse = function(callback) {
//中序遍歷的私有方法,從小到大遍歷
function inOrderTraverseNode(node, callback) {
if (node !== null) {
inOrderTraverseNode(node.left, callback);
callback(node.key);
inOrderTraverseNode(node.right, callback);
}
}
inOrderTraverseNode(this.root, printNode);
};
BinarySearchTree.prototype.preOrderTraverse = function(callback){
function preOrderTraverseNode(node,callback){
if (node !== null) {
callback(node.key);
preOrderTraverseNode(node.left,callback);
preOrderTraverseNode(node.right,callback);
}
}
preOrderTraverseNode(this.root,callback);
};
BinarySearchTree.prototype.postOrderTraverse = function(callback){
function postOrderTraverseNode(node,callback){
if (node !== null) {
postOrderTraverseNode(node.left,callback);
postOrderTraverseNode(node.right,callback);
callback(node.key);
}
}
postOrderTraverseNode(this.root,callback);
};
BinarySearchTree.prototype.min = function(){
function minNode(node){
if (node) {
while(node && node.left !== null){
node = node.left;
}
return node.key;
}
return null;
}
//調用內部方法
return minNode(this.root);
};
BinarySearchTree.prototype.max = function(){
function maxNode(node){
if (node) {
while(node && node.right !== null){
node = node.right;
}
return node.key;
}
return null;
}
//調用內部方法
return maxNode(this.root);
};
BinarySearchTree.prototype.search = function(key){
function searchNode(node,key){
if (node === null) {
return false;
}
if (node.key < key) {
return searchNode(node.right,key);
}else if(node.key > key){
return searchNode(node.left,key);
}else{
return true;
}
}
return searchNode(this.root,key);
};
BinarySearchTree.prototype.remove = function(key){
function findMinNode(node){
if (node) {
while(node && node.left !== null){
node = node.left;
}
return node;
}
return null;
}
function removeNode(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
//第一種情況，一個葉節點
if (node.left === null && node.right === null) {
node = null;
return node;
}
//第二種情況 一個只有一個子節點的節點
if (node.left === null) {
node = node.right;
return node;
}else if (node.right === null){
node = node.left;
return node;
}
//第三種情況 一個有兩個子節點的節點
var aux = findMinNode(node.right);
node.key = aux.key;
node.right = removeNode(node.right,aux.key);
return node;
}
}
this.root = removeNode(this.root,key);
};
}
}
二叉樹基本使用：
//遍歷節點操作
function printNode(value) {
console.log(value);
}
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);//3 5 6 7 8 9 10 11 12 13 14 15 18 20 25
//先序遍歷
tree.preOrderTraverse(printNode);//11 7 5 3 6 9 8 10 15 13 12 14 20 18 25
//后序遍歷
tree.postOrderTraverse(printNode);//3 6 5 8 10 9 7 12 14 13 18 25 20 15 11
console.log(tree.min());
console.log(tree.max());
//搜索
console.log(tree.search(1) ? "Key 1 found." : "Key 1 not found.");//Key 1 not found.
console.log(tree.search(8) ? "Key 8 found." : "Key 8 not found.");//Key 8 found.
//移除節點
tree.remove(15);
tree.inOrderTraverse(printNode);////3 5 6 7 8 9 10 11 12 13 14 15 18 20 25
//console.log(tree.remove(100));
2 圖
2.1 圖的相關概念
由一條邊連接在一起的頂點稱為相鄰頂點。一個頂點的度是其相鄰頂點的數量。如果圖中不存在環,則稱該圖是無環的。
如果圖中每兩個頂點間都存在路徑,則該圖是連通的。
圖可以是無向的(邊沒有方向)或是有向的(有向圖)。
圖還可以是未加權的或是加權的。
圖最常見的實現是鄰接矩陣。每個節點都和一個整數相關聯,該整數將作為數組的索引。我 們用一個二維數組來表示頂點之間的連接。如果索引為i的節點和索引為j的節點相鄰,則arrayi === 1,否則arrayi === 0,鄰接矩陣如下圖所示:
我們也可以使用一種叫作鄰接表的動態數據結構來表示圖。鄰接表由圖中每個頂點的相鄰頂點列表所組成。存在好幾種方式來表示這種數據結構。我們可以用列表(數組)、鏈表,甚至是 散列表或是字典來表示相鄰頂點列表。下面的示意圖展示了鄰接表數據結構。
我們還可以用關聯矩陣來表示圖。在關聯矩陣中,矩陣的行表示頂點,列表示邊。如下圖所示,我們使用二維數組來表示兩者之間的連通性,如果頂點v是邊e的入射點,則arrayv === 1; 否則,arrayv===0。關聯矩陣通常用于邊的數量比頂點多的情況下,以節省空間和內存。
盡管鄰接表可能對大多數問題來說都是更好的選擇,但以上兩種表示法都很有用,且它們有 著不同的性質(例如,要找出頂點v和w是否相鄰,使用鄰接矩陣會比較快)。在后面示例中, 我們將會使用鄰接表表示法。
2.2 圖的遍歷和樹數據結構類似,我們可以訪問圖的所有節點。有兩種算法可以對圖進行遍歷:廣度優先 搜索(Breadth-First Search,BFS)和深度優先搜索(Depth-First Search,DFS)。圖遍歷可以用來尋找特定的頂點或尋找兩個頂點之間的路徑,檢查圖是否連通,檢查圖是否含有環等。
圖遍歷算法的思想是必須追蹤每個第一次訪問的節點,并且追蹤有哪些節點還沒有被完全探索。對于兩種圖遍歷算法,都需要明確指出第一個被訪問的頂點。
完全探索一個頂點要求我們查看該頂點的每一條邊。對于每一條邊所連接的沒有被訪問過的頂點,將其標注為被發現的,并將其加進待訪問頂點列表中。
為了保證算法的效率,務必訪問每個頂點至多兩次。連通圖中每條邊和頂點都會被訪問到。廣度優先搜索算法和深度優先搜索算法基本上是相同的,只有一點不同,那就是待訪問頂點 列表的數據結構。
2.3 廣度優先搜索廣度優先搜索算法會從指定的第一個頂點開始遍歷圖,先訪問其所有的相鄰點,就像一次訪問圖的一層。換句話說,就是先寬后深地訪問頂點。
廣度優先搜索和深度優先搜索都需要標注被訪問過的頂點。為此,我們將使用一個輔助數組color。由于當算法開始執行時,所有的頂點顏色都是白色(行{1}),所以我們可以創建一個輔 助函數initializeColor,為這兩個算法執行此初始化操作。
我們會用到一個隊列結構。隊列的實現.html)。
2.3.1廣度優先搜索的基本實現//廣度優先搜索算法 v表示初始節點，callback表示回調。
Graph.prototype.bfs = function(v, callback){
var color = initializeColor(this.vertices);
var queue = new Queue();//存儲待訪問和待探索的節點
queue.enqueue(v);
while(!queue.isEmpty()){
var u = queue.dequeue();
//獲取u的相鄰節點列表
var neighbors = this.adjList.get(u);
color[u] = "grey";
for(var i = 0; i < neighbors.length; i++){
var w = neighbors[i];
//如果從沒有標記過，則標記為grey，加入隊列
if (color[w] === "white") {
color[w] = "grey";
queue.enqueue(w);
}
}
//所有相鄰節點都被標記了，所以改為黑色
color[u] = "black";
//如果對于標記過得節點有操作，通過callback操作
if (callback) {
callback(u);
}
}
};
2.3.2 廣度優先實現最短路徑查找
給定一個圖G和源頂點v,找出對每個頂點u,u和v之間最短路徑的距離。
//用BFS實現最短路徑
Graph.prototype.BFS = function(v, callback) {
var color = initializeColor(this.vertices);
var queue = new Queue(); //存儲待訪問和待探索的節點
var d = [];
var pred = [];
queue.enqueue(v);
for (var i = 0; i < this.vertices.length; i++) {
d[this.vertices[i]] = 0;
pred[this.vertices[i]] = null;
}
while (!queue.isEmpty()) {
var u = queue.dequeue();
//獲取u的相鄰節點列表
var neighbors = this.adjList.get(u);
color[u] = "grey";
for (var i = 0; i < neighbors.length; i++) {
var w = neighbors[i];
//如果從沒有標記過，則標記為grey，加入隊列
if (color[w] === "white") {
color[w] = "grey";
d[w] = d[u] + 1;
pred[w] = u;
queue.enqueue(w);
}
}
//所有相鄰節點都被標記了，所以改為黑色
color[u] = "black";
//如果對于標記過得節點有操作，通過callback操作
if (callback) {
callback(u);
}
}
return {
distances: d,
predecessors: pred
}
};
2.3.3 深度優先搜索基本實現
//深度優先基本實現
Graph.prototype.dfs = function(callback) {
var self = this;
function dfsVisit(u, color, callback) {
color[u] = "grey";
if (callback) {
callback(u);
}
var neighbors = self.adjList.get(u);
for (var i = 0; i < neighbors.length; i++) {
var w = neighbors[i];
if (color[w] === "white") {
dfsVisit(w, color, callback);
}
}
color[u] = "black";
}
var color = initializeColor(this.vertices);
for (var i = 0; i < this.vertices.length; i++) {
if (color[this.vertices[i]] === "white") {
dfsVisit(this.vertices[i], color, callback);
}
}
};
2.3.4 深度優先搜索實現拓撲排序
當我們需要編排一些任務或步驟的執行順序時,這稱為拓撲排序。
//DFS可以實現輸出被訪問頂點的順序，可以用于拓撲排序實現。
Graph.prototype.DFS = function(){
var time = 0;
var self = this;
function DFSVisit(u,color,d,f,p){
//console.log("discovered " + u);
color[u] = "grey";
d[u] = ++time;
var neighbors = self.adjList.get(u);
for(var i = 0; i < neighbors.length; i++){
var w = neighbors[i];
if (color[w] === "white") {
p[w] = u;
DFSVisit(w,color,d,f,p);
}
}
color[u] = "black";
f[u] = ++time;
//console.log("explored " + u);
}
var color = initializeColor(this.vertices);
var d = [];
var f = [];
var p = [];
var time = 0;
for(var i = 0; i < this.vertices.length; i++){
f[this.vertices[i]] = 0;
d[this.vertices[i]] = 0;
p[this.vertices[i]] = null;
}
for(var i = 0; i< this.vertices.length; i++){
if (color[this.vertices[i]] === "white") {
DFSVisit(this.vertices[i], color, d, f, p);
}
}
return {
discovery:d,
finished:f,
predecessors:p
}
};
2.4 圖的實現
我們會實現一個鄰接表的圖結構。我們使用一個數組來存儲圖中所有頂點的名字,以及一個字典 字典實現.html)來存儲鄰接表字典將會使用頂點的名字作為鍵,鄰接頂點列表作為值。vertices數組和adjList字典兩者都是我們Graph類的私有屬性。
function Graph() {
this.vertices = []; //點數組
this.adjList = new Dictionary();
if ((typeof this.addVertex !== "function") && (typeof this.addVertex !== "string")) {
//私有方法，標記節點顏色 未被訪問過是white 被發現是grey 已被探索black。
function initializeColor(vertices) {
var color = [];
for (var i = 0; i < vertices.length; i++) {
color[vertices[i]] = "white";
}
return color;
}
//添加節點
Graph.prototype.addVertex = function(v) {
this.vertices.push(v);
this.adjList.set(v, []); //給節點v設置一個空數組作為值。
};
//添加邊
Graph.prototype.addEdge = function(v, w) {
this.adjList.get(v).push(w); //先獲取v節點對應的數組，然后把w推入數組中，這樣就表示一條v到w的線
this.adjList.get(w).push(v);
};
//廣度優先d
//搜索算法 v表示初始節點，callback表示回調。
Graph.prototype.bfs = function(v, callback) {
var color = initializeColor(this.vertices);
var queue = new Queue(); //存儲待訪問和待探索的節點
queue.enqueue(v);
while (!queue.isEmpty()) {
var u = queue.dequeue();
//獲取u的相鄰節點列表
var neighbors = this.adjList.get(u);
color[u] = "grey";
for (var i = 0; i < neighbors.length; i++) {
var w = neighbors[i];
//如果從沒有標記過，則標記為grey，加入隊列
if (color[w] === "white") {
color[w] = "grey";
queue.enqueue(w);
}
}
//所有相鄰節點都被標記了，所以改為黑色
color[u] = "black";
//如果對于標記過得節點有操作，通過callback操作
if (callback) {
callback(u);
}
}
};
//用BFS實現最短路徑
Graph.prototype.BFS = function(v, callback) {
var color = initializeColor(this.vertices);
var queue = new Queue(); //存儲待訪問和待探索的節點
var d = [];
var pred = [];
queue.enqueue(v);
for (var i = 0; i < this.vertices.length; i++) {
d[this.vertices[i]] = 0;
pred[this.vertices[i]] = null;
}
while (!queue.isEmpty()) {
var u = queue.dequeue();
//獲取u的相鄰節點列表
var neighbors = this.adjList.get(u);
color[u] = "grey";
for (var i = 0; i < neighbors.length; i++) {
var w = neighbors[i];
//如果從沒有標記過，則標記為grey，加入隊列
if (color[w] === "white") {
color[w] = "grey";
d[w] = d[u] + 1;
pred[w] = u;
queue.enqueue(w);
}
}
//所有相鄰節點都被標記了，所以改為黑色
color[u] = "black";
//如果對于標記過得節點有操作，通過callback操作
if (callback) {
callback(u);
}
}
return {
distances: d,
predecessors: pred
}
};
//深度優先基本實現
Graph.prototype.dfs = function(callback) {
var self = this;
function dfsVisit(u, color, callback) {
color[u] = "grey";
if (callback) {
callback(u);
}
var neighbors = self.adjList.get(u);
for (var i = 0; i < neighbors.length; i++) {
var w = neighbors[i];
if (color[w] === "white") {
dfsVisit(w, color, callback);
}
}
color[u] = "black";
}
var color = initializeColor(this.vertices);
for (var i = 0; i < this.vertices.length; i++) {
if (color[this.vertices[i]] === "white") {
dfsVisit(this.vertices[i], color, callback);
}
}
};
//DFS可以實現輸出被訪問頂點的順序
Graph.prototype.DFS = function(){
var time = 0;
var self = this;
function DFSVisit(u,color,d,f,p){
//console.log("discovered " + u);
color[u] = "grey";
d[u] = ++time;
var neighbors = self.adjList.get(u);
for(var i = 0; i < neighbors.length; i++){
var w = neighbors[i];
if (color[w] === "white") {
p[w] = u;
DFSVisit(w,color,d,f,p);
}
}
color[u] = "black";
f[u] = ++time;
//console.log("explored " + u);
}
var color = initializeColor(this.vertices);
var d = [];
var f = [];
var p = [];
var time = 0;
for(var i = 0; i < this.vertices.length; i++){
f[this.vertices[i]] = 0;
d[this.vertices[i]] = 0;
p[this.vertices[i]] = null;
}
for(var i = 0; i< this.vertices.length; i++){
if (color[this.vertices[i]] === "white") {
DFSVisit(this.vertices[i], color, d, f, p);
}
}
return {
discovery:d,
finished:f,
predecessors:p
}
};
Graph.prototype.toString = function() {
var s = "";
for (var i = 0; i < this.vertices.length; i++) {
s += this.vertices[i] + " -> ";
var neighbors = this.adjList.get(this.vertices[i]);
for (var j = 0; j < neighbors.length; j++) {
s += neighbors[j] + " ";
}
s += ",";
}
return s;
};
}
}
2.5 圖的基本使用
var graph = new Graph();
var myVertices = ["A", "B", "C", "D", "E", "F", "G", "H", "I"];
//添加點
for (var i = 0; i < myVertices.length; i++) {
graph.addVertex(myVertices[i]);
}
//添加點之間的關系
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("A", "D");
graph.addEdge("C", "D");
graph.addEdge("C", "G");
graph.addEdge("D", "G");
graph.addEdge("D", "H");
graph.addEdge("B", "E");
graph.addEdge("B", "F");
graph.addEdge("E", "I");
//console.log(graph.toString());//A -> B C D ,B -> A E F ,C -> A D G ,D -> A C G H ,E -> B I ,F -> B ,G -> C D ,H -> D ,I -> E
function printNode(value) {
console.log("Visited vertex: " + value);
}
//廣度搜索算法
//graph.bfs(myVertices[0],printNode);
//上行輸出結果，節點的訪問順序
// Visited vertex: A
// Visited vertex: B
// Visited vertex: C
// Visited vertex: D
// Visited vertex: E
// Visited vertex: F
// Visited vertex: G
// Visited vertex: H
// Visited vertex: I
//廣度優先搜索的使用:最短路徑算法
var shortestPathA = graph.BFS(myVertices[0]);
//console.log(shortestPathA);
//上行輸出結果：
// { distances: [ A: 0, B: 1, C: 1, D: 1, E: 2, F: 2, G: 2, H: 2, I: 3 ],
// predecessors:
// [ A: null,
// B: "A",
// C: "A",
// D: "A",
// E: "B",
// F: "B",
// G: "C",
// H: "D",
// I: "E" ]
//深入優先搜索算法
//graph.dfs(printNode);
//上一行運行結果，節點的訪問順序
// Visited vertex: A
// Visited vertex: B
// Visited vertex: E
// Visited vertex: I
// Visited vertex: F
// Visited vertex: C
// Visited vertex: D
// Visited vertex: G
// Visited vertex: H
//深度優先搜索查找訪問過程：
graph = new Graph();
myVertices = ["A","B","C","D","E","F"];
for (i=0; i
源碼地址
Javascript的數據結構與算法(三)源碼
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/86658.html
摘要：至于這三個的具體概念，可以看圖中集合的實現首先，創建一個構造函數。前端路漫漫，且行且歌的前端樂園原文鏈接寒假前端學習學習數據結構與算法三集合 本系列的第一篇文章: 學習JavaScript數據結構與算法（一），棧與隊列第二篇文章：學習JavaScript數據結構與算法（二）：鏈表第三篇文章：學習JavaScript數據結構與算法（三）：集合第四篇文章：學習JavaScript數據結構與...
摘要：保護數據結構內部元素下劃線命名約定這只是一種約定，只能依賴于開發人員具備的常識用的限定作用于實現類實現了假的私有屬性，雖然基本類型不可變，但由于新增的方法仍然能取到所有屬性，而且是數組的形式，但我們操作的是棧，不應該出現這種行為。 棧是一種遵循后進先出（ILFO）原則的有序集合，新添加或待刪除的元素都保存在棧的同一段，稱為棧頂，另一端就叫棧底。現實中很多例子采用了這種數據結構，比如一摞...
摘要：筆者作為一位，將工作以來用到的各種優秀資料神器及框架整理在此，畢竟好記性不如爛鍵盤，此前端知識點大百科全書前端掘金，，不定期更新技巧前端掘金技巧，偶爾更新。計算數組的極值技巧使你的更加專業前端掘金一個幫你提升技巧的收藏集。 CSS 樣式畫各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經常用到的圖案，還有一些是在css-tricks看到的。記錄一下，以后會用到。會持續更新… 一、...
摘要：筆者作為一位，將工作以來用到的各種優秀資料神器及框架整理在此，畢竟好記性不如爛鍵盤，此前端知識點大百科全書前端掘金，，不定期更新技巧前端掘金技巧，偶爾更新。計算數組的極值技巧使你的更加專業前端掘金一個幫你提升技巧的收藏集。 CSS 樣式畫各種圖形 - 前端 - 掘金下面是一些我在 CSS 中經常用到的圖案，還有一些是在css-tricks看到的。記錄一下，以后會用到。會持續更新… 一、...
閱讀 2045·2021-11-08 13:22
閱讀 2506·2021-09-04 16:40
閱讀 1150·2021-09-03 10:29
閱讀 1715·2019-08-30 15:44
閱讀 2124·2019-08-30 11:13
閱讀 2791·2019-08-29 17:07
閱讀 1967·2019-08-29 14:22
閱讀 1247·2019-08-26 14:00
