Я хочу узнать, является ли бинарное дерево T2 поддеревом двоичного дерева T1. Я прочитал, что можно было построить строковые представления для T2 и T1, используя предварительные и обходные последовательности, и если строки T2 являются подстроками строк T1, T2 является поддеревом T1.Определите, является ли двоичное дерево поддеревом другого двоичного дерева, используя строки предварительного порядка и в порядке порядка
Я немного смущен этим методом и не уверен в его правильности.
От wiki: «Поддерево дерева T - это дерево, состоящее из узла в T и всех его потомков в T.»
В следующем примере:
T2:
1
/\
2 3
T1:
1
/\
2 3
\
4
Если мы строим струны для Т2 и Т1:
предпорядок T2: "1,2,3"
предпорядок Т1: «1,2, 3,4"
T2: симметричного „2,1,3“
заказовМои T1: „2,1,3,4“
струны Т2 подстроки T1, поэтому с использованием метода согласования подстроки д выше, мы должны заключить, что T2 является поддеревом T1.
Однако T2 по определению не должен быть поддеревом T1, поскольку он не имеет всех потомков корневого узла T1.
Существует связанное обсуждение here, которое, похоже, завершает метод.
Я что-то упустил?
вы не можете повторно использовать' C' подобное, что не как теория работает , –
Я не уверен, о какой теории вы имеете в виду. Я просто заметил, что в книге нет упоминаний о деревьях, не имеющих повторяющихся значений (книга очень ясна в обозначении, когда речь идет о двоичных деревьях поиска, а не об общих двоичных деревьях .. этот случай не был двоичным деревом поиска). –
"можно было построить строковые представления для T2 и T1, используя предварительные и обходные последовательности, и если строки T2 являются подстроками строк T1, T2 является поддеревом T1." Эта теория может быть только правильной, если каждый узел имеет уникальный характер. Если вам нужно больше символов, вам также нужен метод, чтобы быть явным, о том, где начинается имя узла, например имена узлов начинаются с прописных букв, а все остальные символы строчные. –