美文网首页前端大全
前端二叉树

前端二叉树

作者: yun_154192 | 来源:发表于2019-03-20 21:41 被阅读21次

    （一）构造二叉树

    function BinaryTree(){
    var Node = function (key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }
    var root = null;

    // 构造二叉树
    this.insert = function (key) {
        var newNode = new Node(key)
        if (root == null) {
            root = newNode
        } else {
            insertNode(root, newNode)
        }
    }
    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)
            }
        }
    }
}
var nodes = [1,2,3,2,14,23,9,17,13,6]
var binaryTree = new BinaryTree()
nodes.forEach(function(key){
    binaryTree.insert(key)
})

    （二）中序遍历

    function BinaryTree(){
    //...
    // 中序遍历
    var inOrderTraverseNode = function (node, callback) {
        if (node !== null) {
            inOrderTraverseNode(node.left, callback)
            callback(node.key)
            inOrderTraverseNode(node.right, callback)
        }
    }
    this.inOrderTraverse = function (callback) {
        inOrderTraverseNode(root, callback)
    }
}
var nodes = [1,2,3,2,14,23,9,17,13,6]
var binaryTree = new BinaryTree()
//nodes.forEach(function(key){
//  binaryTree.insert(key)
//})    

var callback = function (key) {
    console.log(key)
}
binaryTree.inOrderTraverse(callback)

    （三）前序遍历

    前序遍历可以复制二叉树，效率比重新构造二叉树高

    function BinaryTree(){
    // ...
    // 前序遍历
    var preOrderTraverseNode = function (node, callback) {
        if (node !== null) {
            callback(node.key)
            preOrderTraverseNode(node.left, callback)
            preOrderTraverseNode(node.right, callback)
        }
    }
    this.preOrderTraverse = function (callback) {
        preOrderTraverseNode(root, callback)
    }
}
var nodes = [1,2,3,2,14,23,9,17,13,6]
var binaryTree = new BinaryTree()
//nodes.forEach(function(key){
//  binaryTree.insert(key)
//})    

var callback = function (key) {
    console.log(key)
}
//binaryTree.inOrderTraverse(callback)
binaryTree.preOrderTraverse(callback)

    （四）后序遍历

    当要删除操作系统中的文件时，可以利用后序遍历，查看当前路径下还有没有文件，没有即可删除

    function BinaryTree(){
    // ...
    // 后序遍历
    var postOrderTraverseNode = function (node, callback) {
        if (node !== null) {
            postOrderTraverseNode(node.left, callback)
            postOrderTraverseNode(node.right, callback)
            callback(node.key)
        }
    }
    this.postOrderTraverse = function (callback) {
        postOrderTraverseNode(root, callback)
    }
}
var nodes = [1,2,3,2,14,23,9,17,13,6]
var binaryTree = new BinaryTree()
//nodes.forEach(function(key){
//  binaryTree.insert(key)
//})    

var callback = function (key) {
    console.log(key)
}
//binaryTree.inOrderTraverse(callback)
//binaryTree.preOrderTraverse(callback)
binaryTree.postOrderTraverse(callback)

    （五）查找最小值

    function BinaryTree(){
    // ...
    // 查找最小值
    var minNode = function (node) {
        if (node) {
            while (node && node.left !== null) {
                node = node.left
            }
            return node.key
        }
        return null
    }
    this.min = function () {
        return minNode (root)
    }
}
var nodes = [1,2,3,2,14,23,9,17,13,6]
var binaryTree = new BinaryTree()
//nodes.forEach(function(key){
//  binaryTree.insert(key)
//})    

var callback = function (key) {
    console.log(key)
}
//binaryTree.inOrderTraverse(callback)
//binaryTree.preOrderTraverse(callback)
//binaryTree.postOrderTraverse(callback)

console.log("min node is: " + binaryTree.min())

    （六）查找最大值

    function BinaryTree(){
    // ...
    // 查找最大值
    var maxNode = function (node) {
        if (node) {
            while (node && node.right !== null) {
                node = node.right
            }
            return node.key
        }
        return null
    }
    this.max = function () {
        return maxNode(root)
    }
}
var nodes = [1,2,3,2,14,23,9,17,13,6]
var binaryTree = new BinaryTree()
//nodes.forEach(function(key){
//  binaryTree.insert(key)
//})    

var callback = function (key) {
    console.log(key)
}
//binaryTree.inOrderTraverse(callback)
//binaryTree.preOrderTraverse(callback)
//binaryTree.postOrderTraverse(callback)

//console.log("min node is: " + binaryTree.min())
console.log("max node is: " + binaryTree.max())

    （七）查找给定值

    function BinaryTree(){
    // ...
    // 查找给定值
    var searchNode = function (node, key) {
        if (node === null) {
            return false
        }
        if (key < node.key) {
            return searchNode(node.left, key)
        } else if (key > node.key) {
            return searchNode(node.right, key)
        } else {
            return true
        }
    }
    this.search = function (key) {
        return searchNode(root, key)
    }
}
var nodes = [1,2,3,2,14,23,9,17,13,6]
var binaryTree = new BinaryTree()
//nodes.forEach(function(key){
//  binaryTree.insert(key)
//})    

var callback = function (key) {
    console.log(key)
}
//binaryTree.inOrderTraverse(callback)
//binaryTree.preOrderTraverse(callback)
//binaryTree.postOrderTraverse(callback)

