java宽首树

Question

我似乎在构建广度优先的树时遇到了问题

在下面的代码中，我有一个通过另一个类中的循环插入的节点

树的结构应该是这样的：

    A
   / \
  B   C
 /\   /\
D E  F  G

现在来看看代码：

我的代码正确地构造了左侧，而右侧也添加了左侧。我知道在代码中的什么地方会发生这种情况，但是有没有办法防止这种情况发生

public Node familyTree;

public void breadthFirst(Node newNode){
    familyTree = breadthFirst(familyTree,newNode);

}

public Node breadthFirst(Node T, Node newNode){
    if(T == null){
        T = newNode;
        return T;            
    }
    if(T.left == null){
        newNode.height = T.height + 1;            
        T.left = newNode;
        return T;
    }
    else if(T.right == null){
        newNode.height = T.height + 1;    
        T.right = newNode;
        return T;
    }
    else{            
         T.left = breadthFirst(T.left, newNode);
         T.right = breadthFirst(T.right, newNode); <-- this is the corporate           
    }
    return T;

}

Answer 1

我认为 breadth-first tree类似于complete binary tree，所以可以使用Array来存储它，而不是链接列表。大约complete binary tree如果父数是n，那么left number=2*n+1 right=2*n+2.

---

例如：使用数组nodes[the amount of node] 而0th Node是(number begin zero) 当节点的n个数even类似于C（n=2）时，则节点[（n-2）/2]。右=nth node else odd 像B那么节点[（n-1）/2]。左=nth node

Answer 2

您缺少的是使用左右节点的高度来确定到达else语句时新节点应该是哪一侧的子节点。目前，无论节点应放置在何处，都会将其添加到两侧

另一方面，看起来您可能在高度属性中跟踪树的深度，而不是高度。这篇stackoverflow帖子很好地解释了这种差异

Answer 3

如果您使用的是递归，那么实现肯定是“深度优先搜索”，对于广度优先搜索，则使用队列或FIFO数据结构

伪代码

public Node breadthFirst(Node T, Node searchNode){
  Queue queue = new Queue();
  queue.queue(T);

  while (!queue.isEmpty()) {
    Node curNode = queue.dequeue();
    if (curNode == null) continue;

    if (curNode.value().equals(searchNode.value()) {
      return curNode;
    }

    queue.queue(curNode.left);
    queue.queue(curNode.right);
  } 

  return null; //or throw exception not found
}