JavaScript数据结构-树

我觉得这社会上，也不差钱好多人，可能好多人也不差权力，但是我觉得能得到这种满足的也不多。 --郭小平<临汾红丝带学校校长>

​ 树是计算机科学中经常用到的一种数据结构。树是一种非线性的数据结构，以分层的方式存储数据。是被用来存储具有层级关系或有序的数据，比如文件系统中的文件。

二叉树

二叉树，每个节点最多有两个子树的树结构。二叉树是一种特殊的树，也是一个连通的无环图。

二叉查找树

​ 二叉查找树是一种特殊的二叉树，其相对较小的值保存在左节点中，较大的值保存在右节点中。这一特性使其查找效率很高。

实现二叉查找树

​ 如果待插入节点小于（大于）当前节点，且当前节点的左（右）节点为null，则将待插入节点插入到当前节点的左（右）节点位置上，结束循环；否则，将当前节点的左（右）节作为当前节点继续下次循环。

/** * 节点定义 * @param data 数据 * @param left 左子树 * @param right 右子树 * @constructor */ function Node(data, left, right) { this.data = data; this.left = left; this.right = right; } Node.prototype.show = function() { return this.data; }; /** * 二叉查找树定义 * @constructor */ function BST() { this.root = null; } /** * 插入节点 * @constructor */ BST.prototype.insert = function(data) { // 待插入节点 var node = new Node(data, null, null); if(this.root === null) { this.root = node; } else { var currentNode = this.root; var parent; while(true) { parent = currentNode; // 待插入节点小于当前节点 if(data < currentNode.data) { // 将其左子树作为当前节点 currentNode = currentNode.left; if(currentNode === null) { parent.left = node; break; } }else { // 将其右子树作为当前节点 currentNode = currentNode.right; if(currentNode === null) { parent.right = node; break; } } } } return this; // 支持链式调用 }; 中序：先访问左子树，再访问根节点，最后访问右字数；以升序访问BST上所有节点；（左==>根==>右）先序：先访问根节点，然后以同样方式访问左子树和右子树；（根==>左==>右）后序：先访问叶子节点，从左子树到右子树，再到根节点。（左==>右==>根） BST.prototype.order = function(node, type) { switch (type) { case "inorder": // 中序 if(node != null) { /*左==>根==>右*/ this.order(node.left, type); console.log(node.show()); this.order(node.right, type); } break; case "preorder": // 先序 if(node != null) { /*根==>左==>右*/ console.log(node.show()); this.order(node.left, type); this.order(node.right, type); } break; case "postorder": // 后序 if(node != null) { /*左==>右==>根*/ this.order(node.left, type); this.order(node.right, type); console.log(node.show()); } break; } };

测试

var bst = new BST(); bst.insert(32).insert(11).insert(2) .insert(13).insert(75) .insert(66).insert(88); bst.order(bst.root, "inorder"); // 中序 bst.order(bst.root, "preorder"); // 先序 bst.order(bst.root, "postorder"); // 后序

查询最小值和最大值

最小值：遍历左子树，直到找到最后一个节点；最大值：遍历右子树，直到找到最后一个节点。 /** * 获取最小值：左子树的最后一个节点 */ BST.prototype.getMin = function(node) { var currentNode = node || this.root; while(currentNode.left !== null) { currentNode = currentNode.left; } return currentNode; }; /** * 获取最小值：右子树的最后一个节点 */ BST.prototype.getMax = function(node) { var currentNode = node || this.root; while(currentNode.right !== null) { currentNode = currentNode.right; } return currentNode; }; console.log(bst.getMin().data); // 2 console.log(bst.getMax().data); // 88

查找某节点

/** * 查找某节点 * @param data 数据 */ BST.prototype.find = function(data) { var currentNode = this.root; while(currentNode !== null) { if(data === currentNode.data) { return currentNode; } currentNode = (data < currentNode.data) ? currentNode.left : currentNode.right; } return null; }; console.log(bst.find(66)); // Node { data: 66, left: null, right: null } console.log(bst.find(99)); // null

删除节点

如果待删除节点为叶子节点，则直接删除它；如果待删除节点只有一个子节点，则直接将待删除节点的父节点指向其子节点；如果待删除节点包含两个子节点，我们选择右子树上的最小值创建一个临时节点，然后复制到待删节点，然后删除最小值节点。 /** * 移除指定数据节点 * @param data */ BST.prototype.remove = function(node, data) { node = node || this.root; if(data === null) { // 待删除节点不存在 return node; } if(node.data === data) { // 无子节点 if(node.left === null && node.right === null) { return null; } // 只有右节点，无左节点 if(node.left === null) { return node.right; } // 只有左节点，无右节点 if(node.right === null) { return node.left; } // 存在两个节点 var minNode = this.getMin(node.right); console.log(minNode); node.data = minNode.data; node.right = this.remove(node.right, minNode.data); }else if( node.data > data) { node.left = this.remove(node.left, data); }else if( node.data < data){ node.right = this.remove(node.right, data); } return node; };

总结

​ 树，在计算机科学中体现的特别多 。如，我们熟悉的DOM树，数据库底层经常用到的B树等等。树能很好的保证字典序，存储词典的空间压缩率高, 能做前缀搜索。抽象地说，基本上有序列的地方就可以应用树，因为树结构即是一种序列索引结构。

奋飛 认证博客专家 技术管理 前端工程化 乐观、勇气、专注、果断、好奇、公正、慎思、真诚、追求极致追求完美、诚信！独立撰写了多个前端专题模块，访问量达百万级。多次负责组织大数据可视化前端架构平台开发工作。对前端新技术、新潮流具有很强的敏锐力和洞察力！