2014-10-09 1 views
1

我有簡單的代碼打印路徑到樹中的特定節點。用java字符串我的FPGA實現是如下Java通過值和遞歸

//using strings 
public static void getPathS(Node node,String path,int key){ 
    if (node == null) { 
     return; 
    } else if(node.data == key) { 
     System.out.println(path+" "+key);; 
    } 

    getPathS(node.left,path+" "+node.data,key); 
    getPathS(node.right,path+" "+node.data,key); 
} 

假設有樹下面給,

enter image description here

如果我呼籲3的getPaths,上面的實現將打印

1 34 3 //path from root to the element 

如果我用下面的ArrayList實現相同的方法

public static List getPath(Node node, List<Integer> path, int key) { 
    if (node == null) { 
     //1 . path = new ArrayList<Integer>(); 
     path = new ArrayList<Integer>(); 
     // 2. or tried path.clear() -- it should clear the path 
     //return path; 
     return null; 
    } else if (node.data == key) { 
     path.add(node.data); 
     return path; 
    } 

    path.add(node.data); 
    return nonNull(getPath(node.left, path, key), getPath(node.right, path, key)); 
} 

private List nonNull(List path1, List path2) { 
    if (path1 != null) 
     return path1; 
    if(path2 !=null) 
     return path2; 
    return null; 
} 

// class Node { Node left, Node right , int data; }; 
//Code to call getPath 
Node node = new Node(1); 
node.left = new Node(2); 
node.left.left = new Node(4); 
node.right = new Node(34); 
node.right.right = new Node(3); 
System.out.println(getPath(node, new ArrayList(), 3)); 

在第二實現中,我嘗試了兩種方法,當我們得到空節點,在第一次的方法,如果我給你新ArrayList到路徑,它打印的所有元素,即

[1, 2, 4, 34, 3] 

如果我使用path.clear(),只有它打印最後一個元素,即要搜索的元素。

我們如何確保ArrayList在遞歸中以String方式工作?

+0

什麼是'nonNull(arg1,arg2)'? – Joffrey 2014-10-09 08:13:21

+0

請檢查更新代碼 – Pradeep 2014-10-09 08:17:05

+0

好的謝謝。請張貼第一次調用'getPath()'的代碼。這裏的問題是,你想添加/刪除元素到我猜的同一個列表。你需要使用某種回溯。我會在幾分鐘內拿出一些東西。 – Joffrey 2014-10-09 08:19:30

回答

2

這裏的問題是,你不認爲你的電話nonNull()與兩個分支失敗。 這是一個修正,考慮到這種可能性,並且如果我們未能在其子節點中找到該鍵,則刪除當前節點的數據。

public static List<Integer> getPath(Node node, List<Integer> path, int key) { 
    if (node == null) { 
     return null; 
    } else if (node.data == key) { 
     path.add(node.data); 
     return path; 
    } 
    path.add(node.data); 

    // path is unchanged if nothing is found in left children 
    if (getPath(node.left, path, key) != null || getPath(node.right, path, key) != null) { 
     // found in one branch or the other 
     return path; 
    } 

    // not found in either branch, remove our data 
    path.remove(path.size() - 1); 
    return null; 
} 

當然,它看起來像我們操縱不同的名單,但只能有一個:作爲參數提供的第一次一個。這就是爲什麼數據應該從中刪除。你需要清楚你的論點。


一個更乾淨的解決方案,強調只有一個列表的事實。

/** 
* Appends to the specified list all keys from {@code node} to the {@link Node} containing the 
* specified {@code key}. If the key is not found in the specified node's children, the list is 
* guaranteed to be unchanged. If the key is found among the children, then the specified list 
* will contain the new elements (in addition to the old ones). 
* 
* @param node 
*   the node to start at 
* @param path 
*   the current path to append data to 
* @param key 
*   the key to stop at 
* @return true if the key was found among the specified node's children, false otherwise 
*/ 
public static boolean getPath(Node node, List<Integer> path, int key) { 
    if (node == null) { 
     // leaf reached, and the key was not found 
     return false; 
    } 

    // add data to the path 
    path.add(node.data); 

    // the OR is lazy here, so we treat everything in the given order 
    // if getPath failed on the left children, path is unchanged and used for right children 
    if (node.data == key || getPath(node.left, path, key) || getPath(node.right, path, key)) { 
     // the key is found in the current node, its left children, or its right children 
     return true; 
    } 

    // not found in either branch, remove our data 
    path.remove(path.size() - 1); 
    return false; 
} 

請注意,我沒有使用path.remove(node.data),因爲有可能是與該數據更是一個節點,第一個將被刪除,而不是最後一次。

+1

實際上我想出了一個更好的解決方案(更簡潔),我會在一分鐘後發佈 – Joffrey 2014-10-09 08:37:59