JavaScript數據結構：樹

Chinese (Traditional) (中文（繁體）) translation by Stypstive (you can also view the original English article)

Final product image — What You'll Be Creating

樹是在 web 開發中最常用的數據結構之一。這種說法對開發者和用戶都是正確的。每個編寫HTML並將其加載到Web瀏覽器的Web開發人員都創建了一個樹，稱為文檔對象模型（DOM）。相應地，每個網絡上的消費信息的人，接受信息也以DOM樹的形式。

現在，高潮來了:你正在讀的本文在瀏覽器中就是以樹的形式進行渲染的。元素又嵌套在元素中；元素又嵌套在元素中。文字由<p>元素進行表示；<p>元素又嵌套在<body>元素中；<body>元素又嵌套在<html>元素中。

這些嵌套數據和家族數類似。 <html> 是父元素，<body>是子元素，<p>又是<body>的子元素。如果这个比喻对你有点用的话，你将会发现在我们介绍树的时候会用到更多的类比。

在本文中，我們將會通過兩個不同的樹遍歷方式來創建一個樹：深度優先(DFS)和廣度優先(BFS)。如果你對遍歷這個詞感到比較陌生，不妨將他想象成訪問樹中的每一個節點。）這兩種類型的遍歷強調了與樹交互的不同方式，而且，結合這個系列的數據結構。 DFS和BFS分別用棧和隊列來訪問節點。聽起來很酷！！！

樹（深度搜索和廣度搜索）

在計算機科學中，樹是一種用節點來模擬分層數據的數據結構。每個樹節點都包含他本身的數據及指向其他節點的指針。

節點和指針這些術語可能對一些讀者來說比較陌生，所以讓我們用類比來進一步描述他們。讓我們將樹與組織圖結構圖進行比較。這個結構圖有一個頂級位置（根節點），比如CEO。在這個節點下面還有一些其他的節點，比如副總裁(VP)。在這個節點下面還有一些其他的節點，比如副總裁(VP)。

為了表示這種關系，我們用箭頭從CEO指向VP。一個位置，比如CEO，是一個節點；我們創建的CEO到VP的關系是一個指針。在我們的組織結構圖中去創建更多的關系，我們只要重復這些步驟即可---我們讓一個節點指向另一個節點。

在概念層次上，我希望節點和指針有意義。在實際中，我們能從更科學的實例中獲取收益。讓我們來思考DOM。 DOM有<html>元素作為其頂級位置（根節點）。這個節點指向<head>元素和<body>元素。這些步驟在DOM的所有節點中重復。

這種設計的一個優點是能夠嵌套節點：例如：一個<ul>元素能夠包含很多個<li>元素；此外，每個<li>元素能擁有兄弟<li>元素。著很怪異，但是確實真實有趣！著很怪異，但是確實真實有趣！

操作樹

由於每個樹都包含節點，其可以是來自樹的單獨構造器，我們將概述兩個構造函數的操作：Node和Tree

節點

data存儲值。
parent指向節點的父節點。
children指向列表中的下一個節點。

樹

_root指向一個樹的根節點。
traverseDF(callback)對樹進行DFS遍歷。
traverseBF(callback)對樹進行BFS遍歷。
contains(data, traversal)搜索樹中的節點。
add(data, toData, traverse)向樹中添加節點。
remove(child, parent)移除樹中的節點。

實現樹

現在讓我們寫下樹的代碼！

節點的屬性

在我們的實現中，我們首先定義一個叫做Node的函數，然後構造一個Tree。

function Node(data) {
    this.data = data;
    this.parent = null;
    this.children = [];
}

每一個Node實例都包含三個屬性：data，parant，和children。第一個屬性保存與節點相關聯的數據。第二個屬性指向一個節點。第三個屬性指向許多子節點。

樹的屬性

現在讓我們來定義Tree的構造函數，其中包括Node構造函數的定義：

1	function Tree(data) {
2	var node = new Node(data);
3	this._root = node;
4	}

Tree包含兩行代碼。第一行創建了一個Node的新實例；第二行讓node等於樹的根節點。

Tree和Node的定義只需要幾行代碼。但是，通過這幾行足以幫助我們模擬分層數據。為了證明這一點，讓我們用一些示例數據去創建Tree的示例（和間接的Node）。

