Проверить, является ли бинарное дерево является поддеревом другого дерева


Я делаю повторительный курс по алгоритмам.
Я пытался решить проблему определения если у вас есть 2 деревьев (T1 и T2), является поддеревом другого.

Я придумал следующее:

public boolean isSubtree(Node n1, Node n2){

   if(n2 == null) //Empty Subtree is accepted   
      return true;  

   if(n1 == null)  
      return false;  


   //If roots are equal, check subtrees  
   if(n1.data == n2.data){  
       return isSubTree(n1.left, n2.left) && isSubTree(n1.right, n2.right);  
   }
   else{//No match found for this root. Check subtrees
       return isSubTree(n1.left, n2) || isSubTree(n1.right, n2);  
   }

}

Я думаю, что это правильно.
Просто чтобы прояснить Н1 - это корень дерева и Н2 корень поддерева, мы ищем.
Мне было интересно, если кто-то мог рассмотреть его, пожалуйста? Кроме того, правильность следующие проблемы меня:

Как мне рассчитать его сложность?
Также погуглив я нашел этот код, который был похож на мой, но не совсем то же самое.
Например, фрагменты кода, я нашел уже если(Н1 == null) вернуться ложным; в то время как я также проверить, если П2 не нуль.
Обоснование му заключается в том, что пустое дерево и пустое поддерево должно возвращать true.
Но либо моя логика неправильная или должности код я нашел в интернете, как правило, игнорируют это дело.

Любой входной высоко ценится



7169
8
задан 12 декабря 2011 в 05:12 Источник Поделиться
Комментарии
3 ответа

Подход является в корне ошибочным. Если вы собираетесь сделать это таким образом, вы нуждаетесь в двух методов:

public boolean equals(Node n1, Node n2) {
if (n1 == n2) return true;
if (n1 == null || n2 == null) return false;
if (n1.data != n2.data) return false; // Should use .equals if Node.data isn't primitive
return equals(n1.left, n2.left) && equals(n1.right, n2.right);
}

public boolean isSubtree(Node n1, Node n2) {
if (n2 == null) return true;
if (n1 == null) return false;
return equals(n1, n2) || isSubtree(n1.left, n2) || isSubtree(n1.right, n2);
}

Если вы беспокоитесь о сложности, вы могли бы хотеть рассмотреть, можно ли выровнять дерево в канонической (wlog) префикс-того, строку, и используйте расширенные строку алгоритме сопоставления.

5
ответ дан 14 декабря 2011 в 04:12 Источник Поделиться

Имена переменных N1 и N2-плохой выбор. Я имею в виду, вы даже пришлось уточнить, что они имели в виду свои вопросы. Как насчет просто выбирать имена, которые указывают, что они предназначены для.

А затем назначив в итоге и возвращается, что только двух операторов return.

Если вы изменить порядок двух тестов, вы можете оставить на Н2 != нулевое выражение. Потому что Л2 уже проверено, вы знаете его не null. Я думаю, вы найдете это приносит свой код в соответствие с другими отрывками, которые вы нашли.

Кроме того, я думаю, что ваш алгоритм получает несколько случаев неправильно:

    0           0
/ \ / \
1 2 3 2
/ \
3 4

Я считаю, что это будет считаться совпадающими по вашему алгоритму. Однако, это не так. (В зависимости от вашего определения поддерева)

    0           0
/ \ / \
0 2 3 4
/ \
3 4

Я считаю, что это не будет считаться матч по вашему алгоритму. Он явно есть.

Редактировать

Я думаю, тебе сейчас хватает в этом случае:

    0            1
/ \ /
1 2 3
/
3

3
ответ дан 12 декабря 2011 в 05:12 Источник Поделиться

Быстрая оптимизация будет проверить свои размеры, прежде чем вы даже начинаете сравнивать узлов значения; если дерево больше, чем дерево, Б, В obvisouly не может быть поддерева B, и в этих случаях вы можете вернуть ответ в постоянное время.

Это конечно требует, чтобы ваши деревья в поле, которое отслеживает, сколько узлов вы добавили к ним, что может оказаться полезным также для многих других приложений.

1
ответ дан 3 мая 2012 в 10:05 Источник Поделиться