java—在不能使用递归的地方编写红黑树程序插入

roejwanj 于 2021-07-07 发布在 Java

关注(0)|答案(2)|浏览(281)

这个程序以递归方式工作，但是，我尝试在不必更改方法参数的情况下不以递归方式工作。谢谢，任何事都会有帮助的！

private Node insertTree(Node root, Node node) { //root and node is current vs. next

        if (root == null) { 
            return node;  

        }

        if(node.getCurrentNum() < root.getCurrentNum()) { //Means it is a left child
            root.setLeftChild(insertTree(root.getLeftChild(), node)); //RECURSIVE MUST FIX
            root.getLeftChild().setParent(root); 
        }

        else if(node.getCurrentNum() >root.getCurrentNum()) { //Means it is a right child
            root.setRightChild(insertTree(root.getRightChild(), node)); //RECURSIVE MUST FIX
            root.getRightChild().setParent(root); 
        }

        return root;

    }

}

Java iteration recursion

来源：https://stackoverflow.com/questions/65098372/writing-a-red-black-tree-program-insertion-where-we-cant-use-recursion

2条答案

按热度按时间

lbsnaicq1#

最后这是我得到的感谢安德烈亚斯。

private Node insertTree(Node root, Node newNode) {
        if (root == null) {
            root = newNode;
            newNode.setParent(null);
        }

        Node parent = root;

        while (newNode.getCurrentNum() != parent.getCurrentNum()) {
            if (newNode.getCurrentNum() < parent.getCurrentNum()) {
                if (parent.getLeftChild() == null) {
                    parent.setLeftChild(newNode);
                    newNode.setParent(parent);
                }
                parent = parent.getLeftChild();
            } else if (newNode.getCurrentNum() > parent.getCurrentNum()) {
                if (parent.getRightChild() == null) {
                    parent.setRightChild(newNode);
                    newNode.setParent(parent);

                }
                parent = parent.getRightChild();
            }
        }

        return root;
    }

赞(0）回复(0）举报 2021-07-07

lokaqttq2#

因为你只跟着其中一个 leftChild 或 rightChild ，决不能两者同时存在 Node ，您不需要回溯，因此可以轻松地使用循环来实现这一点。

private void insertTree(Node newNode) {
    if (this.root == null) {
        this.root = newNode;
        newNode.setParent(null);
        return;
    }
    Node parent = this.root;
    while (newNode.getCurrentNum() != parent.getCurrentNum()) {
        if (newNode.getCurrentNum() < parent.getCurrentNum()) {
            if (parent.getLeftChild() == null) {
                parent.setLeftChild(newNode);
                newNode.setParent(parent);
                return;
            }
            parent = parent.getLeftChild();
        } else if (newNode.getCurrentNum() > parent.getCurrentNum()) {
            if (parent.getRightChild() == null) {
                parent.setRightChild(newNode);
                newNode.setParent(parent);
                return;
            }
            parent = parent.getRightChild();
        }
    }
}

赞(0）回复(0）举报 2021-07-07

我来回答

java—在不能使用递归的地方编写红黑树程序插入

2条答案

相关问题

热门标签

最新问答