前端大全

前端二叉树

2019-03-20  本文已影响21人  yun_154192

（一）构造二叉树

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)
上一篇下一篇

猜你喜欢

热点阅读