从二叉树中找到子树

查看下面的二叉树。而看到实施这一算法中在这里：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中插入您的给定代码的某个链接。 –

从二叉树中找到子树

回答

相关问题