原生JavaScript实现排序二叉树

in 前端技术 with 0 comment

C1ewZ9.md.jpg

part.1 排序二叉树定义

二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:
(1)若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值;
(2)若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;
(3)左、右子树也分别为二叉排序树;

part.2 实现思路

part.3 代码实现

    var arr = [14, 25, 45, 16, 58, 42, 26, 31, 21, 42, 51];
    
    //排序二叉树构造方法
    function BinaryTree() {
        //定义根节点属性
        var root = null;
        //定义节点
        var Node = function(key) {
            this.key = key; //数值
            this.left = null; //左孩子
            this.right = 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 bt = new BinaryTree();
    //遍历数组,将数组中的数值插入排序二叉树
    arr.forEach(function(key) {
        bt.insert(key);
    });
Responses