найти поддерево из двоичного дерева

Question

См. Ниже двоичное дерево. И видеть реализацию этого здесь: алгоритме 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.

Дайте мне предложить для любого кода или алгоритма или функции, которые должны быть Решимость Эта проблема?

Answer 1

Предполагая, класс Node определяется как:

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; 
} 

Testing это с помощью дерева в вашем ответе:

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