1. 编程号首页

排序二叉树_二叉树各种计算公式总结

编程小号 • • 未分类

排序二叉树_二叉树各种计算公式总结定义一棵空树，或者是具有下列性质的二叉树即排序二叉树（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）左、右子树

排序二叉树_二叉树各种计算公式总结"

定义

一棵空树，或者是具有下列性质的二叉树即排序二叉树

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

（4）没有键值相等的结点。

所以我们先定义一个节点类：

class Node{
    constructor(key){
        this.key = key;
        this.left = null;
        this.right = null;
    }
}

Node类拥有三个属性，键值，左孩子，右孩子。

现在我们来二叉树类，该类的属性root为树的根节点

class BinaryTree{
    constructor(){
        this.root = null;
    }
}

 现在，我们按照定义来构建排序二叉树，插入节点，根据定义，先定义root节点，当新的节点小于当前节点、并且当前节点没有左子树时，新节点为当前节点的左子树。如果该节点已经有了子节点，那么将当前节点的左孩子作为当前节点再次比较，直到没有左子树将新节点插入。右节点同理。

    //插入
    insert = (key)=>{
        let newNode = new Node(key);
        if(this.root === null){
            this.root = newNode;
        }else{
            this._insertNode(this.root,newNode);
        }
    }

    //插入节点
    _insertNode = (node,newNode)=>{
        if(newNode.key<node.key){
            if(node.left === null){
                node.left = newNode;
            }else{
                this._insertNode(node.left,newNode);
            }
        }else{
            if(node.right === null){
                node.right = newNode;
            }else{
                this._insertNode(node.right,newNode);
            }
        }
    }

节点构建完成之后我们需要遍历该二叉树。二叉树的遍历分为中序遍历、前序遍历、后序遍历。前中后的名称是由遍历根节点的位置决定的。

中序遍历：即可以实现树的值从小到大高效率排序，先遍历左子树，再遍历根节点，最后遍历右子树


    //中序遍历,二叉树数据从小到大打印出来
    inOrderTraverse=(callback)=>{
        this._inOrderTraverseNode(this.root,callback);
    }

    //中序遍历节点
    _inOrderTraverseNode=(node,callback)=>{
        if(node !== null){
            this._inOrderTraverseNode(node.left,callback);
            callback(node.key);
            this._inOrderTraverseNode(node.right,callback);
        }
    }

前序遍历：按照根左右的顺序遍历二叉树，可以实现高效率赋值二叉树

    //前序遍历，以便复制一份二叉树（比从新构造二叉树时间效率要高很多）
    preOrderTraverse=(callback)=>{
        this._preOrderTraverseNode(this.root,callback);
    }
    //前序遍历节点
    _preOrderTraverseNode = (node,callback)=>{
        if(node !== null){
            callback(node.key);
            this._preOrderTraverseNode(node.left,callback);
            this._preOrderTraverseNode(node.right,callback);
        }
    }

后续遍历：按照左右根的顺序遍历二叉树，比如文件系统和操作系统的访问

    //后续遍历，操作系统和文件系统的文件访问
    postOrderTraverse = (callback)=>{
        this._postOrderTraverseNode(this.root,callback);
    }
    //后续遍历节点
    _postOrderTraverseNode = (node,callback)=>{
        if(node !== null){
            this._postOrderTraverseNode(node.left,callback);
            this._postOrderTraverseNode(node.right,callback);
            callback(node.key);
        }
    }

查找节点：

若根结点的关键字值等于查找的关键字，成功。

否则，若小于根结点的关键字值，递归查左子树。

若大于根结点的关键字值，递归查右子树。

若子树为空，查找不成功。

平均情况分析（在成功查找两种的情况下）

查找最小值：

    //查找最小节点
    min = ()=>{
        return this._minNode(this.root);
    }
    //查找最小节点
    _minNode=(node)=>{
        if(node.left === null){
            return node.key;
        }else{
            return this._minNode(node.left);
        }
    }
    //不用递归实现
    // _minNode=(node)=>{
    //     if(node){
    //         while(node && node.left !== null){
    //             node = node.left;
    //         }
    //         return node.key;
    //     }
    //     return null;
    // }

