0

我有两个二叉树T1和T2，它们都是字符树，这意味着：

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。

上述说法是否属实？

树相等的定义：如果T1和T2具有完全相同的数据值和分布，则T1 == T2，否则T1 != T2（NULL树相等）。

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

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

== 编辑 ==

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

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

== 编辑 ==

使语句为假的典型示例：

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 回答