我想找出二叉树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根节点的所有后代。
有一个相关的讨论在这里,这似乎结束方法是正确的。
我在这里想念什么吗?
非常有趣的问题。你似乎是对的。我想您提到的问题是由于数学(图形论)和计算机科学中子树的定义不同而引起的。在图论中,T2是T1的适当子树。