Javascript实现二叉树算法_技术笔记

qq_阿泽呀_1 2018-12-07

<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta http-equiv="X-UA-Compatible" content="ie=edge" />
<title>Document</title>
</head>
<body>
<script>
function BinaryTree() {
//初始化root根为空值

var root = null

//将传入值添加this.key,this.left,this.right属性

var Node = function(key) {
this.key = key

this.left = null

this.right = null
}

//将传入值进行判断,作为父节点的左支或右支

var insertNode = function(node, newNode) {
if (newNode.key < node.key) {
//如果传入值小于父节点,作为左支,不过要先进行判断左支是否已经存在

if (node.left === null) {
//如果左支是null空值,将传入值作为左支

node.left = newNode
console.log(node.left.key)
} else {
//否则(左支已经存在)继续执行函数进行下个节点的判断

insertNode(node.left, newNode)
}
} else {
//否则(传入值大于父节点)作为右支,不过要先进行判断右支是否已经存在

if (node.right === null) {
//如果右支是null空值,将传入值作为右支

node.right = newNode
console.log(node.right.key)
} else {
//否则(右支已经存在)继续执行函数进行下个节点的判断

insertNode(node.right, newNode)
}
}
}

//函数的入口,第一步执行的函数,确定root根的值

this.insert = function(key) {
var newNode = new Node(key)
if (root === null) {
root = newNode
console.log(root.key)
//如果没有root根,将传入值作为root根
} else {
insertNode(root, newNode)
//如果已经存在根,执行insertNode函数
}
}

// 删除二叉树
this.remove = function(key) {
root = removeNode(root, key)
}
}

//传入子节点(callback)和父节点(node)(第一次的父节点就是root)
var inOrderTraverseNode = function(node, callback) {
//如果父节点存在,继续将左支和右支执行inOrderTraverseNod(),直到不存在子分支为止

// !!注意if结构里面的函数执行顺序,先执行inOrderTraverseNode(node.left,callback);再执行callback(node.key);最后执行inOrderTraverseNode(node.right,callback);

//当inOrderTraverseNode(node.left,callback);执行完之后,才会再执行callback(node.key);(即先打印完左分支的值,再打印最顶层的父节点,这样就达到了从小到大的排序效果).右分支同理

if (node !== null) {
inOrderTraverseNode(node.left, callback)

callback(node.key)

inOrderTraverseNode(node.right, callback)
}
}
var findMinNode = function(node) {
if (node) {
while (node && node.left !== null) {
node = node.left
}
return node
}
return null
}
TODO:;
// 删除二叉树
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.left
return node
}
// 如果左右两个分支都存在的时候,那么执行下面的代码
var aux = findMinNode(node.right)
node.key = aux.key
node.right = removeNode(node.right, aux.key)
return node
}
}
//
var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13]

//实例化BinaryTree

var binaryTree = new BinaryTree()

//遍历nodes数组,将每个数组的值(key)传入binary.insert(),执行 insert()函数

nodes.forEach(function(key) {
binaryTree.insert(key)
})

console.log(binaryTree.remove(10))
</script>
</body>
</html>

2赞 · 2采集

