[游戏开发]二叉树搜索树的插入、删除、查找【迭代法】

//二叉树节点

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

}

//树
class Tree {
    root = null
    count = null

    find(data, isDeleteFind = false) { // 删除的查找 isDeleteFind
        let curTempNode = this.root
        let parentNode = null //父节点
        let curIsLeftNode = false //当前节点是否是父节点的左节点
        while (curTempNode) {
            if (curTempNode.data > data) {
                parentNode = curTempNode
                curTempNode = curTempNode.left
                curIsLeftNode = true
            } else if (curTempNode.data < data) {
                parentNode = curTempNode
                curTempNode = curTempNode.right
            } else {
                return isDeleteFind ? {
                    parentNode,
                    curTempNode,
                    curIsLeftNode
                } : curTempNode
            }
        }
        return false

    }

    insert(data) {
        let newNode = new Node(data)
        if (this.root === null) {
            this.root = newNode
            this.count++
            return true
        }
        let curTempNode = this.root
        let parentNode = null
        while (curTempNode) {
            parentNode = curTempNode
            if (curTempNode.data > data) {
                curTempNode = curTempNode.left
                if (!curTempNode) {
                    parentNode.left = newNode
                    this.count++
                    return true
                }
            } else if (curTempNode.data < data) {
                curTempNode = curTempNode.right
                if (!curTempNode) {
                    parentNode.right = newNode
                    this.count++
                    return true
                }
            } else { //相等的时候直接return
                return false
            }

        }
    }

    delete(data) {
        let {
            parentNode,
            curTempNode,
            curIsLeftNode
        } = this.find(data, true)

        if (!curTempNode) return false;
        this.count--
        if (!curTempNode.right && !curTempNode.left) {
            if (curIsLeftNode) {
                parentNode.left = null
            } else {
                parentNode.right = null

            }
        } else if (curTempNode.right && curTempNode.left) {
            let minLeftNode = curTempNode.right;
            let leftNode = curTempNode.left;
            let tempCurrent = minLeftNode
            while (minLeftNode) {
                tempCurrent = minLeftNode
                minLeftNode = minLeftNode.left;
            }
            tempCurrent.left = leftNode
            if (curIsLeftNode) {
                parentNode.left = curTempNode.right;
            } else {
                parentNode.right = curTempNode.right;
            }
            return true
        } else {
            if (curTempNode.right && !curTempNode.left) {
                if (curIsLeftNode) {
                    parentNode.left = curTempNode.right
                } else {
                    parentNode.right = curTempNode.right
                }
            } else {
                if (curIsLeftNode) {
                    parentNode.left = curTempNode.left
                } else {
                    parentNode.right = curTempNode.left
                }
            }
        }
    }
}

const tree = new Tree()
tree.insert(2)
tree.insert(1)
tree.insert(7)
tree.insert(5)
tree.insert(9)
tree.insert(6)
tree.insert(8)


tree.delete(5)
console.log(tree);