将节点插入树广度优先

Question

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

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

生成的树应该是

          10
    8           20

5      29    50

等等...

此解决方案无效，我不太确定原因。我认为可能是我的 generateList 没有正常工作，但我已经检查了最后打印的列表，它似乎是正确的。

是否有更好的方法来执行此操作，或者我的代码中是否存在我找不到的问题。非常感谢任何帮助。

这是我的树节点Class:

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;
            }
        }
    }




}

将节点插入树广度优先

Inserting nodes into a tree Breadth First

java

tree

breadth-first-search