慕前端9063831 2018-10-24

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<script type="text/javascript">
    function binaryTree() {
        /**
         * 定义节点
         * @param key int|float 节点值
         */
        var node = function (key) {
            this.key = key;
            this.left = null;
            this.right = null;
        }

        //定义根节点
        var root = null;

        /**
         * 定义插入属性
         * @param key int|float 要插入的值
         */
        this.insert = function (key) {
            var newNode = new node(key);
            if (root === null) {
                root = newNode;
            } else {
                insertNoder(root, newNode);
            }
        }

        /**
         * 插入数据 小左大右
         * @param node obj 节点数据
         * @param newNode obj 要插入的节点数据
         */
        var insertNoder = function (node, newNode) {
            if (newNode.key < node.key) {
                if (node.left === null) {
                    node.left = newNode;
                } else {
                    insertNoder(node.left, newNode);
                }
            } else {
                if (node.right === null) {
                    node.right = newNode;
                } else {
                    insertNoder(node.right, newNode);
                }
            }
        }

        /**
         * 查找节点
         * @param key int|float 查找的节点值
         * @param node obj 节点
         * @returns obj|null 查找的节点, 不存在返回null
         */
        this.find = function (key, node = root) {
            return findNode(key, node)[1];
        }

        /**
         * 判断节点是否存在
         * @param key int|float 查找的节点值
         * @param node obj 节点
         * @returns bool 存在true, 不存在false
         */
        this.exists = function (key, node = root) {
            return findNode(key, node)[0];
        }

        /**
         * 查找节点
         * @param key int|float 查找的节点值
         * @param node obj 节点
         * @returns array
         */
        var findNode = function (key, node) {
            if (node === null) return [false, null];
            if (key == node.key) return [true, node];
            if (key < node.key) return findNode(key, node.left);
            return findNode(key, node.right);
        }

        /**
         * 中序排列查询
         * @param node obj 节点
         * @returns {Array}
         */
        this.inOrder = function (sort = 'ASC', node = root) {
            var nodeArr = [];
            if (node !== null) {
                if (sort.toUpperCase() == 'DESC') {
                    inOrderDescNode(node, nodeArr);
                } else {
                    inOrderAscNode(node, nodeArr);
                }
            }
            return nodeArr;
        }

        /**
         * 中序查询-升序(左->中->右)
         * @param node obj 节点
         * @param nodeArr array 存储排序的值
         */
        var inOrderAscNode = function (node, nodeArr) {
            if (node !== null) {
                inOrderAscNode(node.left, nodeArr);
                nodeArr.push(node.key)
                inOrderAscNode(node.right, nodeArr);
            }
        }

        /**
         * 中序查询-降序(右->中->左)
         * @param node obj 节点
         * @param nodeArr array 存储排序的值
         */
        var inOrderDescNode = function (node, nodeArr) {
            if (node !== null) {
                inOrderDescNode(node.right, nodeArr);
                nodeArr.push(node.key);
                inOrderDescNode(node.left, nodeArr)
            }
        }

        /**
         * 前序查询
         * @param node obj 节点
         * @returns {Array}
         */
        this.preOrder = function (node = root) {
            var nodeArr = [];
            if (node !== null) {
                preOrderNode(node, nodeArr);
            }
            return nodeArr;
        }

        /**
         * 前序(中->左->右)
         * @param node obj 节点
         * @param nodeArr 存储查询的值
         */
        var preOrderNode = function (node, nodeArr) {
            if (node !== null) {
                nodeArr.push(node.key);
                preOrderNode(node.left, nodeArr);
                preOrderNode(node.right, nodeArr)
            }
        }

        /**
         * 后序查询
         * @param node obj 节点
         * @returns {Array}
         */
        this.reOrder = function (node = root) {
            var nodeArr = [];
            if (node !== null) {
                reOrderNode(node, nodeArr);
            }
            return nodeArr;
        }

        /**
         * 后序(左->右->中)
         * @param node obj 节点
         * @param nodeArr 存储查询的值
         */
        var reOrderNode = function (node, nodeArr) {
            if (node !== null) {
                reOrderNode(node.left, nodeArr);
                reOrderNode(node.right, nodeArr);
                nodeArr.push(node.key);
            }
        }

        /**
         * 最大值
         * @param node obj 节点
         * @returns {*}
         */
        this.max = function (node = root) {
            var newNode = maxNode(node);
            return newNode === null ? null : newNode.key;
        }

        /**
         * 查找一个节点最大的值
         * @param node obj 节点
         * @returns {*}
         */
        var maxNode = function (node) {
            if (node === null) return null;
            while (node !== null && node.right !== null) {
                node = node.right;
            }
            return node;
        }

        /**
         * 最小值
         * @param node obj 节点
         * @returns {*}
         */
        this.min = function (node = root) {
            var newNode = minNode(node);
            return newNode === null ? null : newNode.key;
        }

        /**
         * 查找一个节点最小值
         * @param node obj 节点
         * @returns {*}
         */
        var minNode = function (node) {
            if (node === null) return null;
            if (node.left !== null) return minNode(node.left);
            return node;
        }

        /**
         * 移除一个节点
         * @param key int|float 要移除的节点值
         * @param node obj 节点
         * @returns {*}
         */
        this.remove = function (key, node = root) {
            return removeNode(key, node);
        }

        /**
         * 移除节点
         * @param key int|float 要移除的节点值
         * @param node obj 节点
         * @returns {*}
         */
        var removeNode = function (key, node) {
            if (node === null) return null;
            if (key === node.key) {
                if (node.left === null && node.right === null) return null;
                if (node.left === null) return node.right;
                if (node.right === null) return node.left
                var aux = minNode(node.right);
                node.key = aux.key;
                node.right = removeNode(node.right, aux.key);
                return node;
            }
            if (key < node.key) {
                node.left = removeNode(key, node.left);
                return node;
            }
            node.right = removeNode(key, node.right);
            return node;
        }
    }

    var arr = [9, 7, 4, 4, 6.4, 5, 8, 3.2, 11, 15, 9, 5, 6, 0, 3, 2, 13, 3.6, 1, 12, 14];
    var node = new binaryTree();
    //循环插入数据
    arr.forEach(function (key) {
        node.insert(key);
    })
    console.log('exists: ', node.exists(9));
    console.log('exists-100: ', node.exists(100));
    console.log('find: ', node.find(9));
    console.log('find-1000: ', node.find(1000));
    console.log('inOrder-Asc: ', node.inOrder());
    //js实现对象的复制，不影响原对象
    //var newNode = Object.assign({}, node.find(4));//
    var newNode = JSON.parse(JSON.stringify(node.find(4)));//当源对象的属性值是一个指向对象的引用时，应用深度复制
    console.log('inOrder-Asc-4: ', node.inOrder('ASC', newNode));
    console.log('remove-2: ', node.remove(2,newNode));
    console.log('remove-3: ', node.remove(3));
    console.log('remove-15: ', node.remove(15));
    console.log('inOrder-Asc: ', node.inOrder());
    console.log('inOrder-Asc-4: ', node.inOrder('ASC', newNode));
    console.log('inOrder-desc: ', node.inOrder('DESC'));
    console.log('inOrder-desc-11: ', node.inOrder('DESC', node.find(11)));
    console.log('preOrder: ', node.preOrder());
    console.log('reOrder: ', node.reOrder());
    console.log('max: ', node.max());
    console.log('max-4: ', node.max(node.find(4)));
    console.log('min: ', node.min());
    console.log('min-11: ', node.min(node.find(11)));
    console.log('min-11: ', node.max(null));
