欢迎来到新闻!
我的订单 签到有礼 资讯中心
当前位置:首页 > 代码知识 >
代码知识

【Java】JavaScript数据结构-树

发布日期:2019-12-16 09:30 浏览量:0

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

428.png

  二叉树

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

429.png

  二叉查找树

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

430.png

  实现二叉查找树

   如果待插入节点小于(大于)当前节点,且当前节点的左(右)节点为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树等等。树能很好的保证字典序,存储词典的空间压缩率高, 能做前缀搜索。抽象地说,基本上有序列的地方就可以应用树,因为树结构即是一种序列索引结构。