JS实现数据结构:树和森林

 1 // 1.双亲表示法 
 2 // 优点：parent(tree, x)操作可以在常量时间内实现 
 3 // 缺点：求结点的孩子时需要遍历整个结构 
 4 function ParentTree() { 
 5     this.nodes = []; 
 6 } 
 7 ParentTree.prototype = { 
 8     constructor: ParentTree, 
 9     getDepth: function () { 
10         var maxDepth = 0; 
11  
12         for (var i = 0; i < this.nodes.length; i++) { 
13             var dep = 0; 
14             for (var j = i; j >= 0; j = this.nodes[i].parent) dep++; 
15             if (dep > maxDepth) maxDepth = dep; 
16         } 
17  
18         return maxDepth; 
19     } 
20 }; 
21 function ParentTreeNode(data, parent) { 
22     // type: ParentTree 
23     this.data = data || null; 
24     // 双亲位置域 {Number} 
25     this.parent = parent || 0; 
26 } 
27 var pt = new ParentTree(); 
28 pt.nodes.push(new ParentTreeNode('R', -1)); 
29 pt.nodes.push(new ParentTreeNode('A', 0)); 
30 pt.nodes.push(new ParentTreeNode('B', 0)); 
31 pt.nodes.push(new ParentTreeNode('C', 0)); 
32 pt.nodes.push(new ParentTreeNode('D', 1)); 
33 pt.nodes.push(new ParentTreeNode('E', 1)); 
34 pt.nodes.push(new ParentTreeNode('F', 3)); 
35 pt.nodes.push(new ParentTreeNode('G', 6)); 
36 pt.nodes.push(new ParentTreeNode('H', 6)); 
37 pt.nodes.push(new ParentTreeNode('I', 6));

 1 // 孩子表示法 
 2  
 3 function ChildTree() { 
 4     this.nodes = []; 
 5 } 
 6 ChildTree.prototype = { 
 7     constructor: ChildTree, 
 8     getDepth: function () { 
 9         var self = this; 
10         return function subDepth(rootIndex) { 
11             if (!self.nodes[rootIndex]) return 1; 
12  
13             for (var sd = 1, p = self.nodes[rootIndex]; p; p = p.next) { 
14                 var d = subDepth(p.child); 
15                 if (d > sd) sd = d; 
16             } 
17  
18             return sd + 1; 
19         }(this.data[0]); 
20     } 
21 }; 
22 /** 
23  * 
24  * @param {*} data 
25  * @param {ChildTreeNode} firstChild 孩子链表头指针 
26  * @constructor 
27  */ 
28 function ChildTreeBox(data, firstChild) { 
29     this.data = data; 
30     this.firstChild = firstChild; 
31 } 
32 /** 
33  * 孩子结点 
34  * 
35  * @param {Number} child 
36  * @param {ChildTreeNode} next 
37  * @constructor 
38  */ 
39 function ChildTreeNode(child, next) { 
40     this.child = child; 
41     this.next = next; 
42 }

 1 // 孩子兄弟表示法(二叉树表示法) 
 2 // 可增设一个parent域实现parent操作 
 3 function ChildSiblingTree(data) { 
 4     this.data = data || null; 
 5     this.firstChild = null; 
 6     this.nextSibling = null; 
 7 } 
 8 ChildSiblingTree.prototype = { 
 9     // 输出孩子兄弟链表表示的树的各边 
10     print: function print() { 
11         for (var child = this.firstChild; child; child = child.nextSibling) { 
12             console.log('%c %c', this.data, child.data); 
13             print.call(child); 
14         } 
15     }, 
16     // 求孩子兄弟链表表示的树的叶子数目 
17     leafCount: function leafCount() { 
18         if (!this.firstChild) return 1; 
19         else { 
20             var count = 0; 
21             for (var child = this.firstChild; child; child = child.nextSibling) { 
22                 count += leafCount.call(child); 
23             } 
24             return count; 
25         } 
26     }, 
27     // 求树的度 
28     getDegree: function getDegree() { 
29         if (!this.firstChild) return 0; 
30         else { 
31             var degree = 0; 
32             for (var p = this.firstChild; p; p = p.nextSibling) degree++; 
33  
34             for (p = this.firstChild; p; p = p.nextSibling) { 
35                 var d = getDegree.call(p); 
36                 if (d > degree) degree = d; 
37             } 
38  
39             return degree; 
40         } 
41     }, 
42     getDepth: function getDepth() { 
43         if (this === global) return 0; 
44         else { 
45             for (var maxd = 0, p = this.firstChild; p; p = p.nextSibling) { 
46                 var d = getDepth.call(p); 
47                 if (d > maxd) maxd = d; 
48             } 
49  
50             return maxd + 1; 
51         } 
52     } 
53 };