JavaScript数据结构——树

文章目录 二叉树二叉搜索树insert()树的遍历中序先序后序 最小节点最大节点搜索指定值
一个树结构含有父子关系的节点，除了根节点外，每一个节点都一个父节点和0个或者多个子节点。如下图：

根节点也是可以有多个子节点的。

二叉树

二叉树中的节点最多只能有两个子节点，左侧节点和右侧节点。

二叉搜索树

左侧节点存储的值必须比父节点小，右侧节点存储的值必须比父节点大。

现在以二叉树为例，分析一下节点的信息，节点包含了存储值、指向左右两个子节点的left和right属性。如图：

root是根节点，存储值为4，含有左右两个节点。

声明一个Node类来表示节点信息：

class Node {
    constructor(key) {
        this.key = key; // 节点值
        this.left = null; //左侧节点引用
        this.right = null; // 右侧节点引用
    }
}

声明一个方法来比较节点值，判断元素存储到左侧节点还是右侧节点。

const Compare = {
    LESS_THAN: -1,
    BIGGER_THAN: 1,
    EQUALS: 0
};

function defaultCompare(a, b) {
    if (a === b) {
        return Compare.EQUALS;
    }
    return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

声明树的框架：

class BinarySearchTree {
    constructor(compareFn = defaultCompare) {
        this.compareFn = compareFn;
        this.root = null; //根节点
    }
    insertNode(node, key) {
        
    }
    insert(key) {
       
    }
    search(key) {}

    // 通过中序遍历所有节点
    inOrderTraverse() {}

    // 通过后序遍历所有节点
    postOrderTraverse() {}

    min() {}
    max() {}
    remove(key) {}
}

insert()

将节点添加到根节点之下，并且是插入正确位置。先判断根节点是否为空，若是，那么该节点为树的根节点；反之，该节点作为子节点插入树中。

那么作为子节点，如何插入正确位置呢？这就是insertNode方法的作用了：

    insertNode(node, key) {
        // 当前节点key和父节点key比较，当前key小于父节点的key，那么该节点放在父节点的左侧
        if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
            if (node.left == null) {
                node.left = new Node(key);
            } else {
                this.insertNode(node.left, key)
            }
        } else if (node.right == null) {
            node.right = new Node(key);
        } else {
            this.insertNode(node.right, key)
        }
    }

这里面用到递归，当前节点已经拥有左侧节点了，那么就需要继续查找到树的下一层比较。如下图：

现在需要添加一个节点，key为7：

7<32，节点归到左侧节点，找到树的下一层比较；
7<12，节点归到左侧节点，找到树的下一层作比较；
7<11，节点归到则侧节点，这一层的节点，也就是key为11的节点，它的左侧子节点为null，那么当前需要添加的新节点作为该节点的左侧子节点。如下图：

树的遍历

访问树上所有节点的方式：中序、先序和后序

中序

从最小到最大的顺序访问所有几点。

    // 通过中序遍历所有节点
    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)
        }
    }

调用：

tree.inOrderTraverse((value)=>{
    console.log("遍历树",value)
})

最后的访问排序：

先序

以优先于后代节点的顺序访问所有节点：先访本身，然后访问左侧节点，最后访问右侧节点。

    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)
        }
    }

访问：

tree.preOrderTraverse((value)=>{
    console.log("先序遍历",value)
})

最后访问：

后序

先访问节点的后代节点，在访问节点本身：

    // 后序遍历
    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)
        }
    }

调用：

tree.postOrderTraverse((value) => {
    console.log("后序遍历", value)
})

最小节点

在二叉树中，最小节点只能存在左侧节点：

    min() {
        return this.minNode(this.root)
    }
    minNode(node){
        let current = node;
        while(current != null && current.left !=null){
            current = current.left
        }

        return current
    }

console.log("最小节点",tree.min()); // 最小节点 Node { key: 7, left: null, right: null }

最大节点

最大节点存储在右侧节点：

    max() {
        return this.maxNode(this.root)
    }
    maxNode(node){
        let current = node;
        while(current != null && current.right !=null){
            current = current.right
        }

        return current 
    }

console.log("最大节点",tree.max()); // 最大节点 Node { key: 37, left: null, right: null }

搜索指定值

    search(key) {
        return this.searchNode(this.root,key);
    }
    searchNode(node,key){
        if(node==null) return false;
        if(this.compareFn(key,node.key)===Compare.LESS_THAN){
            return this.searchNode(node.left,key)
        }else if(this.compareFn(key,node.key)===Compare.BIGGER_THAN){
            return this.searchNode(node.right,key);
        }else{
            return true
        }
    }

完整代码：

/**
 * 树：分层数据的抽象模型
 */
const Compare = {
    LESS_THAN: -1,
    BIGGER_THAN: 1,
    EQUALS: 0
};

function defaultCompare(a, b) {
    if (a === b) {
        return Compare.EQUALS;
    }
    return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
class Node {
    constructor(key) {
        this.key = key; // 节点值
        this.left = null; //左侧节点引用
        this.right = null; // 右侧节点引用
    }
}


class BinarySearchTree {
    constructor(compareFn = defaultCompare) {
        this.compareFn = compareFn;
        this.root = null; //根节点
    }
    insertNode(node, key) {
        // 当前节点key和父节点key比较，当前key小于父节点的key，那么该节点放在父节点的左侧
        if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
            if (node.left == null) {
                node.left = new Node(key);
            } else {
                this.insertNode(node.left, key)
            }
        } else if (node.right == null) {
            node.right = new Node(key);
        } else {
            this.insertNode(node.right, key)
        }
    }
    insert(key) {
        if (this.root == null) {
            this.root = new Node(key)
        } else {
            this.insertNode(this.root, key)
        }
    }
    search(key) {
        return this.searchNode(this.root, key);
    }
    searchNode(node, key) {
        if (node == null) return false;
        if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
            return this.searchNode(node.left, key)
        } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
            return this.searchNode(node.right, key);
        } else {
            return true
        }
    }

    // 通过中序遍历所有节点
    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) {
        let current = node;
        while (current != null && current.left != null) {
            current = current.left
        }

        return current
    }
    max() {
        return this.maxNode(this.root)
    }
    maxNode(node) {
        let current = node;
        while (current != null && current.right != null) {
            current = current.right
        }

        return current
    }
    remove(key) {
        return this.removeNode(this.root, key)
    }
    removeNode(node, key) {
        if (node == null) return null;
        if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
            node.left = this.removeNode(node.left, key);
            return node;
        } else if (this.compareFn(key, node.right) === Compare.BIGGER_THAN) {
            node.right = this.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;
            }

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

            const aux = this.minNode(node.right)
            node.key = aux.key;
            node.right = this.removeNode(node.right,aux.key);
            return node;
        }
    }
}


const tree = new BinarySearchTree();

tree.insert(32);
tree.insert(12);
tree.insert(11);
tree.insert(23);
tree.insert(7);
tree.insert(36);
tree.insert(32);
tree.insert(37);


console.log("树", tree)
console.log('\n')
tree.inOrderTraverse((value) => {
    console.log("中序遍历树", value)
})
console.log('\n')
tree.preOrderTraverse((value) => {
    console.log("先序遍历", value)
})

console.log('\n')
tree.postOrderTraverse((value) => {
    console.log("后序遍历", value)
})
console.log('\n')
console.log("最小节点", tree.min())

console.log('\n')
console.log("最大节点", tree.max())
console.log('\n')
console.log("搜索", tree.search(11))
console.log('\n')
console.log("删除", tree.remove(7))```