JavaScript实现排序二叉树的基本操作

下面我们用代码实现一波

首先是树的结构和根节点

var Node = function(key){//节点结构        this.left = null         this.right = null        this.key = key    }
     var root = null //根节点

二叉树的插入，基本过程是比较要插入的数和当前节点的值大小，按照 排序二叉树 的特点，左边的值永远小于右边

var insertNode = function(node,newNode){        if(node.key > newNode.key){//要插入的值小于当前节点，左子树遍历            if(node.left === null){                node.left = newNode                return             }else{                insertNode(node.left,newNode)            }        }else if(node.key <= newNode.key){//要插入的值小于当前节点，右子树遍历            if(node.right === null){                node.right = newNode            }else{                insertNode(node.right,newNode)            }        }    }

插入成功后我们分别来实现排序二叉树的前序，中序和后序遍历

前序遍历是先访问根节点，而后是左右节点

中序遍历先访问左节点，而后是根节点和右节点

后序遍历则先访问左右节点，最后是根节点

代码如下

 var inOrderTraverseNode = function(node,callback){//中序遍历        if(node !== null){            inOrderTraverseNode(node.left)            console.log(node.key)            inOrderTraverseNode(node.right)        }    }
   
    var preOrderTraverseNode = function(node,callback){//前序遍历        if(node !== null){            console.log(node.key)            preOrderTraverseNode(node.left)            preOrderTraverseNode(node.right)        }    }
   
    var afterOrderTraversNode = function(node,callback){//后序遍历        if(node !== null){            afterOrderTraversNode(node.left)            afterOrderTraversNode(node.right)            console.log(node.key)        }    }

寻找二叉树的最大值和最小值，这一部分根据 排序二叉树 的特点很快就能知道，最大值在最右边的叶子节点，最小值处于最左边的叶子节点

var Max = function(node){//最大值        if(node.right !== null){            maxNum = Max(node.right)        }else{            return node.key        }        return maxNum    }
    var Min = function(node){//最小值        if(node.left !== null){            minNum = Min(node.left)        }else{            return node.key        }        return minNum    }

寻找 排序二叉树 中的指定值，也很简单，以根节点为界，比左边小到左边找，比右边小去右边

var Search = function(node,key){//寻找指定值                    if(node.key === key){                return true            }else{                if(key < node.key && node.left !=null){                    return Search(node.left,key)                }else if(key > node.key && node.left !=null){                    return Search(node.right,key)                }else{                    return false                }            }        }

最麻烦的是删除节点的操作，这里需要分三种情况，删除节点无子树，删除节点为单子树，删除节点有两个子树，

无子树最简单，直接删

 if(node.left === null && node.right === null){                node = null                return node            }

有单子树的：比如下图（画的有点丑。。。），现在我要删掉3，

代码实现如下

else if(node.left !== null && node.right === null){                node = node.left                return node            }else if(node.left === null && node.right !== null){                node = node.right                return node            }

按照上面的思想，找到4代替3，然后删掉一开始找到的4所在的节点

依旧满足排序二叉树的特点

else if(node.left !== null && node.right !== null){                var minNode = finMinNode(node.right)                node.key = minNode.key                node.right = Remove(node.right,minNode.key)                return node            }

到这里排序二叉树的基本功能都实现了

完整代码在GitHub（求GitHub小星星）上，我把双向链表也用JavaScript实现了下，需要的也可以看看

原文发布时间为：2018年06月23日
原文作者：笑佛弥勒

本文来源： 掘金 如需转载请联系原作者