</script>
</body>
</html>

2赞 · 0采集

qq_肥_0 2018-08-12
```
源代码：
```
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>Document</title>
</head>
<body>

</body>
<script type="text/javascript">
function BinaryTree () {
var Node = function (key) {
this.key = key;
this.left = null;
this.right = null;
}

this.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(newNode.key > node.key){
if(node.right === null){
node.right = newNode;
}else{
insertNode(node.right,newNode);
}
}
}

this.insert = function (key) {
if(this.root === null){
this.root = new Node(key);
}else{
insertNode(this.root,new Node(key));
}
}
//栈是先进后出的，所以在节点1的时候，它没有左子节点，这个时候开始出栈，继续执行上一次的inOrderTraverceNodes里未执行完的代码，当节点1也没有右子节点的时候，到节点3开始继续执行上一次的inOrderTraverceNodes里未执行完的代码，以此类推。

//栈是先进后出的，一开始节点8执行函数，有左子节点3，节点3执行函数，有左子节点1，节点1执行函数，没有左子节点，这时是null，这时这个函数已经出栈，到节点1之前执行的函数开始出栈了，然后调用callback，打印了1，然后节点1传入node.right,这时又是null，然后这个函数出栈了，开始到节点3之前执行的函数出栈了，所以进栈的顺序是8,3,1,1的左null,出栈的顺序是1的左null，1，1的右null，3，3执行后，右边有个6，6进栈，6有4，4进栈，这个时候栈里还有8,3,,6,4
//中序遍历代码,先找左子节点，再找右子节点
var inOrderTraverceNodes = function (node,callback) {
if(node !== null){
inOrderTraverceNodes(node.left,callback);
callback(node.key);//调动callback
inOrderTraverceNodes(node.right,callback);
}
}

