寬度優先樹

我似乎在構建寬度優先樹時遇到問題。寬度優先樹

在下面的代碼中，我有一個節點通過另一個類中的循環插入。

樹的結構應該是像這樣：

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

回答

相關問題