java - 广度优先向树中插入节点

Question

我正在尝试生成具有广度优先插入形式的树。我尝试通过生成一个列表来做到这一点，其中树中的所有元素均按广度优先顺序排列。然后在我的 insertNode 方法中，我使用名为 needChildren() 的方法检查该节点是否需要子节点，如果需要，我将要插入到树中的节点添加到最左边的位置。

如果我打电话插入节点(10)插入节点(8)插入节点(20)插入节点(5)插入节点(29)插入节点(50)

生成的树应该是

          10
    8           20

5      29    50

等等...

这个解决方案不起作用，我不太清楚为什么。我认为我的generateList可能无法正常工作，但我检查了最后打印的列表，它似乎是正确的。

有没有更好的方法来做到这一点，或者我的代码中是否存在我找不到的问题。非常感谢任何帮助。

这是我的 TreeNode 类:

private static class TreeNode<T> {

    public T data;
    public TreeNode<T> left;
    public TreeNode<T> right;

    public TreeNode(T d) {
                    data = d;
                    left = null;
                    right = null;
    }
}

我的insertNode方法:

public void insertNode(T d) { 

    if(root==null){
        root= new TreeNode<T>(d);             
    }

    genList(root);

    if(needsChildren(nodesThatNeedChildren.get(0))){
        if(nodesThatNeedChildren.get(0).left==null){
            nodesThatNeedChildren.get(0).left= new TreeNode<T>(d);
        }else{
            nodesThatNeedChildren.get(0).right= new TreeNode<T>(d);
        }
    }else{
        while(!needsChildren(nodesThatNeedChildren.get(0))){
            nodesThatNeedChildren.remove(0);

        }
        System.out.println(nodesThatNeedChildren.get(0).data);


        if(nodesThatNeedChildren.get(0).left==null){
            nodesThatNeedChildren.get(0).left = new TreeNode<T>(d);
        }else{
            nodesThatNeedChildren.get(0).right = new TreeNode<T>(d);
        }
    }


}

我检查节点是否需要子节点的方法:

public boolean needsChildren(TreeNode<T> node){
    if(node.left==null || node.right ==null){
        return true;
    }
    return false;
}

我的方法生成树中所有节点的列表:

public void genList(TreeNode<T> root) {
    //generate new List each time
    nodesThatNeedChildren.clear();
    nodesThatNeedChildren.add(root);

    //generate new Queue each time genList is called
    tempQueue.clear();
    tempQueue.add(root);

    while(!tempQueue.isEmpty()){

        TreeNode<T> node = tempQueue.remove(0);

        if(node.left != null){ 
            tempQueue.add(node.left);
            nodesThatNeedChildren.add(node.left);
        }     

        if(node.right != null){
            tempQueue.add(node.right);
            nodesThatNeedChildren.add(node.right);
        }
    }
}

Answer 1

经过一番调试，我发现了我的错误。这个问题出在我的 insertNode() 方法中。

我正在生成第一个节点，我在树中插入了两次。

这是因为我打电话

if(root==null){
    root= new TreeNode<T>(d);             
}

对于第一个节点，但随后并没有突破该方法，而是调用了生成第一个节点两次的其余代码。一个简单的 else if 语句就解决了这个问题。解析后的代码如下所示。

public void insertNode(T d) { 


    if(root==null){
        root= new TreeNode<T>(d); 
        size+=1;    

    }
    else if(root!=null){
        genList(root);
        if(needsChildren(nodesThatNeedChildren.get(0))){
            if(nodesThatNeedChildren.get(0).left==null){
                nodesThatNeedChildren.get(0).left= new TreeNode<T>(d);
                size+=1;
            }else{
                nodesThatNeedChildren.get(0).right= new TreeNode<T>(d);
                size+=1;
            }
        }else{
            while(!needsChildren(nodesThatNeedChildren.get(0))){
                nodesThatNeedChildren.remove(0);

            }

            if(nodesThatNeedChildren.get(0).left==null){
                nodesThatNeedChildren.get(0).left = new TreeNode<T>(d);
                size+=1;
            }else{
                nodesThatNeedChildren.get(0).right = new TreeNode<T>(d);
                size+=1;
            }
        }
    }




}