1	var tree = new Tree('CEO');
2
3	// {data: 'CEO', parent: null, children: []}
4	tree._root;

幸虧有parent和children的存在，我們可以為_root添加子節點和讓這些子節點的父節點等於_root。換一種說法，我們可以模擬分層數據的創建。

Tree的方法

接下來我們將要創建以下五種方法。

樹

traverseDF(callback)
traverseBF(callback)
contains(data, traversal)
add(child, parent)
remove(node, parent)

因為每種方法都需要我們去遍歷一個樹，所以我們首先要實現一個方法去定義不同的樹遍歷。（遍歷樹是一種正式的方式來訪問樹的每個節點。）

1 of 5: traverseDF(callback)

這種方法以DFS這種方式遍歷樹。

Tree.prototype.traverseDF = function(callback) {

    // this is a recurse and immediately-invoking function 
    (function recurse(currentNode) {
        // step 2
        for (var i = 0, length = currentNode.children.length; i < length; i++) {
            // step 3
            recurse(currentNode.children[i]);
        }

        // step 4
        callback(currentNode);
        
        // step 1
    })(this._root);

};

traverseDF(callback)有一個參數callback。如果對這個名字不明白，callback被假定是一個函數，將在後面被traverseDF(callback)調用。

traverseDF(callback)的函數體含有另一個叫做recurse的函數。這個函數是一個遞歸函數！換句話說，它是自我調用和自我終止。使用recurse的註釋中提到的步驟，我將描述遞歸用來recurse整個樹的一般過程。

這裏是步驟：

立即使用樹的根節點作為其參數調用recurse。此時，currentNode指向當前節點。
進入for循環並且從第一個子節點開始，每一個子節點都叠代一次currentNode函數。
在for循環體內，使用currentNode的子元素調用遞歸。確切的子節點取決於當前for循環的當前叠代。
當currentNode不存在子節點時，我們退出for循環並callback我們在調用traverseDF（callback）期間傳遞的回調。

步驟2（自終止），3（自調用）和4（回調）重復，直到我們遍歷樹的每個節點。

遞歸是一個非常困難的話題，需要一個完整的文章來充分解釋它。由於遞歸的解釋不是本文的重點 - 重點是實現一棵樹 - 我建議任何讀者沒有很好地掌握遞歸做以下兩件事。

首先，實驗我們當前的traverseDF(callback)實現，並嘗試一定程度上理解它是如何工作的。第二，如果你想要我寫一篇關於遞歸的文章，那麽請在本文的評論中請求它。

以下示例演示如何使用traverseDF(callback)遍歷樹。要遍歷樹，我將在下面的示例中創建一個。我現在使用的方法不是理想的，但它能很好的工作。一個更好的方法是使用add（value），我們將在第4步和第5步中實現。

var tree = new Tree('one');

tree._root.children.push(new Node('two'));
tree._root.children[0].parent = tree;

tree._root.children.push(new Node('three'));
tree._root.children[1].parent = tree;

tree._root.children.push(new Node('four'));
tree._root.children[2].parent = tree;

tree._root.children[0].children.push(new Node('five'));
tree._root.children[0].children[0].parent = tree._root.children[0];

tree._root.children[0].children.push(new Node('six'));
tree._root.children[0].children[1].parent = tree._root.children[0];

tree._root.children[2].children.push(new Node('seven'));
tree._root.children[2].children[0].parent = tree._root.children[2];

/*

creates this tree

 one
 ├── two
 │   ├── five
 │   └── six
 ├── three
 └── four
     └── seven

*/

現在，讓我們調用traverseDF(callback)

tree.traverseDF(function(node) {
    console.log(node.data)
});

/*

logs the following strings to the console

'five'
'six'
'two'
'three'
'seven'
'four'
'one'

*/

2 of 5: traverseBF(callback)

這個方法使用深度優先搜索去遍歷樹

深度優先搜索和廣度優先搜索之間的差別涉及樹的節點訪問的序列。為了說明這一點，讓我們使用我們從traverseDF（callback）創建的樹。

/*

 tree

 one (depth: 0)
 ├── two (depth: 1)
 │   ├── five (depth: 2)
 │   └── six (depth: 2)
 ├── three (depth: 1)
 └── four (depth: 1)
     └── seven (depth: 2)

 */

現在，讓我們傳遞traverseBF（callback）和我們用於traverseDF（callback）的回調。

