在二叉搜索樹中查找K個最大的元素

我想在BST中找到K個最大的元素，但是我的代碼流沒有正確地發生。例如，考慮BST如下在二叉搜索樹中查找K個最大的元素

我的代碼流在16秩序發生 - > 12 - > 9，但我想擁有它16 - > 12 - > 11

代碼如下

public class FindKLargestElements { 


private static int n =0; 

public static int[] findLarge(Node node, int large[], int k) { 

    if (node == null) return large; 

    if (k == 0) return large; 

    findLarge(node.getRightNode(), large, k); 

    if (k >0) { 
     large[n] = node.getValue(); 
     k = k -1; 
     n = n +1; 
     return large; 

    } 

    findLarge(node.getLeftNode(), large, k); 

    return large; 

} 

}

我現在已經解決了這個問題。這是最終的代碼。

這是我做過什麼

移除了如果k> 0塊

改變了原始k以一流的水平，而不是遞歸方法級別更新到它是迷路return語句。

public class FindKLargestElements { 


private static int n =0; 
private static int k =3; 

public static int[] findLarge(Node node, int large[]) { 

    if (node == null) return large; 

    if (k == 0) return large; 

    findLarge(node.getRightNode(), large); 

    if (k >0) { 
     large[n] = node.getValue(); 
     k = k -1; 
     n = n +1; 

    } 

    findLarge(node.getLeftNode(), large); 

    return large; 

}

}

來源

2014-05-08 Manish

所描繪的樹無效，「10」不可能在左邊。 – Ingo

請嘗試以下程序

public class FindKLargestElements { 

private static int n =0; 
private static int large[]; 

public static void findLarge(Node node, int k) { 

    if (node == null) return; 
    if (k == 0) return; 

    findLarge(node.getRightNode(), k); 

    if (k >0) { 
     large[n] = node.getValue(); 
     k = k-1; 
     n = n+1; 

    } 

    findLarge(node.getLeftNode(), k); 

} 

}

來源

2014-05-08 09:42:59

它沒有任何區別 – Manish

基本上我已經評論了程序中的if（k> 0）塊的返回語句，以便在返回之前發生左節點遍歷。所以它應該工作 if（k> 0）{[n] = node.getValue（）; k = k-n-1; n = n +1; // return large; } –

我會建議得到k個最大二叉搜索樹的元素的非常不同，但方式更加簡單，有效的方法。

1.使用序遍歷從最後一個元素開始得到在列表或陣列

function inorder(node) { 
     if (node == null) 
     return; 
     inorder(node.left); 
     visit(node); 
     inorder(node.right); 
}

2.進入最後K元素排序的元素。

use for loop or while

來源

2014-05-08 11:02:33 AurA

的另一種方法是創建給定的BST的反射鏡和先做K個元素的序遍歷。那些將是最大的k個元素。這種方法的缺點是您正在浪費時間來創建鏡像樹，但您稍後獲得的優勢是您不必在以後遍歷整個n個元素。由於k可能與n一樣大，在最壞的情況下，我們仍然必須遍歷BST中的每個元素。所以簡單地做一個原始BST的inorder遍歷和在inorder遍歷中返回最後的k個元素應該是一個更簡單的選擇。

來源

2014-09-27 13:21:27 psbits

在二叉搜索樹中查找K個最大的元素

回答

相關問題