查找最大值：

    //查找最大值
    max=()=>{
        return this._max(this.root);
    }
    //查找最大节点
    _max=(node)=>{
        if(node.right === null){
            return node.key;
        }else{
            return this._max(node.right);
        }
    }
    //不用递归实现
    // _max=()=>{
    //     if(node){
    //         while(node && node.right !== null){
    //             node = node.right;
    //         }
    //         return node.key;
    //     }
    //     return null;
    // }

查找值：

    //查找值
    search = (value)=>{
        return this._searchNode(this.root,value);
    }
    //查找节点
    _searchNode = (node,value)=>{
        if(node.key === value){
            return node;
        }else if(value < node.key){ 
            if(node.left){
                return this._searchNode(node.left,value);
            }else{
                return null;
            }
        }else if(value > node.key){
            if(node.right){
                return this._searchNode(node.right,value);
            }else{
                return null;
            }
        }
    }

最后一个是删除节点，删除节点有点复杂分为三种情况

  1. 若*p结点为叶子结点，即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构，则可以直接删除此子结点。

  2. 若*p结点只有左子树PL或右子树PR，此时只要令PL或PR直接成为其双亲结点*f的左子树（当*p是左子树）或右子树（当*p是右子树）即可，作此修改也不破坏二叉排序树的特性。

  3. 若*p结点的左子树和右子树均不空。在删去*p之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整，需要将要删除的节点的右子树中的最小值赋值给当前节点的值，然后删除右子树中的最小节点。这样排序二叉树就可以保持左孩子值小于根节点的值小于右孩子的值。

    //查找最小节点
    findMinNode = (node)=>{
        if(node.left === null){
            return node;
        }else{
            return this.findMinNode(node.left);
        }
    }
    //删除值
    remove = (value)=>{
        this._removeNode(this.root,value);
    }
    //删除节点
    _removeNode = (node,value)=>{
        //删除的是叶子节点
        if(node.key === value){
            if(node.left === null && node.right === null){
                node = null;
                return node;
            }
            //如果要删除的节点只有右子树没有左子树
            if(node.left === null){
                node = node.right;
                return node;
            }
            //如果要删除的节点只有左子树没有右子树
            if(node.right === null){
                node = node.left;
                return node;
            }

            //如果被删除的节点有左右子树
            let rightMinNode = this.findMinNode(node.right);
            node.key = rightMinNode.key;
            node.right = this._removeNode(node.right,rightMinNode.key);
            return node;

        }else if(value < node.key){
            if(node.left){
                node.left = this._removeNode(node.left,value);
                return node;
            }else{
                return null;
            }
        }else if(value > node.key){
            if(node.right){
                node.right = this._removeNode(node.right,value);
                return node;
            }else{
                return null;
            }
        }
    }

完整代码以及测试用例：

class Node{
    constructor(key){
        this.key = key;
        this.left = null;
        this.right = null;
    }
}

class BinaryTree{
    constructor(){
        this.root = null;
    }

    //插入
    insert = (key)=>{
        let newNode = new Node(key);
        if(this.root === null){
            this.root = newNode;
        }else{
            this._insertNode(this.root,newNode);
        }
    }

    //插入节点
    _insertNode = (node,newNode)=>{
        if(newNode.key<node.key){
            if(node.left === null){
                node.left = newNode;
            }else{
                this._insertNode(node.left,newNode);
            }
        }else{
            if(node.right === null){
                node.right = newNode;
            }else{
                this._insertNode(node.right,newNode);
            }
        }
    }

    //中序遍历,二叉树数据从小到大打印出来
    inOrderTraverse=(callback)=>{
        this._inOrderTraverseNode(this.root,callback);
    }

    //中序遍历节点
    _inOrderTraverseNode=(node,callback)=>{
        if(node !== null){
            this._inOrderTraverseNode(node.left,callback);
            callback(node.key);
            this._inOrderTraverseNode(node.right,callback);
        }
    }

    //前序遍历，以便复制一份二叉树（比从新构造二叉树时间效率要高很多）
    preOrderTraverse=(callback)=>{
        this._preOrderTraverseNode(this.root,callback);
    }
    //前序遍历节点
    _preOrderTraverseNode = (node,callback)=>{
        if(node !== null){
            callback(node.key);
            this._preOrderTraverseNode(node.left,callback);
            this._preOrderTraverseNode(node.right,callback);
        }
    }

