确定是否二叉树是使用pre-秩序和有序的字符串的另一个二叉树子树 [英] Determine if a binary tree is subtree of another binary tree using pre-order and in-order strings

问题描述

我想找出二叉树T2是否二叉树T1的子树。我读使用pre-秩序和有序遍历人们可以打造字符串重新presentations为T1和T2，如果T2字符串是T1串子，T2是T1的子树。

I want to find out whether binary tree T2 is a subtree of of binary tree T1. I read that one could build string representations for T2 and T1 using pre-order and in-order traversals, and if T2 strings are substrings of T1 strings, T2 is a subtree of T1.

我有点困惑这个方法并不能确定它的正确性。

I am a bit confused by this method and not sure about its correctness.

从维基：一树T A子树是由在T和所有的T中的后代节点的树

From wiki: "A subtree of a tree T is a tree consisting of a node in T and all of its descendants in T."

在下面的例子：

T2:
  1
 / \
2   3

T1:
  1
 / \
2   3
     \
      4

如果我们建立了T2和T1的字符串：

If we build the strings for T2 and T1:

preorder T2：1,2,3
preorder T1：1,2,3,4
序T2：2,1,3
序T1：2,1,3,4

preorder T2: "1,2,3"
preorder T1: "1,2,3,4"
inorder T2: "2,1,3"
inorder T1: "2,1,3,4"

在T2字符串是T1的子串，因此，使用上面的串匹配方法说明，我们应该得出T2是T1的子树。

The T2 strings are substrings of T1, so using the substring matching method described above, we should conclude T2 is a subtree of T1.

但是，T 2根据定义不应该T1的一个子树，因为它不具有T 1的根节点的所有后代。

However, T2 by definition shouldn't be a subtree of T1 since it doesn't have all the descendants of T1's root node.

有一个相关的讨论<一href="http://stackoverflow.com/questions/14287980/checking-subtrees-using-$p$porder-and-inorder-strings">here,这似乎得出结论：该方法是正确的。

There is a related discussion here, which seems to conclude the method is correct.

我失去了一些东西呢？

推荐答案

很有趣的问题。你似乎是正确的。我想，你提的这个问题的出现是由于树的数学（图论）和计算机科学的定义不同。在图论T2是T1适当的子树。

Very interesting question. You seem to be correct. I suppose the issue that you mention arises due to different definitions of subtree in math (graph theory) and computer science. In graph theory T2 is a proper subtree of T1.

这篇关于确定是否二叉树是使用pre-秩序和有序的字符串的另一个二叉树子树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！