前端二叉树

（一）构造二叉树

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)

最后编辑于：2019.03.24 15:31:55

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 212,294评论 6赞 493
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,493评论 3赞 385
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 157,790评论 0赞 348
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,595评论 1赞 284
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,718评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,906评论 1赞 290
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,053评论 3赞 410
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,797评论 0赞 268
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,250评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,570评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,711评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,388评论 4赞 332
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,018评论 3赞 316
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,796评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,023评论 1赞 266
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,461评论 2赞 360
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,595评论 2赞 350

前端二叉树

（一）构造二叉树

（二）中序遍历

（三）前序遍历

（四）后序遍历

（五）查找最小值

（六）查找最大值

（七）查找给定值

（八）删除指定节点

完整代码如下：

推荐阅读更多精彩内容