//console.log("min node is: " + binaryTree.min())
//console.log("max node is: " + binaryTree.max())
console.log(binaryTree.search(3) ? 'key 3 is found' : 'key 3 is not found')

    （八）删除指定节点

    function BinaryTree(){
    // ...
    // 删除指定节点
    var removeNode = function (node, key) {
        if (node === null) {
            return null
        }
        if (key < node.key) {
            node.left = removeNode(node.left, key)
            return node
        } else if (key > node.key) {
            node.right = removeNode(node.right, key)
            return node
        } else {
            if (node.left === null && node.right === null) {
                node = null
                return node
            }
            if (node.left === null) {
                node = node.right
                return node
            } else if (node.right === null) {
                node = node.right
                return node 
            }
            // 删除节点有两个子节点时
            // 找到右子树中最小节点替换删除的节点
            var aux = findMinNode(node.right)
            node.key = aux.key
            node.right = removeNode(node.right, aux)
        }
    }
    this.remove= function (key) {
        root = removeNode(root, key)
    }
}
var nodes = [1,2,3,2,14,23,9,17,13,6]
var binaryTree = new BinaryTree()
//nodes.forEach(function(key){
//  binaryTree.insert(key)
//})    

var callback = function (key) {
    console.log(key)
}
//binaryTree.inOrderTraverse(callback)
//binaryTree.preOrderTraverse(callback)
//binaryTree.postOrderTraverse(callback)

//console.log("min node is: " + binaryTree.min())
//console.log("max node is: " + binaryTree.max())
//console.log(binaryTree.search(3) ? 'key 3 is found' : 'key 3 is not found')
binaryTree.remove(23)

    完整代码如下：

    function BinaryTree(){
    var Node = function (key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }
    var root = null;

    // 构造二叉树
    this.insert = function (key) {
        var newNode = new Node(key)
        if (root == null) {
            root = newNode
        } else {
            insertNode(root, newNode)
        }
    }
    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)
            }
        }
    }

    // 中序遍历
    var inOrderTraverseNode = function (node, callback) {
        if (node !== null) {
            inOrderTraverseNode(node.left, callback)
            callback(node.key)
            inOrderTraverseNode(node.right, callback)
        }
    }
    this.inOrderTraverse = function (callback) {
        inOrderTraverseNode(root, callback)
    }

    // 前序遍历
    var preOrderTraverseNode = function (node, callback) {
        if (node !== null) {
            callback(node.key)
            preOrderTraverseNode(node.left, callback)
            preOrderTraverseNode(node.right, callback)
        }
    }
    this.preOrderTraverse = function (callback) {
        preOrderTraverseNode(root, callback)
    }

    // 后序遍历
    var postOrderTraverseNode = function (node, callback) {
        if (node !== null) {
            postOrderTraverseNode(node.left, callback)
            postOrderTraverseNode(node.right, callback)
            callback(node.key)
        }
    }
    this.postOrderTraverse = function (callback) {
        postOrderTraverseNode(root, callback)
    }

    // 查找最小值
    var minNode = function (node) {
        if (node) {
            while (node && node.left !== null) {
                node = node.left
            }
            return node.key
        }
        return null
    }
    this.min = function () {
        return minNode (root)
    }

    // 查找最大值
    var maxNode = function (node) {
        if (node) {
            while (node && node.right !== null) {
                node = node.right
            }
            return node.key
        }
        return null
    }
    this.max = function () {
        return maxNode(root)
    }

    // 查找给定值
    var searchNode = function (node, key) {
        if (node === null) {
            return false
        }
        if (key < node.key) {
            return searchNode(node.left, key)
        } else if (key > node.key) {
            return searchNode(node.right, key)
        } else {
            return true
        }
    }
    this.search = function (key) {
        return searchNode(root, key)
    }

    // 查找最小值
    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 (key < node.key) {
            node.left = removeNode(node.left, key)
            return node
        } else if (key > node.key) {
            node.right = removeNode(node.right, key)
            return node
        } else {
            if (node.left === null && node.right === null) {
                node = null
                return node
            }
            if (node.left === null) {
                node = node.right
                return node
            } else if (node.right === null) {
                node = node.right
                return node 
            }
            // 删除节点有两个子节点时
            // 找到右子树中最小节点替换删除的节点
            var aux = findMinNode(node.right)
            node.key = aux.key
            node.right = removeNode(node.right, aux)
        }
    }
    this.remove= function (key) {
        root = removeNode(root, key)
    }
}
var nodes = [1,2,3,2,14,23,9,17,13,6]
var binaryTree = new BinaryTree()
nodes.forEach(function(key){
    binaryTree.insert(key)
})  

var callback = function (key) {
    console.log(key)
}
binaryTree.inOrderTraverse(callback)
binaryTree.preOrderTraverse(callback)
binaryTree.postOrderTraverse(callback)

console.log("min node is: " + binaryTree.min())
console.log("max node is: " + binaryTree.max())
console.log(binaryTree.search(3) ? 'key 3 is found' : 'key 3 is not found')
binaryTree.remove(23)

    相关文章

      网友评论

        本文标题：前端二叉树

        本文链接：https://www.haomeiwen.com/subject/qhjxvqtx.html

        延伸阅读

        深度阅读

        • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

        栏目导航

        热点阅读

        前端大全

        关于我们|服务条款|联系我们|前端二叉树|投稿指南|网站地图|RSS订阅|排版工具|手机版

        提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

        Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

        备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

        本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

        所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！