宽度优先树

我似乎在构建宽度优先树时遇到问题。宽度优先树

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

树的结构应该是像这样：

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; 

}

来源

2016-11-13 1011 1110

你在递归思考。你应该反复思考。在做广度优先的时候，要与一系列“尚未评估”的节点一起工作。 – Dibbeke

您正在执行depthFirstSearch实现，如果您想执行breathFirstSearch，请使用队列。 –

试图首先建立一棵树，宽度。 –

我觉得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是A (number begin zero) 当数量的节点的n是even像C（n=2）然后节点[（ N-2）/ 2] .right = nth node 别的odd样B然后节点[（N-1）/ 2]。左= nth node

来源

2016-11-13 01:27:44

什么你缺少使用是左边和右边节点的高度，以确定到达else语句时新节点应该是哪个边的子节点。目前，您将它添加到双方，无论节点放置在哪里。

顺便说一句，它看起来像你可能跟踪高度属性树的深度，而不是高度。这stackoverflow帖子做了很好的解释差异。

来源

2016-11-13 01:28:51

，如果你使用的是递归的，绝对的实现是一个“深度优先搜索”，广度优先搜索，您可以使用一个队列或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 
}

来源

2016-11-13 02:28:33

回答

相关问题