    //后续遍历，操作系统和文件系统的文件访问
    postOrderTraverse = (callback)=>{
        this._postOrderTraverseNode(this.root,callback);
    }
    //后续遍历节点
    _postOrderTraverseNode = (node,callback)=>{
        if(node !== null){
            this._postOrderTraverseNode(node.left,callback);
            this._postOrderTraverseNode(node.right,callback);
            callback(node.key);
        }
    }

    //查找最小节点
    min = ()=>{
        return this._minNode(this.root);
    }
    //查找最小节点
    _minNode=(node)=>{
        if(node.left === null){
            return node.key;
        }else{
            return this._minNode(node.left);
        }
    }
    //不用递归实现
    // _minNode=(node)=>{
    //     if(node){
    //         while(node && node.left !== null){
    //             node = node.left;
    //         }
    //         return node.key;
    //     }
    //     return null;
    // }



    //查找最大值
    max=()=>{
        return this._max(this.root);
    }
    //查找最大节点
    _max=(node)=>{
        if(node.right === null){
            return node.key;
        }else{
            return this._max(node.right);
        }
    }
    //不用递归实现
    // _max=()=>{
    //     if(node){
    //         while(node && node.right !== null){
    //             node = node.right;
    //         }
    //         return node.key;
    //     }
    //     return null;
    // }

    //查找值
    search = (value)=>{
        return this._searchNode(this.root,value);
    }
    //查找节点
    _searchNode = (node,value)=>{
        if(node.key === value){
            return node;
        }else if(value < node.key){ 
            if(node.left){
                return this._searchNode(node.left,value);
            }else{
                return null;
            }
        }else if(value > node.key){
            if(node.right){
                return this._searchNode(node.right,value);
            }else{
                return null;
            }
        }
    }

    //查找最小节点
    findMinNode = (node)=>{
        if(node.left === null){
            return node;
        }else{
            return this.findMinNode(node.left);
        }
    }
    //删除值
    remove = (value)=>{
        this._removeNode(this.root,value);
    }
    //删除节点
    _removeNode = (node,value)=>{
        //删除的是叶子节点
        if(node.key === value){
            if(node.left === null && node.right === null){
                node = null;
                return node;
            }
            //如果要删除的节点只有右子树没有左子树
            if(node.left === null){
                node = node.right;
                return node;
            }
            //如果要删除的节点只有左子树没有右子树
            if(node.right === null){
                node = node.left;
                return node;
            }

            //如果被删除的节点有左右子树
            let rightMinNode = this.findMinNode(node.right);
            node.key = rightMinNode.key;
            node.right = this._removeNode(node.right,rightMinNode.key);
            return node;

        }else if(value < node.key){
            if(node.left){
                node.left = this._removeNode(node.left,value);
                return node;
            }else{
                return null;
            }
        }else if(value > node.key){
            if(node.right){
                node.right = this._removeNode(node.right,value);
                return node;
            }else{
                return null;
            }
        }
    }
}


let nodes = [8,3,10,1,6,14,4,7,13];
let binaryTree = new BinaryTree();
nodes.forEach(item=>{
    binaryTree.insert(item);
})
console.log(binaryTree);
// binaryTree.inOrderTraverse((key)=>{
//     console.log(key);//1,3,4,6,7,8,10,13,14
// })
// binaryTree.preOrderTraverse((key)=>{
//     console.log(key);//8,3,1,6,4,7,10,14,13
// })
// binaryTree.postOrderTraverse((key)=>{
//     console.log(key);//1,4,7,6,3,13,14,10,8
// })
//console.log(binaryTree.min(),'min');//1
// console.log(binaryTree.max(),'max');//14
// console.log(binaryTree.search(14)); 
/*
    key: 14
    left: Node {key: 13, left: null, right: null}
    right: null
    */

console.log(binaryTree.remove(3));
binaryTree.inOrderTraverse((key)=>{
    console.log(key);//1,4,6,7,8,10,13,14
})

 

今天的文章排序二叉树_二叉树各种计算公式总结分享到此就结束了，感谢您的阅读。

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/77042.html

赞 (0)
编程小号编程小号
0

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注