tree.traverseBF(function(node) {
    console.log(node.data)
});

/*

logs the following strings to the console

'one'
'two'
'three'
'four'
'five'
'six'
'seven'

*/

來自控制臺的日誌和我們的樹的圖顯示了關於廣度優先搜索的模式。從根節點開始;然後行進一個深度並訪問該深度從左到右的每個節點。重復此過程，直到沒有更多的深度要移動。

由於我們有一個廣度優先搜索的概念模型，現在讓我們實現使我們的示例工作的代碼。

Tree.prototype.traverseBF = function(callback) {
    var queue = new Queue();
    
    queue.enqueue(this._root);

    currentTree = queue.dequeue();

    while(currentTree){
        for (var i = 0, length = currentTree.children.length; i < length; i++) {
            queue.enqueue(currentTree.children[i]);
        }

        callback(currentTree);
        currentTree = queue.dequeue();
    }
};

我們對traverseBF(callback)的定義包含了很多邏輯。因此，我將以可管理的步驟解釋邏輯：

創建 Queue的實例。
將調用traverseBF(callback)的節點添加到Queue的實例。
定義一個變量currentNode並且將他的值初始化為剛才添加到隊列裏的node。
當currentNode指向一個節點時，執行wille循環裏面的代碼。
用for循環去叠代currentNode的子節點。
在for循環體內，將每個子元素加入隊列。
獲取currentNode並將其作為callback的參數傳遞。
將currentNode重新分配給正從隊列中刪除的節點。
直到currentNode不在指向任何節點-也就是說樹中的每個節點都訪問過了-重復4-8步。

3 of 5: contains(callback, traversal)

讓我們定義一個方法，讓我們在樹中搜索一個特定的值。去使用我們創建的任一種樹遍歷方法，我們已經定義了contains(callback, traversal)接收兩個參數：搜索的數據和遍歷的類型。

1	Tree.prototype.contains = function(callback, traversal) {
2	traversal.call(this, callback);
3	};

在contains(callback, traversal)函數體內，我們用call方法去傳遞this和callback。第一個參數將traversal綁定到被調用的樹contains（callback，traversal）;第二个参数是树种每个节点被调用的函数。

想象一下，我們要將包含奇數數據的任何節點記錄到控制臺，並使用BFS遍歷樹中的每個節點。代碼我們可以這麽寫：

// tree is an example of a root node
tree.contains(function(node){
    if (node.data === 'two') {
        console.log(node);
    }
}, tree.traverseBF);

4 of 5: add(data, toData, traversal)

現在我們有了一個可以搜索樹中特定節點的方法。現在讓我們定義一個允許我們向指定節點添加節點的方法。

Tree.prototype.add = function(data, toData, traversal) {
    var child = new Node(data),
        parent = null,
        callback = function(node) {
            if (node.data === toData) {
                parent = node;
            }
        };

    this.contains(callback, traversal);

    if (parent) {
        parent.children.push(child);
        child.parent = parent;
    } else {
        throw new Error('Cannot add node to a non-existent parent.');
    }
};

add(data, toData, traversal)定義了三個參數。第一個參數，data，用來創建一個Node的新實例。第二個參數，toData，用來比較樹中的每個節點。第三個參數，traversal，是這個方法中用來遍歷樹的類型。

在add(data, toData, traversal)函數體內，我們聲明了三個變量。第一個變量，child，代表初始化的Node實例。第二個變量，parent，初始化為null；但是將來會指向匹配toData值的樹中的任意節點。 parent的重新分配發生在我們聲明的第三個變量，這就是callback。

callback是一個將toData和每一個節點的data屬性做比較的函數。如果if語句的值是true，那麽parent將被賦值給if語句中匹配比較的節點。

每個節點的toData比較發生在contains(callback, traversal)。遍歷類型和callback必須作為contains(callback, traversal)的參數進行傳遞。

最後，如果parent不存在於樹中，我們將child推入parent.children；同時也要將parent賦值給child的父級。否則，將拋出錯誤。否則，將拋出錯誤。

讓我們用add(data, toData, traversal)做個例子：

var tree = new Tree('CEO');

tree.add('VP of Happiness', 'CEO', tree.traverseBF);

/*

our tree

'CEO'
└── 'VP of Happiness'

*/

