无法显示节点的祖先总和

Question

我的问题是关于将值从数组插入到树中，然后使用inOrder遍历以升序支付这些值。我还必须在上面提到的值旁边显示每个节点的祖先总数。预期的输出是：23（135），45（90），50（135），90（0），110（90）

但是结果我只得到50（0）

这是我的代码：

class BSTNode {

    private int value;
    private int sum;
    private BSTNode left;
    private BSTNode right;

    public BSTNode(){
        value = 0;
        sum = 0;
        left = null;
        right = null;
    }

    public BSTNode(int value){  
        this.value = value;
        sum = 0;
        left = null;
        right = null;
    }

    public void setValue(int newValue){ value = newValue; }

    public int getValue(){ return value; }

    public void setSum(int sum){ this.sum = sum; }

    public int getSum(){ return sum; }

    public void setLeft(BSTNode newLeft){ left = newLeft; }

    public BSTNode getLeft(){ return left; }

    public void setRight(BSTNode newRight){ right = newRight; }

    public BSTNode getRight(){ return right; }

    public String toString() { return value + " (" + sum + ")"; }
} // end class BSTNode

public class BST {


    private BSTNode root;

    public BST(){
        root = null;
    } // end constructor

    public BSTNode getRoot(){
        return root;
    } // end getRoot

    public void addElement(int elementVal){

        int sum = 0;

        while(root != null) {
            sum += elementVal;
            if (elementVal > root.getValue()) {
                root = root.getRight();
            }
            else if(elementVal < root.getValue()) {
                root = root.getLeft();
            } else {
            root.setSum(sum-elementVal);

            }
        }


        BSTNode tmp = new BSTNode(elementVal);      
        if(root == null) { root = tmp; }
        else{           
            BSTNode parent, current;    
            parent = current = root;            
            while(current != null){ 
                parent = current;
                if(elementVal < current.getValue()) { current = current.getLeft(); }
                else { current = current.getRight(); }

            }            
            if(elementVal < parent.getValue()) { parent.setLeft(tmp); }
            else { parent.setRight(tmp); }
        }
    } // end addElement

    private String toString(BSTNode bstNode) {      
        // returns the elements of a subtree rooted as bstNode in ascending order (inorder traversal) 
        String result = "";
        if (bstNode == null) { return "";}
        result += (bstNode.getLeft() == null? "" : toString(bstNode.getLeft()) + ", ");
        result += bstNode.toString() + ", ";
        result += (bstNode.getRight() == null? "" : toString(bstNode.getRight()) + ", ");
        result = result.replaceAll(", $", "");  // removes trailing comma ", "
        return result;      
    } // end toString

    public String toString(){
        // returns the elements of the BST in ascending order (inorder traversal) 
        return toString(root);
    } 
} 

这是我的主语：

public class Main {

    public static void main(String[] args) {


        System.out.println("-- Binary Search Tree --");


        BST myBST = new  BST();
        int[] myList = {90, 45, 23, 110, 50};
        for(int value: myList){ myBST.addElement(value); }
        System.out.println(myBST);

    }
}

Answer 1

旁边显示每个节点的祖先总数。

问题是，每次添加元素时，您都在更改根本身。因此，最后50个成为树的根。

在addElement中，每当您从while(root != null)中出来时，root将为空。因此，在这种情况下，您总是以if(root == null) { root = tmp; }结尾，而永远不会以else结尾。

甚至不需要while中的第一个addElement。

如果将addElement更改为]，它将按预期工作>

public void addElement(int elementVal) {
        BSTNode tmp = new BSTNode(elementVal);
        if (root == null) {
            root = tmp;
        } else {
            BSTNode parent, current;
            parent = current = root;
            while (current != null) {
                parent = current;
                if (elementVal < current.getValue()) {
                    current = current.getLeft();
                } else {
                    current = current.getRight();
                }

            }
            tmp.setSum(parent.getSum() + parent.getValue());
            if (elementVal < parent.getValue()) {
                parent.setLeft(tmp);
            } else {
                parent.setRight(tmp);
            }
        }
    }