Это общий вопрос на собеседовании, такой как получение иерархического обхода бинарного дерева через предварительный заказ и прохождение бинарного дерева и т. Д.
Предзаказ + средний порядок -> сборка
Предположим, теперь есть бинарное дерево, следующим образом:
В настоящее время порядок обхода:
Предварительный заказ: gdafemhz inorder: adefghmz postorder: aefdhzmg
Теперь дайте предварительный заказ и порядок (inorder), создайте двоичное дерево или дайте в порядке (inorder) и пост-заказ (постмодер
Определение узла дерева:
Дерево класса {char val; дерево слева; дерево правое; дерево (char val, дерево слева, дерево справа) {this.val = val; this.left = слева; this.right = right;} tree () {} tree (char val) {this.val = val; this.left = null; this.right = null;}}Сделайте достижения:
Публичное статическое дерево Buildtree (char [] предварительный заказ, char [] inorder) {// предварительный заказ - это последовательность предварительного заказа // inorder - средняя последовательность if (предварительный заказ == null || Предварительный заказ. for (char i = 0; i <indorder.length; i ++) {if (inorder [i] == root.val) {indorderIndex = i;}} // левый поддерек и правая часть предварительного заказа char [] preorderleft = rays.copyofrange (предзакачивание 1, 1+inorder -inderex); 1+indorderIndex, предварительный заказ. Buildtree (предварительный заказ, inorderleft); reever rightchild = buildtree (предварительный заказ, inorderright); root.left = Leathchild; root.right = rightchild; return root;}На самом деле то же самое для создания среднего порядка + пост-заказ. Я не напишу здесь
Различные обходы
Пост-заказ
public static void postorderprint (root tree) {// Последующий обход // левый и правый корни if (root.left! = null) {postorderprint (root.left); } if (root.right! = null) {postorderprint (root.right); } System.out.print (root.val + ""); }Учитесь из одного примера, и порядок такой же, как порядок в середине. Я не буду писать это здесь
Проверка последовательности слоя
Вы можете использовать очередь очереди в очереди, чтобы сначала добавить корневой узел в очередь. Когда очередь не пуста, возьмите узел узла заголовка очереди и распечатайте значение узла узла. Если узел левый и правый дети не пусты, добавьте левых и правых детей в очередь.
public static void layerorderprint (root tree) {if (root == null) {return; } // Последовательность последовательности слоя qe.add (root); while (! qe.isempty ()) {tree node = qe.poll (); System.out.print (node.val + ""); if (node.left! = null) {qe.add (node.left); } if (node.right! = null) {qe.add (node.right); }}}Глубина и приоритет широты
На самом деле, это просто другая поговорка. Приоритет глубины-это прохождение предварительного заказа, приоритет широты-обход на заказ слоя.
public static void deepfirstprint (root tree) {// глубокий приоритет } System.out.print (root.val + ""); if (root.left! = null) {deepfirstprint (root.left); } if (root.right! = null) {deepfirstprint (root.right); }} public static void deepfirstprintnonerec (root tree) {// нерекурсирующая форма приоритета глубины } Stack <Tree> st = new Stack <Tree> (); St.Add (корень); while (! st.isempty ()) {tree node = st.pop (); System.out.print (node.val + ""); // стек возвращается и сначала сначала // Сначала добавьте правого ребенка, а затем левый ребенок if (node.right! = Null) {st.aldd (node.right); } if (node.left! = null) {st. st.add (node.left); }}}Основная функция:
public static void main (string [] args) {char [] preorder = "gdafemhz" .tochararray (); char [] inorder = "adefghmz" .tochararray (); Root tree = main.buildtree (предварительный заказ, inorder); // main.postorderprint (root); // Postorder Traversal // main.layerorderprint (root); // последовательность слоя Traversal // main.deepfirstprint (root); // глубокий приоритет обход // main.deepfirstprintnonerec (root); // нерекурсивная версия первого обхода глубины}Суммировать
Вышеуказанное посвящено установлению бинарных деревьев и различных кодов экземпляров в Java. Я надеюсь, что это будет полезно для всех. Заинтересованные друзья могут продолжать ссылаться на этот сайт:
« Введение в два метода зеркалирования в бинарных деревьях Java » »
« Язык Java описывает глубину и ширину бинарного дерева »
Двоичный путь и пример кода Java
Если есть какие -либо недостатки, пожалуйста, оставьте сообщение, чтобы указать это. Спасибо, друзья, за вашу поддержку на этом сайте!