在 BST 中查找节点位置并将其递归添加到树中

Question

所以我有 3 种方法 1 使用 traverseAdd 方法将节点添加到二叉树，另一种方法根据其父节点查找值在树中的放置位置。我想消除 traverseAdd 方法并在 add 方法中使用 findLocation 方法将新值添加到 BST。

 public void add(int val) {
            /*Adds a new node to the binary tree after traversing the tree and figuring out where it belongs*/
            Node nodeObjToAdd = new Node(val);

            if(root == null){
            //if node root is not null root = new node value
                root = nodeObjToAdd;
            }

            Node nodeTraversed = root;

            traverseAdd(nodeTraversed, nodeObjToAdd);
        }
    private void traverseAdd(Node node, Node nodeObjToAdd){
        /*Traverses tree and finds a place to add the node to be added by comparing values of the left child and right child of the
        * focus node*/
            if(nodeObjToAdd.value < node.value){
                if(node.leftChild == null){
                    node.leftChild = nodeObjToAdd;
                }
                else {
                    //if the val < the root.value set int he constructor
                    traverseAdd(node.leftChild, nodeObjToAdd);
                }
            }
            else if(nodeObjToAdd.value > node.value) {
                if (node.rightChild == null) {
                    node.rightChild = nodeObjToAdd;
                } else {
                    traverseAdd(node.rightChild, nodeObjToAdd);
                }
            }
        }
    public Node findNodeLocation(Node rootNode, int val) {
        /*returns where a the Node after which the value would be added.*/
            if(val < rootNode.value && rootNode.leftChild != null){
                return rootNode.leftChild;
            }
            if(val >= rootNode.value && rootNode.rightChild != null){
                return rootNode.rightChild;
            }
            else
                return this.root;

        }

Answer 1

public void add(int val) {
    if (root == null) {
        root = new Node(val);
    }
    Node cur = root;
    Node next = null;
    while (true) {
        next = findNodeLocation(cur, val);
        if (next != cur) {
            cur = next;         
        } else {
            break;
        }
    }
    if (val < cur.value) {
        cur.leftChild = new Node(val);
    } else {
        cur.rightChild = new Node(val);
    }
}

我认为这应该可行

在 BST 中查找节点位置并将其递归添加到树中

finding a node location within a BST and adding it to the tree recursively

java

recursion

binary-search-tree

nodes