這裏是add(addData, toData, traversal)的更加復雜的例子：

var tree = new Tree('CEO');

tree.add('VP of Happiness', 'CEO', tree.traverseBF);
tree.add('VP of Finance', 'CEO', tree.traverseBF);
tree.add('VP of Sadness', 'CEO', tree.traverseBF);

tree.add('Director of Puppies', 'VP of Finance', tree.traverseBF);
tree.add('Manager of Puppies', 'Director of Puppies', tree.traverseBF);

/*

 tree

 'CEO'
 ├── 'VP of Happiness'
 ├── 'VP of Finance'
 │   ├── 'Director of Puppies'
 │   └── 'Manager of Puppies'
 └── 'VP of Sadness'

 */

5 of 5: remove(data, fromData, traversal)

為了完成Tree的實現，我們將添加一個叫做remove(data, fromData, traversal)的方法。跟從DOM裏面移除節點類似，這個方法將移除一個節點和他的所有子級。

Tree.prototype.remove = function(data, fromData, traversal) {
    var tree = this,
        parent = null,
        childToRemove = null,
        index;

    var callback = function(node) {
        if (node.data === fromData) {
            parent = node;
        }
    };

    this.contains(callback, traversal);

    if (parent) {
        index = findIndex(parent.children, data);

        if (index === undefined) {
            throw new Error('Node to remove does not exist.');
        } else {
            childToRemove = parent.children.splice(index, 1);
        }
    } else {
        throw new Error('Parent does not exist.');
    }

    return childToRemove;
};

與add(data, toData, traversal)類似，移除將遍歷樹以查找包含第二個參數的節點，現在為fromData。如果這個節點被發現了，那麽parent將指向它。

在這時候，我們到達了第一個if語句。如果parent不存在，將拋出錯誤。如果parent不存在，我們使用parent.children調用findIndex（）和我們要從parent節點的子節點中刪除的數據（findIndex（）是一個幫助方法，我將在下面定義。）（findIndex（）是一個幫助方法，我將在下面定義。）

function findIndex(arr, data) {
    var index;

    for (var i = 0; i < arr.length; i++) {
        if (arr[i].data === data) {
            index = i;
        }
    }

    return index;
}

在findIndex()裏面，以下邏輯將發生。如果parent.children中的任意一個節點包含匹配data值的數據,那麽變量index賦值為一個整數。如果沒有子級的數值屬性匹配data，那麽index保留他的默認值undefined。在最後一行的findIndex()方法，我們返回一個index。

我們現在去remove(data, fromData, traversal) 。如果index的值是undefined，將會拋出錯誤。如果index的值存在，我們用它來拼接我們想從parent的子節點中刪除的節點。同樣我們給刪除的子級賦值為childToRemove。

最後，我們返回childToRemove。

至此我們完成了Tree的完整實現。

至此我們完成了Tree的完整實現。回過頭看看-我們完成了很多工作：

function Node(data) {
    this.data = data;
    this.parent = null;
    this.children = [];
}

function Tree(data) {
    var node = new Node(data);
    this._root = node;
}

Tree.prototype.traverseDF = function(callback) {

    // this is a recurse and immediately-invoking function
    (function recurse(currentNode) {
        // step 2
        for (var i = 0, length = currentNode.children.length; i < length; i++) {
            // step 3
            recurse(currentNode.children[i]);
        }

        // step 4
        callback(currentNode);

        // step 1
    })(this._root);

};

Tree.prototype.traverseBF = function(callback) {
    var queue = new Queue();

    queue.enqueue(this._root);

    currentTree = queue.dequeue();

    while(currentTree){
        for (var i = 0, length = currentTree.children.length; i < length; i++) {
            queue.enqueue(currentTree.children[i]);
        }

        callback(currentTree);
        currentTree = queue.dequeue();
    }
};

Tree.prototype.contains = function(callback, traversal) {
    traversal.call(this, callback);
};

Tree.prototype.add = function(data, toData, traversal) {
    var child = new Node(data),
        parent = null,
        callback = function(node) {
            if (node.data === toData) {
                parent = node;
            }
        };

    this.contains(callback, traversal);

    if (parent) {
        parent.children.push(child);
        child.parent = parent;
    } else {
        throw new Error('Cannot add node to a non-existent parent.');
    }
};

