我有两个二叉树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
则为的子树。T1
N1 == T2
T2
T1
基本上,我不是在谈论节点地址的等价性。我说的是树的数据值和分布。
== 编辑 ==
我认为这不是真的。中可能有两个子树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