Поскольку другие, похоже, не согласны со мной в том, что этот вопрос не по теме, теперь я решаю, что он относится к теме, и предоставляю и отвечаю.упорядочить n пар скобок "(второй пункт в этой ссылке .) Часть путаницы заключается в том, что порядок строк в скобках не соответствует порядку двоичного дерева, которое вы понимаетеили со многими другими примерами.
Вот способ преобразования строки n пар скобок, которые правильно сопоставлены, в двоичное дерево с n внутренними узлами.Рассмотрим крайнюю левую скобку, которая будет левой скобкой, вместе с соответствующей ей правой скобкой.Преврати строку в узел двоичного дерева.Подстрока, которая является внутри рассматриваемых в настоящее время скобок, становится левым дочерним элементом этого узла, а подстрока, которая составляет после (справа) от рассматриваемой в настоящее время скобкиправая скобка становится правильным ребенком.Любая или обе подстроки могут быть пустыми, и рассматриваемые в настоящее время скобки просто удаляются.Если какая-либо подстрока не пуста, продолжайте эту процедуру рекурсивно, пока все скобки не будут удалены.
Вот два примера.Начнем со строки ((())).Мы начинаем с
Рассмотренные скобки являются самыми внешними.Это становится
(я не удосужился нарисовать внешние листовые узлы), затем
затем
, которое является самым левым двоичным деревом Википедии с 3 внутренними узлами.
Теперь давайте сделаемдругая строка, (())().Мы начинаем с
Опять же, рассматриваемые скобки являются самыми внешними.Это преобразуется в
И теперь рассматриваемые скобки - это первые два, а не внешние.Это становится
, которое в итоге становится
, которое являетсявторое двоичное дерево в списке Википедии.
Надеюсь, теперь вы понимаете.Вот список всех пяти возможных строк из 3 пар круглых скобок, которые правильно спарены, за которыми следует список двоичных деревьев Википедии.Эти списки теперь соответствуют друг другу.
((())) (()()) (())() ()(()) ()()()