this.inOrderTraverce = function (callback) {
inOrderTraverceNodes(this.root,callback);
}
//前序遍历代码,先找自己，再找左子节点，再找右子节点
var preOrderTraverceNodes = function (node,callback) {
if(node !== null){
callback(node.key);//调动callback
preOrderTraverceNodes(node.left,callback);
preOrderTraverceNodes(node.right,callback);
}
}

this.preOrderTraverce = function (callback) {
preOrderTraverceNodes(this.root,callback);
}

//后序遍历代码,先找左子节点，再找右子节点，需要找完自己的左右子节点
var postOrderTraverceNodes = function (node,callback) {
if(node !== null){
postOrderTraverceNodes(node.left,callback);
postOrderTraverceNodes(node.right,callback);
callback(node.key);//调动callback
}
}

this.postOrderTraverce = function (callback) {
preOrderTraverceNodes(this.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(this.root);
}

//查找最大值，只需要查找右子节点
var maxNode = function (node) {
if(node){
while (node && node.right !== null) {
node = node.right;
}
return node.key;
}
return null;
}

this.max = function () {
return minNode(this.root);
}

//查找值x
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(this.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.left;
return node;
}else{
//例如删除的是节点3，走到这里当前节点就是节点3了，传入节点6，找到它的最小节点，返回当前节点，修改节点3的key为节点4，传入节点6和要删除的节点4，删除后重新对节点6赋值，在返回其父节点4
var aux = findMinNode(node.right);
node.key = aux.key;
node.right = removeNode(node.right,aux.key);
return node;
}
}
}

this.remove = function (key) {
removeNode(this.root,key);
}
}

var nodes = [8,3,10,1,6,14,4,7,13];
var binaryTree = new BinaryTree;
nodes.forEach((key) =>{
binaryTree.insert(key);
})
console.dir(binaryTree.root);
var callback = function (key) {
console.log(key);
}
// binaryTree.preOrderTraverce(callback);

// console.log('this is min: ' + binaryTree.min());

console.log('this is search: ' + binaryTree.search(7));
console.log('this is search: ' + binaryTree.search(9));

binaryTree.remove(1);
</script>
</html>
0赞 · 1采集
程序员熊明才 2017-10-16

//二叉树叶子节点的删除原理 function removeNode(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 }else if (node.left === null) { node = node.right; return node; }else if (node.right === null) { node = node.left; return node; } //左右两个节点删除 var aux = findMinNode(node.right); node.key = aux.key; node.right = removeNode(node.right,aux.key) return node } } this.remove = function (key) { return removeNode(root, key) } //二叉树叶子节点的删除原理 }

截图
0赞 · 0采集
花森煜米 2017-09-14

二叉排序树删除节点有两种情况，一种是删除叶子节点，一种删除普通节点（删除普通节点在不删除该节点的子节点下，要把它的子节点与它的父节点重新链接）

截图
0赞 · 0采集

数据加载中...