排序二叉树——删除指定节点

之前也对二叉树的增添了各种方法,添加节点,查找节点是否存在,3种不同的遍历方法,其实三种方法跟搜索引擎的抓取有点相似,假如你了解SEO,或者说懂一点搜索引擎的抓取的话,你就能理解为什么会有深度遍历和广度遍历了,想了解的可以看看我之前写的一篇《搜索引擎的工作原理》

好了,不说废话了,对于二叉树算法最后在添加一个删除方法,删除的意思大家都知道,带着思维,然后跟着代码理一遍,最后在自己写出来。下面就是代码:

<script type="text/javascript">
    function BinaryyTree() {
        var Node=function (key) {              //定义一个节点
            this.key=key;
            this.left=null;
            this.right=null;
        }
        var root =null;
        var insertNode=function (node,newNode) {         //二叉树的实现方法
            if (newNode.key<node.key){
                if (node.left==null){
                    node.left=newNode;
                }else {
                    insertNode(node.left,newNode);
                }
            }else {
                if (node.right==null){
                    node.right=newNode;
                }else {
                    insertNode(node.right,newNode);
                }
            }
        }
        this.insert=function (key) {              //二叉树创建接口
            var newNode= new Node(key);
            if (root===null){
                root=newNode;
            }else {
                insertNode(root,newNode);
            }
        };

        var findminNode=function (node) {                 //找最小节点
            if(node){
                while (node&&node.left!==null){
                    node=node.left;
                }
                return node;
            }
            return null;
        }
        var removeNode=function (node, key) {                   //删除节点流程
            if (node===null){
                return null
            }
            if (node.key>key){
                 node.left=removeNode(node.left,key);
                 return node;
            }else if(node.key<key){
                 node.right = removeNode(node.right,key);
                 return node;
            }else {
                if (node.left===null&&node.right===null){
                    node=null;
                    return node;
                }else  if(node.left===null){
                    node = node.right;
                    return node;
                }else if (node.right===null){
                    node=node.left;
                }else {
                    var aux=findminNode(node.right);             //在当前节点的右节点中找出最小节点
                    node.key=aux.key;
                    node.right=removeNode(node,aux);
                    return node;
                }
            }
        }
        this.remove=function (key) {              //删除节点接口
            root=removeNode(root,key);
        };
        var inOrderNode=function (node, callback) {      //中序遍历实现流程
            if (node!==null){
                inOrderNode(node.left,callback);
                callback(node.key);
                inOrderNode(node.right,callback);
            }
        }
        this.inOrder=function (callback) {             //中序遍历接口
            inOrderNode(root,callback);
        }

    }
    var node=[7,3,9,5,12,21,18,32];        //创建一个数组
    var binaryyTree= new BinaryyTree();    //构造一颗二叉树
    node.forEach(function (key) {            //创建一颗二叉树
        binaryyTree.insert(key);
    })
    var callback=function (key) {
        console.log(key);
    }
    binaryyTree.remove(12);
    binaryyTree.inOrder(callback);
</script>

最后需要在后台调试一下,看一下代码是否正确,看看是否正确删除了节点后,而不影响二叉树的结构,所以我又运用了之前的中序遍历输出一遍,看看是否正确,结果是从小到大遍历的,那说明二叉树结构也是正确的。下面就是代码在后台输出的结果

删除节点

陈健的个人博客,记录生活所见所感、学习笔记。专注于Web前端_SEO教程_读书心得。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

返回主页看更多
狠狠的抽打博主 支付宝 扫一扫