0

我有两个二叉树T1T2,它们都是字符树,这意味着:

struct TreeNode
{
    char      data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(const char d, TreeNode* const lptr = NULL,
                           TreeNode* const rptr = NULL)
        : data(d), left(lptr), right(rptr){}

};

如果PreOrder2是 的子串PreOrder1,并且InOrder2是 的子串InOrder1,则T2是 的子树T1

上述说法是否属实?

树相等的定义:如果T1T2具有完全相同的数据值和分布,则T1 == T2,否则T1 != T2(NULL树相等)。

子树的定义:如果其中至少有一个节点,N1则为的子树。T1N1 == T2T2T1

基本上,我不是在谈论节点地址的等价性。我说的是树的数据值和分布。

== 编辑 ==

我认为这不是真的。中可能有两个子树T1,其中一个T2具有与 相同的 PreOrder,另一个具有与 相同的 InOrder T2

现在我的问题变成了:有没有一种简单的方法来确定是否T2T1使用遍历的子树?

== 编辑 ==

使语句为假的典型示例:

T1:

      A
   B     C
 C         B  
D           D

T2:

  B
C   D

另一个T1:

          A
      A       A
   B     B       C
 C         D       B
D           C       D
4

1 回答 1

0

我一直在寻找一种算法来检查 T2 是否是 T1 的子树,它需要少于 O(m*n)。

经过一番搜索,我发现了这两个线程:

使用前序和中序字符串确定二叉树是否是另一棵二叉树的子树

使用前序和中序字符串检查子树

查看这些,实际上可能仅使用前序字符串和中序字符串就可以找到子树。有趣的是,他们还讨论了子树的相互矛盾的定义。

无论如何,我自己还没有测试过这个方法,但是你试试这个怎么样?:

在前序遍历和中序遍历中将树 T1 和 T2 展平为字符串(就像我们在聊天中讨论的那样),但这次也包括字符串中的每个 NULL叶子(例如作为空格),然后尝试检查子字符串.

于 2013-08-18T06:58:55.103 回答