N-арные деревья - это симметрично или нет

Question

Учитывая N-арное дерево, выясните, симметрично ли оно относительно линии, проведенной через корневой узел дерева. Это легко сделать в случае двоичного дерева. Однако для N-арных деревьев это кажется трудным

Answer 1

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

1. Отражение пустого дерева само по себе.
2. Отражение дерева с корнем r и дочерних элементов c1, c2, ..., cn - это дерево с корнем r, а дочерние элементы отражают (cn), ..., отражают (c2), отражают (c1).

Затем вы можете решить эту проблему, вычислив отражение дерева и проверив, равно ли оно исходному дереву. Это снова может быть сделано рекурсивно:

1. Пустое дерево равно только себе.
2. Дерево с корнем r и дочерними элементами c1, c2, ..., cn равно другому дереву, если другое дерево непустое, имеет корень r, имеет n дочерних элементов и имеет дочерние элементы, равные c1,. .., сп в этом порядке.

Конечно, это немного неэффективно, потому что перед сравнением создается полная копия дерева. Использование памяти составляет O (n + d), где n - количество узлов в дереве (для хранения копии), а d - высота дерева (для хранения кадров стека в проверке рекурсии на равенство). Так как d = O (n), это использует O (n) памяти. Однако он выполняется за время O (n), поскольку каждая фаза посещает каждый узел ровно один раз.

Более эффективный способ сделать это - использовать следующую рекурсивную формулировку:

1. The empty tree is symmetric.
2. A tree with n children is symmetric if the first and last children are mirrors, the second and penultimate children are mirrors, etc.

Затем вы можете определить два дерева, которые будут зеркалами, следующим образом:

1. Пустое дерево - только зеркало самого себя.
2. Дерево с корнем r и дочерними элементами c1, c2, ..., cn является зеркалом дерева с корнем t и дочерними элементами d1, d2, ..., dn, если r = t, c1 является зеркалом dn с2 - зеркало дн-1 и т. д.

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

Answer 2

Я просто сделал бы обход дерева по порядку (узел слева направо) в левом поддереве и сохранил его в список. Затем выполните другой обход дерева по порядку (узел справа налево) в правом поддереве и сохраните его в списке. Затем вы можете просто сравнить два списка. Они должны быть одинаковыми.

Answer 3

Возьми стек Теперь каждый раз начинайте обход через корневой узел, теперь рекурсивно вызываем функцию и нажимаем элемент левого поддерева один за другим на определенном уровне. поддерживать глобальную переменную и обновлять ее значение каждый раз, когда левое поддерево помещается в stack.now, рекурсивно вызывает (после рекурсивного вызова в левое поддерево) правый подпункт и выскакивает в каждом правильном match.doing, что гарантирует проверено симметрично.

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

Answer 4

Это не сложно. Я собираюсь играть в гольф с этим вопросом. Я получил 7 ... кто-нибудь поправился?

data Tree = Tree [Tree]
symmetrical (Tree ts) =
    (even n || symmetrical (ts !! m)) &&
    all mirror (zip (take m ts) (reverse $ drop (n - m) ts))
    where { n = length ts; m = n `div` 2 }
mirror (Tree xs, Tree ys) =
    length xs == length ys && all mirror (zip xs (reverse ys))