资讯专栏INFORMATION COLUMN

《学习JavaScript数据结构与算法》(第8章)(树)

30e8336b8229 / 1989人阅读

摘要:先序遍历的一种应用是打印一个结构化的文档。方法的实现如下中序遍历中序遍历是一种以上行顺序访问所有节点的遍历方式,也就是以从最小到最大的顺序访问所有节点。中序遍历的一种应用就是对树进行排序操作。

1、二叉搜索树(两个条件):

(1)二叉树中的节点最多只有两个子节点:一个是左侧节点,另一个是右侧子节点;
(2)只允许在左侧节点存储(比父节点)小的值,在右侧节点存储(比父节点)大(或者等于)的值;

2、代码主要架构:

主要包括有插入(insert)、搜索(search)、移除(removce)、遍历(traverse)等功能

var Tree = function() {
    var Node = function(value) {
        this.value = value;
        this.left = null;  //左节点
        this.right = null; //右节点
    }
    var root = null;    //根节点  
    /*
    插入节点:
    1、树为空
    2、树不为空 -> 比较(小于 -> 往左走;大于 -> 往右走)
    */ 
    this.insert = function(value) {};
    //搜索节点(搜索一个特定的值)
    this.search = function(value) {};
    //寻找树的最小键的方法
    this.min = function() {};
    //寻找树的最大键的方法
    this.max = function() {};
    /*
    移除节点:
    1、最简单的情况:移除叶节点
    2、移除只有一个子节点的节点
    3、移除有两个子节点的节点(替换为右侧子树的最小节点)
    */
    this.remove =function(value) {
    };
    //遍历节点
    this.traverse = function(callback) {};
    
    //显示树
    this.getRoot = function() {};
}
3、整体详细代码部分
var Tree = function() {
    var Node = function(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
    var root = null;    //根节点  
    /*
    插入节点:
    1、树为空
    2、树不为空 -> 比较(小于 -> 往左走;大于 -> 往右走)
    */ 
    this.insert = function(value) {
        var newNode = new Node(value);
        if(root == null) { //空树          
            root = newNode;
        }else{//树非空           
            insertNode(root, newNode);
        }
    };
    var insertNode = function(node, newNode) {
        if(newNode.value > node.value) {
            //往右走
            if(node.right == null) {
                node.right = newNode;
            }else{
                insertNode(node.right, newNode);
            }   
        }else if(newNode.value < node.value) {
            //往左走
            if(node.left == null) {
                node.left = newNode;
            }else{
                insertNode(node.left, newNode);
            }
        }
    };


    //搜索节点(搜索一个特定的值)
    this.search = function(value) {
        return searchNode(root, value);
    };
    var searchNode = function(node, value) {
        if(node === null) {
            return false;
        }
        if(value < node.value) {
            return searchNode(node.left, value);
        }else if(value > node.value) {
            return searchNode(node.right, value);
        }else{
            return true;
        }
    };
   //寻找树的最小键的方法
   this.min = function() {
       return minNode(root);
   };
   var minNode = function(node) {
       if(node) {
           while(node && node.left !== null) {
               node = node.left;
           }
           return node.value;
       }
       return null;
   };
   //寻找树的最大键的方法
   this.max = function() {
       return maxNode(root);
   };
   var maxNode = function(node) {
       if(node) {
           while(node && node.right !== null) {
               node = node.right;
           }
           return node.value;
       }
       return null;
   };

    /*
    移除节点:
    1、最简单的情况:移除叶节点
    2、移除只有一个子节点的节点
    3、移除有两个子节点的节点(替换为右侧子树的最小节点)
    */
    this.remove =function(value) {
        root = removeNode(root, value);
    };
    var removeNode = function(node,value) {
        if( node == null) return null;
        if(node.value < value) {
            //继续向右查找
            node.right = removeNode(node.right , value);
            return node;
        }else if(node.value > value) {
            //向左查找
            node.left = removeNode(node.left, value);
            return node;
        }else{
            //value == node.value
            //执行删除过程
            //叶节点条件
            if(node.left == null && node.right == null) {
                node = null;
                return node;
            }
            //只有一个子节点条件
            if(node.left == null && node.right) {
                node = node.right;
                return node;     
            }else if(node.right == null && node.left){
                node = node.left;
                return node;
            }

            //有两个子节点(替换为右侧子树的最小节点)
            var aux = findMinNode(node.right);   //aux是查找到的最小的子节点
            node.value = aux.value;
            node.right = removeNode(node.right, aux.value);
            return node;
        }
    };
    var findMinNode = function(node) {
        if(node == null) return null;
        while(node && node.left) {
            node = node.left;
        }
        return node;
    };


    //遍历节点
    this.traverse = function(callback) {
        traverse(root, callback);
    };
    var traverse = function(node, callback) {
        if(node == null) return;
        //(后续遍历)左右中;(中序遍历)左中右;(前序遍历)中左右
        traverse(node.left, callback);
        traverse(node.right, callback);
        callback(node.value);
    };
    
    //显示树
    this.getRoot = function() {
        return root;
    };
}
4、代码功能验证测试
var t = new Tree;
var print = function(value) {
    console.log("value -",value)   
};

t.insert(11);
t.insert(8);
t.insert(4);
t.insert(9);
t.insert(3);
t.insert(5);

t.insert(9);
t.insert(12);

t.search(9); //true
t.remove(8);
t.min(); //3
t.max(); //12
t.traverse(print); 

5、遍历方式 先序遍历

先序遍历是以优先于后代节点的顺序访问每个节点的。先序遍历的一种应用是打印一个结构化的文档。


11 7 5 3 6 9 8 10 15 13 12 14 20 18 25

this.preOrderTraverse = function(callback){
    preOrderTraverseNode(root, callback);
};
preOrderTraverseNode方法的实现如下:
var preOrderTraverseNode = function (node, callback) {
    if (node !== null) {
        callback(node.key); //{1}
        preOrderTraverseNode(node.left, callback); //{2}
        preOrderTraverseNode(node.right, callback); //{3}
    }
};
中序遍历

中序遍历是一种以上行顺序访问BST所有节点的遍历方式,也就是以从最小到最大的顺序访问所有节点。中序遍历的一种应用就是对树进行排序操作。


3 5 6 7 8 9 10 11 12 13 14 15 18 20 25

this.inOrderTraverse = function(callback){
    inOrderTraverseNode(root, callback); //{1}
};
var inOrderTraverseNode = function (node, callback) {
    if (node !== null) { //{2}
    inOrderTraverseNode(node.left, callback); //{3}
    callback(node.key); //{4}
    inOrderTraverseNode(node.right, callback); //{5}
    }
};
后序遍历

后序遍历则是先访问节点的后代节点,再访问节点本身。后序遍历的一种应用是计算一个目录和它的子目录中所有文件所占空间的大小。


3 6 5 8 10 9 7 12 14 13 18 25 20 15 11

this.postOrderTraverse = function(callback){
    postOrderTraverseNode(root, callback);
};
postOrderTraverseNode方法的实现如下:
var postOrderTraverseNode = function (node, callback) {
    if (node !== null) {
        postOrderTraverseNode(node.left, callback); //{1}
        postOrderTraverseNode(node.right, callback); //{2}
        callback(node.key); //{3}
    }
};

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/106474.html

相关文章

  • 学习JavaScript数据结构算法》(8)(平衡二叉代码实现)

    摘要:平衡二叉树代码实现根节点插入节点树为空树不为空比较小于往左走大于往右走空树树非空自平衡树插入新节点向左走向左子树拆入新节点,且节点的值小于其左子节点时,应该进行旋转。 平衡二叉树JS代码实现 var Tree = function() { var Node = function(value) { this.value = value; this....

    isLishude 评论0 收藏0
  • ApacheCN 人工智能知识 v1.0

    摘要:贡献者飞龙版本最近总是有人问我,把这些资料看完一遍要用多长时间,如果你一本书一本书看的话,的确要用很长时间。为了方便大家,我就把每本书的章节拆开,再按照知识点合并,手动整理了这个知识树。 Special Sponsors showImg(https://segmentfault.com/img/remote/1460000018907426?w=1760&h=200); 贡献者:飞龙版...

    刘厚水 评论0 收藏0
  • 高性能JavaScript(文档)

    摘要:最近在全力整理高性能的文档,并重新学习一遍,放在这里方便大家查看并找到自己需要的知识点。 最近在全力整理《高性能JavaScript》的文档,并重新学习一遍,放在这里方便大家查看并找到自己需要的知识点。 前端开发文档 高性能JavaScript 第1章:加载和执行 脚本位置 阻止脚本 无阻塞的脚本 延迟的脚本 动态脚本元素 XMLHTTPRequest脚本注入 推荐的无阻塞模式...

    RayKr 评论0 收藏0
  • 翻译连载 | 9 :递归(上)-《JavaScript轻量级函数式编程》 |《你不知道的JS》

    摘要:一旦我们满足了基本条件值为,我们将不再调用递归函数,只是有效地执行了。递归深谙函数式编程之精髓,最被广泛引证的原因是,在调用栈中,递归把大部分显式状态跟踪换为了隐式状态。 原文地址:Functional-Light-JS 原文作者:Kyle Simpson-《You-Dont-Know-JS》作者 关于译者:这是一个流淌着沪江血液的纯粹工程:认真,是 HTML 最坚实的梁柱;...

    MasonEast 评论0 收藏0
  • Java学习路线总结,搬砖工逆袭Java架构师(全网最强)

    摘要:哪吒社区技能树打卡打卡贴函数式接口简介领域优质创作者哪吒公众号作者架构师奋斗者扫描主页左侧二维码,加入群聊,一起学习一起进步欢迎点赞收藏留言前情提要无意间听到领导们的谈话,现在公司的现状是码农太多,但能独立带队的人太少,简而言之,不缺干 ? 哪吒社区Java技能树打卡 【打卡贴 day2...

    Scorpion 评论0 收藏0

发表评论

0条评论

30e8336b8229

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<