從二叉樹中找到子樹

查看下面的二叉樹。而看到實施這一算法中在這裏：http://msdn.microsoft.com/en-us/library/ms379572(v=vs.80).aspx 從二叉樹中找到子樹

     1       level 0 
       2    3     level 1 
      4 5 6 7  level 2 
     8  9 10 11 12 13 14 15   level 3

我的問題是：我如何發現樹從這棵樹基於水平？假設我想從15個編號的節點中發現兩個已分級的子樹。那麼結果應該是

  3 
     6  7 
12  13  14  15

如果我搜索3剷平樹，那麼它應該返回上面我所描述滿樹從1到15

給我提出的任何代碼或算法或函數應該是決心這個問題？

來源

2011-12-27 Hiren Visavadiya

你指的是BST，還是隻是一個二叉樹？無論哪種方式，它都應該很容易。真正的問題是：如何找到節點的第N個父節點？該節點是您正在查找的子樹。你會如何找到節點的直接父節點？ – Kobi

我指的是BST。但是哪個遍歷方法對於找到這個第N個父節點非常有用。或者你有任何算法？ –

沒有人能在上面給出的庫中添加一個函數來滿足我的要求嗎？ –

假設節點類定義爲：

public class Node 
{ 
    public Node Left { get; set; } 
    public Node Right { get; set; } 
    public int Value { get; set; } 

    public Node(int value) 
    { 
     Value = value; 
    } 
}

您可以在以下兩種方法添加到這個類來實現你想要做什麼：

public Node GetSubtree(int value, int depth) 
{ 
    int foundDepth; 
    return GetSubtreeHelper(value, depth, out foundDepth); 
} 

private Node GetSubtreeHelper(int value, int depth, out int foundDepth) 
{ 
    if (Value == value) 
    { 
     foundDepth = 0; 
     return depth == foundDepth ? this : null; 
    } 
    if (Left != null) 
    { 
     var node = Left.GetSubtreeHelper(value, depth, out foundDepth); 
     if (foundDepth != -1) 
     { 
      return ++foundDepth == depth ? this : node; 
     } 
    } 
    if (Right != null) 
    { 
     var node = Right.GetSubtreeHelper(value, depth, out foundDepth); 
     if (foundDepth != -1) 
     { 
      return ++foundDepth == depth ? this : node; 
     } 
    } 
    foundDepth = -1; 
    return null; 
}

測試此使用樹在你的問題：

GetSubtree(15, 0) = Node 15 
GetSubtree(15, 1) = Node 7 
GetSubtree(15, 2) = Node 3 
GetSubtree(15, 3) = Node 1 
GetSubtree(15, 4) = null

來源

2011-12-27 17:41:47 Iridium

hi Indium，非常感謝。讓我使用問題中給出的BST算法實現來測試此代碼。 –

您示例中的樹不是BST，所以我的代碼被設計爲適用於一般二叉樹。搜索階段可以優化，如果這是爲了僅用於BST。 – Iridium

感謝您的回覆。我閱讀了一些BST的博客和書籍，我認爲你是對的。但你能給我一些解決方案，將在上面給出的示例（http://msdn.microsoft.com/en-us/library/ms379572(v=vs.80).aspx）中適合。非常感謝。或者，您建議我在BST中插入您的給定代碼的某個鏈接。 –

從二叉樹中找到子樹

回答

相關問題