高级前端之js数据结构之线二叉树（下）

水深无声 2022-11-12 01:41 160阅读 0赞

## 废话少说，上干货，二叉树数据结构实现增删改查排序等功能 ##

class Node { 
            constructor(key) { 
                this.key = key;
                this.left = null;
                this.right = null;
            }
        }
        class BinaryTree { 
            root = null;
            arr = [];
            insert(key) { 
                let node = new Node(key);
                if (this.root) { 
                    this.insertNode(this.root, node);
                } else { 
                    this.root = node;
                }
            }
            insertNode(node, newNode) { 
                if (node.key > newNode.key) { 
                    if (node.left) { 
                        this.insertNode(node.left, newNode);
                    } else { 
                        node.left = newNode;
                    }
    
                } else { 
                    if (node.right) { 
                        this.insertNode(node.right, newNode)
                    } else { 
                        node.right = newNode;
                    }
                }
            }
            callBack(node) { 
                console.log(node.key)
                this.arr.push(node);
            }
    
            // 中序遍历
            inOrderTraverse() { 
                this.inOrderTraverseNode(this.root)
            }
            inOrderTraverseNode(node) { 
                if (node !== null) { 
                    this.inOrderTraverseNode(node.left);
                    this.callBack(node);
                    this.inOrderTraverseNode(node.right);
                }
            }
    
            // 前序遍历
            preOrderTraverse() { 
                this.preOrderTraverseNode(this.root);
            }
            preOrderTraverseNode(node) { 
                if (node !== null) { 
                    this.callBack(node);
                    this.preOrderTraverseNode(node.left);
                    this.preOrderTraverseNode(node.right);
                }
            }
            // 后序遍历
            postOrderTraverse() { 
                this.postOrderTraverseNode(this.root);
            }
            postOrderTraverseNode(node) { 
                if (node !== null) { 
                    this.postOrderTraverseNode(node.left);
                    this.postOrderTraverseNode(node.right);
                    this.callBack(node)
                }
            }
            // 查找最小节点
            min() { 
                return this.minNode(this.root)
            }
            minNode(node) { 
                if (node !== null) { 
                    while (node.left) { 
                        node = node.left;
                    }
                    return node
                }
            }
            // 最大值查找
            max() { 
                return this.maxNode(this.root)
            }
            maxNode(node) { 
                while (node.right) { 
                    node = node.right
                }
                return node
            }
            // 随机节点查找
            search(key) { 
                return this.searchNode(this.root, key);
            }
            searchNode(node, key) { 
                if (node === null) { 
                    return false
                }
                if (node.key < key) { 
                    return this.searchNode(node.right, key)
                } else if (node.key > key) { 
                    return this.searchNode(node.left, key)
                } else { 
                    return true
                }
            }
            // 删除节点
            findRightMinNode(node) { 
                if (node) { 
                    while (node && node.left) { 
                        node = node.left;
                    }
                    return node
                }
                return null;
            }
            remove(key) { 
                this.removeNode(this.root, key)
            }
            removeNode(node, key) { 
                if (node === null) { 
                    return null
                }
                if (key < node.key) { 
                    node.left = this.removeNode(node.left, key);
                    return node;
                } else if (key > node.key) { 
                    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.findRightMinNode(node.right);
                    node.key = aux.key;
                    node.right = this.removeNode(node.right, aux.key);
                    return node
                }
            }
        }
        let bt = new BinaryTree();
        let arr = [3, 1, 5, 8, 0, 7, 9];
        arr.forEach((val) => { bt.insert(val) }) // console.log(bt); // bt.inOrderTraverse(); // bt.preOrderTraverse(); // bt.postOrderTraverse(); // console.log(bt.min())
        // console.log(bt.max())
        // console.log(bt.search(9))
        // bt.remove(9);
        // console.log(bt);
        // bt.inOrderTraverse();
        bt.remove(3);
        console.log(bt);
        bt.inOrderTraverse();