深度優先搜索二進制樹/圖中的Java

Question

我一直在嘗試一段時間，以獲得這個圖僞裝成二叉樹工作。目前我正在使用一個傳入根節點的函數和我正在查找的節點的ID。唯一的問題是，根據我的編碼方式，我的一方永遠不能超過3個節點。我相信我只是沒有正確地做遞歸。我一直堅持這一整晚，並不能得到這個。我嘗試過看其他圖表和樹木，但無濟於事。我們沒有使用實際的頂點或其他圖形屬性，但我不能只使用if (x <root.getID())然後root.left，因爲它不能保留，因爲它仍然是一個「圖」

這是我的非工作搜索算法，如果我使它長到幾個節點，就停止在右側工作。訪問使用HashSet（）類。

private Node dfs(Node x, int id) 
{ 
    if (x==null) //base case. Runs into null link 
     return null; 
    if(visited.contains(x.getID())) //visited before 
     return null; 
    visited.add(x.getID()); //don't go below Node again 
    if(id==x.getID()) 
     return x; 
    Node rc = dfs(x.getRightChild(), id); 
    Node lc = dfs(x.getLeftChild(), id); 
    //recursive calls 

    if (lc.getID()==id) 
     return lc; 
    if(rc.getID()==id) 
     return rc; 
    return null; 
} 

我有一個用於打印所有樹的工作代碼，但是我無法在上面的代碼中更改它的密鑰比較。

private String dfsPrint(Node x) //pass in root at top level 
           //returns a String containing all ID's 
{ 
    if (x==null) //base case. Runs into null link 
     return ""; 
    if(visited.contains(x.getID())) //visited before 
     return ""; 
    visited.add(x.getID()); //don't go below Node again 
    String lc = dfsPrint(x.getLeftChild()); //recursive stuffs 
    String rc = dfsPrint(x.getRightChild()); 
    return Integer.toString(x.getID()) + " " + lc + rc; 
} 

謝謝你的幫助。

編輯：我想我會擴展我在做什麼。我必須有一個makeRight或makeLeft函數放入一個新的節點，然後一個現有的節點將它放在它的左邊或右邊。 這是。其中搜索是調用私有dfs的公共方法。

Node search(int id) // calls private dfsSearch() returns null or a ref to 
        // a node with ID = id 
{ 
    int ID = id; 
    Node x= dfs(root, ID); 
    return x; 
} 


void ML(int x, int y) // ML command 
{ 
visited.clear(); 
Node temp = new Node(y, null, null); 
Node current = search(x); 
current.putLeft(temp); 

} 

void MR(int x, int y)//MR command 
{ 
visited.clear(); 
Node temp = new Node(y, null, null); 
Node current = search(x); 
current.putRight(temp); 

} 

取決於如何訂購的遞歸函數如果LC和RC陳述，樹的不同側面被遞歸回升至基本情況，這是什麼讓我承擔DFS方法是什麼是錯的。這是請求的節點類。

class Node { 
private int ID; //ID of the Node. Distinct 
private Node leftChild; 
private Node rightChild; 

Node(int identification)//constructor 

{ 
    ID = identification; 
} 
Node(int identification, Node lt, Node rt) //constructor 

{ 
ID = identification; 
leftChild = lt; 
rightChild = rt; 

} 

int getID() 

{ 
    return ID; 
} 

Node getLeftChild() 
    { 
      return leftChild; 
    } 
Node getRightChild() 
{ 
    return rightChild; 
} 
void putLeft(Node lt) 
{ 
    leftChild = lt; 
} 
void putRight (Node rt) 
{ 
    rightChild = rt; 
} 

}

Answer 1

你dfs方法返回在幾種情況下空。當您嘗試致電getId()這樣的返回值時，您應該會發生異常。你不是嗎？

Answer 2

你可以簡化代碼。我不認爲你需要'身份證'。這個怎麼樣？

private dfs(Node x, int id) { 
    if (x==null) { //base case. Runs into null link 
     return; 
    } 
    if(visited.contains(x)) { //visited before 
     return; 
    } 
    visited.add(x); //don't go below Node again 
    dfs(x.getRightChild()); 
    dfs(x.getLeftChild()); 
}