简单的树
我们需要始终从简单的算法开始，然后一步步走向复杂的算法。简单的树二叉树
class simpletree { constructor(value) { this.value = value; this.children = []; } insertchild(value) { const newchild = new simpletree(value); const lastelement = this.findlastchild(this); lastelement.children.push(newchild); return newchild; } findlastchild(root) { if (root.children.length == 0) { return root; } return this.findlastchild(root.children[0]); } traversal(root) { console.log(root.value + ' --> '); root.children.foreach(child => { this.traversal(child); }) }}const simpletree = new simpletree('a');simpletree.insertchild('b');simpletree.insertchild('c');simpletree.insertchild('d');simpletree.insertchild('e');simpletree.insertchild('f');console.log(simpletree)simpletree.traversal(simpletree)/*{ "value": "a", "children": [ { "value": "b", "children": [ { "value": "c", "children": [ { "value": "d", "children": [ { "value": "e", "children": [ { "value": "f", "children": [] } ] } ] } ] } ] } ]}*/
二叉树
class BinaryTree { constructor(value) { this.value = value; this.left = null; this.right = null; } insertNode(value) { const newNode = new BinaryTree(value); const {node: lastNode, side} = this.findAppropriatePlace(this, value); lastNode[side] = newNode; return newNode; } removeFromNode(value) { this.findAppropriateNodAndrRemove(this, value); } findAppropriateNodAndrRemove(root, value) { const side = root.value < value ? 'right' : 'left'; if (root[side].value == value) { root[side] = null; return ; } return this.findAppropriateNodAndrRemove(root[side], value); } // root left right preOrderTraversal(root) { if (root === null) { return ; } console.log(root.value); this.preOrderTraversal(root.left); this.preOrderTraversal(root.right); } inOrderTraversal(root) { // left root right if (root === null) { return ; } this.inOrderTraversal(root.left); console.log(root.value); this.inOrderTraversal(root.right); } // left right root postOrderTraversal(root){ if (root === null) { return ; } this.postOrderTraversal(root.left); console.log(root.value); this.postOrderTraversal(root.right) } findAppropriatePlace(root, value) { const side = root.value < value ? 'right' : 'left'; if (side !== '' && root[side] === null) { return {node : root, side}; } if(root.value < value) { //right return this.findAppropriatePlace(root.right, value); } else { //left return this.findAppropriatePlace(root.left, value); } }}const test = new BinaryTree(20);test.insertNode(10);test.insertNode(30);test.insertNode(5);test.insertNode(12);test.insertNode(3);test.insertNode(6);test.insertNode(11);test.insertNode(15);test.insertNode(25);test.insertNode(40);console.log(test);console.log('-------------preOrderTraversal---------');test.preOrderTraversal(test);console.log('-------------inOrderTraversal---------');test.inOrderTraversal(test)console.log('-------------postOrderTraversal---------');test.postOrderTraversal(test)test.removeFromNode(30);console.log(test)/*{ "value": 20, "left": { "value": 10, "left": { "value": 5, "left": { "value": 3, "left": null, "right": null }, "right": { "value": 6, "left": null, "right": null } }, "right": { "value": 12, "left": { "value": 11, "left": null, "right": null }, "right": { "value": 15, "left": null, "right": null } } }, "right": { "value": 30, "left": { "value": 25, "left": null, "right": null }, "right": { "value": 40, "left": null, "right": null } }}-------------preOrderTraversal---------2010536121115302540-------------inOrderTraversal---------3561011121520253040-------------postOrderTraversal---------3561011121520253040------------------------- **After delete node 30** --------------------BinaryTree { value: 20, left: BinaryTree { value: 10, left: BinaryTree { value: 5, left: [BinaryTree], right: [BinaryTree] }, right: BinaryTree { value: 12, left: [BinaryTree], right: [BinaryTree] } }, right: null}*/
以上就是使用 Javascript 实现各种树算法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1490152.html
微信扫一扫 
支付宝扫一扫 
