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

Question

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

Есть идеи, как решить эту проблему?

Answer 1

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

Answer 2

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

  1       1
 / \     / \
3   2   2   3

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

Несколько подсказок

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

Будучи немного точнее

Рассмотрим это родовое дерево:

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

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

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

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

Answer 3

Вы можете использовать что-то вроде Обход дерева , чтобы проверить каждое значение.

Answer 4

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

bool isEqual(BinaryTreeNode *a, BinaryTreeNode *b)  
{  
    return (a && b) ?  (a->m_nValue==b->m_nValue && isEqual(a->m_pLeft,b->m_pLeft) && isEqual(a->m_pRight,b->m_pRight)) :  (a == b);  
}

Answer 5

Написание кода 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 6

Вы можете использовать указатели и рекурсию, чтобы проверить, равен ли узел, а затем проверить поддеревья. Код может быть написан следующим образом на языке 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 7

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

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

Answer 8

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

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

Answer 9

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