сравнить узлы двоичного дерева

Question

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

Любые идеи о том, как решить эту проблему?

Answer 1

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

Answer 2

вы можете использовать что-то вроде Tree Traversal для проверки каждого значения.

Answer 3

Если деревья двоичные поиск деревьев, так что предварительная прогулка даст надежное, повторяемое упорядочение предметов, существующие ответы будут работать. Если они являются произвольными бинарными деревьями, у вас есть гораздо более интересная проблема, и вы должны посмотреть на hash tables.

Answer 4

Имеет ли порядок узлов? Я предполагаю, что для этого ответа, что следующие два дерева:

1  1 
/\ /\ 
3 2 2 3 

не равен, потому что положение узла и порядок учитываются для сравнения.

Несколько советов

• Согласны ли вы, что две пустые деревья равны?
• Согласны ли вы с тем, что два дерева, которые имеют только корневой узел с одинаковыми значениями узлов, равны?
• Разве вы не можете обобщить этот подход?

Будучи немного более точным

Рассмотрим общую дерево:

 rootnode(value=V) 
     / \ 
     /  \ 
     -------- ------- 
    | left | | right | 
    | subtree| |subtree| 
     -------- ------- 

RootNode является один узел. Двое детей более общие и представляют собой двоичные деревья. Дети могут быть пустыми, или единым узлом, или полностью выращенным бинарным деревом.

Вы согласны с тем, что это представление является достаточно общим для представления любого типа непустого двоичного дерева? Можете ли вы разложить, скажем, this simple tree в мое представление?

Если вы понимаете эту концепцию, то это разложение поможет вам решить проблему. Если вы понимаете концепцию, но не можете идти дальше с алгоритмом, прокомментируйте здесь, и я буду немного более конкретным :)

Answer 5

Моим решением было бы сгладить два дерева на 2 массива (используя порядок уровня), а затем перебирать каждый элемент и сравнивать. Вы знаете, что оба массива - это один и тот же порядок. Вы можете сделать простые предварительные проверки, например, если размеры массива отличаются, то два дерева не совпадают.

Уровень заказа довольно прост в применении, статья Википедии на tree traversal в основном дает вам все необходимое, включая код. Если в вопросе задается вопрос об эффективности, то наилучшим является нерекурсивное решение и выполняется с использованием списка FIFO (очередь на языке C# - я не программист на C).

Answer 6

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

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

Answer 7

Вы можете использовать указатели и рекурсию, чтобы проверить, равен ли узел, а затем проверить поддеревья. Код можно записать в виде языка Java.

public boolean sameTree(Node root1, Node root2){ 
//base case :both are empty 
if(root1==null && root2==null) 
    return true; 

if(root1.equals(root2)) { 
    //subtrees 
    boolean left=sameTree(root1.left,root2.left); 
    boolean right=sameTree(root1.right,root2.right); 
    return (left && right); 
}//end if 
else{ 
    return false; 
}//end else 

} // конец sameTree()

Answer 8

Написание кода C как тег упоминает в этом вопросе.

int is_same(node* T1,node* T2) 
{ 
    if(!T1 && !T2) 
    return 1; 
    if(!T1 || !T2) 
    return 0; 

    if(T1->data == T2->data) 
    { 
     int left = is_same(T1->left,T2->left); 
     int right = is_same(T1->right,T2->right); 
     return (left && right); 
    } 
    else 
    return 0; 
} 

Учитывает структуру, а также значения.

Answer 9

Один код линии достаточно, чтобы проверить, равны ли два узла двоичного дерева (одинаковое значение и одна и та же структура) или нет.