Tree.prototype.remove = function(data, fromData, traversal) {
    var tree = this,
        parent = null,
        childToRemove = null,
        index;

    var callback = function(node) {
        if (node.data === fromData) {
            parent = node;
        }
    };

    this.contains(callback, traversal);

    if (parent) {
        index = findIndex(parent.children, data);

        if (index === undefined) {
            throw new Error('Node to remove does not exist.');
        } else {
            childToRemove = parent.children.splice(index, 1);
        }
    } else {
        throw new Error('Parent does not exist.');
    }

    return childToRemove;
};

function findIndex(arr, data) {
    var index;

    for (var i = 0; i < arr.length; i++) {
        if (arr[i].data === data) {
            index = i;
        }
    }

    return index;
}

總結

樹的模擬分層數據。我們的周圍有許多類似於這種類型的層次結構，如網頁和我們的家庭。任何時候你發現自己需要結構化數據與層次結構，考慮使用樹。

1	var tree = new Tree('one');
2
3	tree._root.children.push(new Node('two'));
4	tree._root.children[0].parent = tree;
5
6	tree._root.children.push(new Node('three'));
7	tree._root.children[1].parent = tree;
8
9	tree._root.children.push(new Node('four'));
10	tree._root.children[2].parent = tree;
11
12	tree._root.children[0].children.push(new Node('five'));
13	tree._root.children[0].children[0].parent = tree._root.children[0];
14
15	tree._root.children[0].children.push(new Node('six'));
16	tree._root.children[0].children[1].parent = tree._root.children[0];
17
18	tree._root.children[2].children.push(new Node('seven'));
19	tree._root.children[2].children[0].parent = tree._root.children[2];
20
21	/*
22
23	creates this tree
24
25	one
26	├── two
27	│ ├── five
28	│ └── six
29	├── three
30	└── four
31	└── seven
32
33	*/

1	function Node(data) {
2	this.data = data;
3	this.parent = null;
4	this.children = [];
5	}
6
7	function Tree(data) {
8	var node = new Node(data);
9	this._root = node;
10	}
11
12	Tree.prototype.traverseDF = function(callback) {
13
14	// this is a recurse and immediately-invoking function
15	(function recurse(currentNode) {
16	// step 2
17	for (var i = 0, length = currentNode.children.length; i < length; i++) {
18	// step 3
19	recurse(currentNode.children[i]);
20	}
21
22	// step 4
23	callback(currentNode);
24
25	// step 1
26	})(this._root);
27
28	};
29
30	Tree.prototype.traverseBF = function(callback) {
31	var queue = new Queue();
32
33	queue.enqueue(this._root);
34
35	currentTree = queue.dequeue();
36
37	while(currentTree){
38	for (var i = 0, length = currentTree.children.length; i < length; i++) {
39	queue.enqueue(currentTree.children[i]);
40	}
41
42	callback(currentTree);
43	currentTree = queue.dequeue();
44	}
45	};
46
47	Tree.prototype.contains = function(callback, traversal) {
48	traversal.call(this, callback);
49	};
50
51	Tree.prototype.add = function(data, toData, traversal) {
52	var child = new Node(data),
53	parent = null,
54	callback = function(node) {
55	if (node.data === toData) {
56	parent = node;
57	}
58	};
59
60	this.contains(callback, traversal);
61
62	if (parent) {
63	parent.children.push(child);
64	child.parent = parent;
65	} else {
66	throw new Error('Cannot add node to a non-existent parent.');
67	}
68	};
69
70	Tree.prototype.remove = function(data, fromData, traversal) {
71	var tree = this,
72	parent = null,
73	childToRemove = null,
74	index;
75
76	var callback = function(node) {
77	if (node.data === fromData) {
78	parent = node;
79	}
80	};
81
82	this.contains(callback, traversal);
83
84	if (parent) {
85	index = findIndex(parent.children, data);
86
87	if (index === undefined) {
88	throw new Error('Node to remove does not exist.');
89	} else {
90	childToRemove = parent.children.splice(index, 1);
91	}
92	} else {
93	throw new Error('Parent does not exist.');
94	}
95
96	return childToRemove;
97	};
98
99	function findIndex(arr, data) {
100	var index;
101
102	for (var i = 0; i < arr.length; i++) {
103	if (arr[i].data === data) {
104	index = i;
105	}
106	}
107
108	return index;
109	}