一尘不染

使用预定义和有序字符串确定二叉树是否是另一个二叉树的子树

algorithm

我想找出二叉树T2是否是二叉树T1的子树。我读到
可以使用预遍历和有序遍历为T2和T1构建字符串表示形式,并且如果T2字符串是T1字符串的子字符串,则T2是T1的子树。

我对该方法有些困惑,不确定其正确性。

摘自Wiki:“树T的子树是由T中的一个节点和T中的所有后代组成的树。”

在以下示例中:

T2:
  1
 / \
2   3

T1:
  1
 / \
2   3
     \
      4

如果我们为T2和T1构建字符串:

预购商品T2:“ 1,2,3”
预购商品T1:“ 1,2,3,4”在
订购商品T2:“ 2,1,3
”在订购商品T1:“ 2,1,3,4”

T2字符串是T1的子字符串,因此使用上述子字符串匹配方法,我们应该得出T2是T1的子树的结论。

但是,根据定义,T2不应是T1的子树,因为它没有T1根节点的所有后代。

有一个相关的讨论在这里,这似乎结束方法是正确的。

我在这里想念什么吗?


阅读 214

收藏
2020-07-28

共1个答案

一尘不染

非常有趣的问题。你似乎是对的。我想您提到的问题是由于数学(图形论)和计算机科学中子树的定义不同而引起的。在图论中,T2是T1的适当子树。

2020-07-28