树是计算机科学中经常用到的一种数据结构。树是一种非线性的数据结构,以分层的方式存储数据。是被用来存储具有层级关系或有序的数据,比如文件系统中的文件。
二叉树,每个节点最多有两个子树的树结构。二叉树是一种特殊的树,也是一个连通的无环图。
二叉查找树是一种特殊的二叉树,其相对较小的值保存在左节点中,较大的值保存在右节点中。这一特性使其查找效率很高。
如果待插入节点小于(大于)当前节点,且当前节点的左(右)节点为 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.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 树等等。树能很好的保证字典序,存储词典的空间压缩率高, 能做前缀搜索。抽象地说,基本上有序列的地方就可以应用树,因为树结构即是一种序列索引结构。
来源: http://www.bubuko.com/infodetail-1994435.html