Поворот бинарного дерева java

Reverse A Binary Tree (Left to Right) [closed]

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

I was looking at interview questions and I recently came upon one that asked you how to reverse a general binary tree, like flip it from right to left. So for example if we had the binary tree

You can see that the new tree is the mirror image of the original tree. I haven’t been able to think of a good implementation on how to solve this problem. Can anyone offer any good ideas?

6 Answers 6

You can use recursion. We swap the left and right child of a node, in-place, and then do the same for its children:

static void reverseTree(final TreeNode root) < final TreeNode temp = root.right; root.right = root.left; root.left = temp; if (root.left != null) < reverseTree(root.left); >if (root.right != null) < reverseTree(root.right); >> 

To handle the case where the parameter root may be null:

static void reverseTree(final TreeNode root) < if (root == null) < return; >final TreeNode temp = root.right; root.right = root.left; root.left = temp; reverseTree(root.left); reverseTree(root.right); > 

Reverse a binary tree in O(1) in C/C++.

struct NormalNode < int value; struct NormalNode *left; struct NormalNode *right; >; struct ReversedNode < int value; struct ReversedNode *right; struct ReversedNode *left; >; struct ReversedNode *reverseTree(struct NormalNode *root)

There are a couple interesting parts to this question. First, since your language is Java, you’re most likely to have a generic Node class, something like this:

class Node < private final T data; private final Node left; private final Node right; public Node(final T data, final Node left, final Node right) < this.data = data; this.left = left; this.right = right; >. > 

Secondly, reversing, sometimes called inverting, can be done either by mutating the left and right fields of the node, or by creating a new node just like the original but with its left and right children «reversed.» The former approach is shown in another answer, while the second approach is shown here:

class Node  < // See fields and constructor above. public Nodereverse() < NodenewLeftSubtree = right == null ? null : right.reverse(); Node newRightSubtree = left == null ? null : left.reverse(); return Node(data, newLeftSubtree, newRightSubtree); > > 

The idea of not mutating a data structure is one of the ideas behind persistent data structures, which are pretty interesting.

The swapping is done when constructing a new Node: i.e. that’s why the right comes before the left. It is not clear because the constructor has not been given.

Good call, @amnn and thanks for the initial edit. Java’s lack of named arguments is a bit of a bummer, being able to say new Node(data=data, left=right?.reverse(), right=left?.reverse()) would be awesome but Java is not there yet. We could also do new Node().withData(data).withLeft(right.reverse. ).withRight(left.reverse. ) etc. I ended up just making the reverse method a little more readable by using named local variables.

You can recursively swap the left and right nodes as below;

// helper method private static void reverseTree(TreeNode root) < reverseTreeNode(root); >private static void reverseTreeNode(TreeNode node) < TreeNodetemp = node.left; node.left = node.right; node.right = temp; if(node.left != null) reverseTreeNode(node.left); if(node.right != null) reverseTreeNode(node.right); > 

Demonstration Code for Java

import java.util.LinkedList; import java.util.Queue; public class InvertBinaryTreeDemo < public static void main(String[] args) < // root node TreeNoderoot = new TreeNode<>(6); // children of root root.left = new TreeNode(3); root.right = new TreeNode(4); // grand left children of root root.left.left = new TreeNode(7); root.left.right = new TreeNode(3); // grand right childrend of root root.right.left = new TreeNode(8); root.right.right = new TreeNode(1); System.out.println("Before invert"); traverseTree(root); reverseTree(root); System.out.println("\nAfter invert"); traverseTree(root); > // helper method private static void reverseTree(TreeNode root) < reverseTreeNode(root); >private static void reverseTreeNode(TreeNode node) < TreeNodetemp = node.left; node.left = node.right; node.right = temp; if(node.left != null) reverseTreeNode(node.left); if(node.right != null) reverseTreeNode(node.right); > // helper method for traverse private static void traverseTree(TreeNode root) < QueueleftChildren = new LinkedList<>(); Queue rightChildren = new LinkedList<>(); traverseTreeNode(root, leftChildren, rightChildren); System.out.println("Tree;\n*****"); System.out.printf("%3d\n", root.value); int count = 0; int div = 0; while(!(leftChildren.isEmpty() && rightChildren.isEmpty())) < System.out.printf("%3d\t%3d\t", leftChildren.poll(), rightChildren.poll()); count += 2; div++; if( (double)count == (Math.pow(2, div))) < System.out.println(); count = 0; >> System.out.println(); > private static void traverseTreeNode(TreeNode node, Queue leftChildren, Queue rightChildren) < if(node.left != null) leftChildren.offer(node.left.value); if(node.right != null) rightChildren.offer(node.right.value); if(node.left != null) < traverseTreeNode(node.left, leftChildren, rightChildren); >if(node.right != null) < traverseTreeNode(node.right, leftChildren, rightChildren); >> private static class TreeNode> < protected E value; protected TreeNodeleft; protected TreeNode right; public TreeNode(E value) < this.value = value; this.left = null; this.right = null; >> > 

Output

Before invert Tree; ***** 6 3 4 7 3 8 1 After invert Tree; ***** 6 4 3 1 8 3 7 

Источник

Руководство по деревьям AVL на Java

В этом уроке мы представим дерево AVL и рассмотрим алгоритмы вставки, удаления и поиска значений.

2. Что Такое Дерево AVL?

Дерево AVL, названное в честь его изобретателей Адельсона-Вельского и Ландиса, представляет собой самобалансирующееся бинарное дерево поиска (BST).

Самобалансирующееся дерево-это двоичное дерево поиска, которое балансирует высоту после вставки и удаления в соответствии с некоторыми правилами балансировки.

Наихудшая временная сложность BST является функцией высоты дерева. В частности, самый длинный путь от корня дерева до узла. Для BST с N узлами предположим, что каждый узел имеет только ноль или один дочерний элемент. Поэтому его высота равна N, а время поиска в худшем случае равно O(N). Таким образом, наша главная цель в BST-сохранить максимальную высоту близко к log(N).

Коэффициент баланса узла N равен height(right(N)) – height(left(N)) . В дереве AVL коэффициент баланса узла может быть только одним из значений 1, 0 или -1.

Давайте определим объект Node для нашего дерева:

Далее давайте определим дерево AVL :

public class AVLTree < private Node root; void updateHeight(Node n) < n.height = 1 + Math.max(height(n.left), height(n.right)); >int height(Node n) < return n == null ? -1 : n.height; >int getBalance(Node n) < return (n == null) ? 0 : height(n.right) - height(n.left); >. >

3. Как сбалансировать дерево AVL?

Дерево AVL проверяет коэффициент баланса своих узлов после вставки или удаления узла. Если коэффициент баланса узла больше единицы или меньше -1, дерево восстанавливает баланс.

Существует две операции для перебалансировки дерева:

3.1. Поворот вправо

Давайте начнем с правильного вращения.

У нас есть BST called T1, с корневым узлом, X как левый ребенок У, и Z как правый ребенок X. Given the characteristics of BST, мы знаем, что X < Z < Y.

После правого поворота у нас есть дерево, названное T2 с X как корень и как правый ребенок X и Z как левый ребенок Y. T2 все еще BST, потому что он держит порядок X < Z < Y.

Давайте рассмотрим правильную операцию вращения для нашего дерева AVL :

3.2. Операция Поворота Влево

У нас также есть операция поворота влево.

Предположим, что BST называется T1, с Y в качестве корневого узла, X в качестве правого дочернего элемента Y и Z в качестве левого дочернего элемента X. Учитывая это, мы знаем, что Y < Z < X.

После левого поворота Y у нас есть дерево под названием T2 с X в качестве корня и Y в качестве левого потомка X и Z в качестве правого потомка Y. T2 все еще является BST, потому что он сохраняет порядок Y < Z < X.

Давайте взглянем на операцию поворота влево для нашего дерева AVL :

3.3. Методы восстановления баланса

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

Когда коэффициент баланса узла Z равен 2, поддерево с Z в качестве корня находится в одном из этих двух состояний, считая Y правым дочерним элементом Z.

В первом случае высота правого дочернего элемента Y (X) больше высоты левого дочернего элемента (T2). Мы можем легко сбалансировать дерево, повернув его влево на Z.

Во втором случае высота правого дочернего элемента Y (T4) меньше высоты левого дочернего элемента (X). В этой ситуации требуется комбинация операций ротации.

В этом случае мы сначала поворачиваем Y вправо, чтобы дерево приняло ту же форму, что и в предыдущем случае. Затем мы можем перебалансировать дерево, повернув его влево на Z.

Кроме того, когда коэффициент баланса узла Z равен -2, его поддерево находится в одном из этих двух состояний, поэтому мы рассматриваем Z как корень, а Y-как его левый дочерний элемент.

Высота в левом дочернем элементе Y больше, чем у его правого дочернего элемента, поэтому мы уравновешиваем дерево правым поворотом Z.

Или во втором случае правый потомок Y имеет больший рост, чем его левый потомок.

Итак, прежде всего, мы преобразуем его в прежнюю форму с левым поворотом Y, затем уравновешиваем дерево с правым поворотом Z.

Давайте взглянем на операцию перебалансировки для нашего дерева AVL :

Node rebalance(Node z) < updateHeight(z); int balance = getBalance(z); if (balance >1) < if (height(z.right.right) >height(z.right.left)) < z = rotateLeft(z); >else < z.right = rotateRight(z.right); z = rotateLeft(z); >> else if (balance < -1) < if (height(z.left.left) >height(z.left.right)) z = rotateRight(z); else < z.left = rotateLeft(z.left); z = rotateRight(z); >> return z; >

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

4. Вставьте узел

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

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

После вставки узла у нас есть BST, но это может быть не дерево AVL. Поэтому мы проверяем коэффициенты баланса и перебалансируем BST для всех узлов на пути от нового узла к корню.

Давайте взглянем на операцию вставки:

Node insert(Node node, int key) < if (node == null) < return new Node(key); >else if (node.key > key) < node.left = insert(node.left, key); >else if (node.key < key) < node.right = insert(node.right, key); >else < throw new RuntimeException("duplicate Key!"); >return rebalance(node); >

Важно помнить, что ключ уникален в дереве — нет двух узлов, имеющих один и тот же ключ.

Временная сложность алгоритма вставки зависит от высоты. Поскольку наше дерево сбалансировано, мы можем предположить, что временная сложность в худшем случае равна O(log(N)).

5. Удалите узел

Чтобы удалить ключ из дерева, мы сначала должны найти его в ЛУЧШЕМ.

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

Предположим, что правый дочерний элемент Z называется Y. Сначала мы находим крайний левый узел Y и называем его X. Затем мы устанавливаем новое значение Z равным значению X и продолжаем удалять X из Y.

Наконец, мы вызываем метод баланса в конце, чтобы сохранить ЛУЧШЕЕ дерево AVL.

Node delete(Node node, int key) < if (node == null) < return node; >else if (node.key > key) < node.left = delete(node.left, key); >else if (node.key < key) < node.right = delete(node.right, key); >else < if (node.left == null || node.right == null) < node = (node.left == null) ? node.right : node.left; >else < Node mostLeftChild = mostLeftChild(node.right); node.key = mostLeftChild.key; node.right = delete(node.right, node.key); >> if (node != null) < node = rebalance(node); >return node; >

Временная сложность алгоритма удаления зависит от высоты дерева. Аналогично методу вставки, мы можем предположить, что временная сложность в худшем случае равна O(log(N)).

6. Поиск узла

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

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

Временная сложность поиска зависит от высоты. Мы можем предположить, что временная сложность в худшем случае равна O(log(N)).

Давайте посмотрим пример кода:

Node find(int key) < Node current = root; while (current != null) < if (current.key == key) < break; >current = current.key < key ? current.right : current.left; >return current; >

7. Заключение

В этом уроке мы реализовали дерево AVL с операциями вставки, удаления и поиска.

Как всегда, вы можете найти код на Github .

Читайте ещё по теме:

Источник

Обход бинарного дерева в обратном порядке

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

Например, обратная обход порядка уровней для следующего дерева 4, 5, 6, 7, 2, 3, 1 :

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

Мы можем уменьшить временную сложность до O(n) с использованием дополнительного пространства. Ниже приведен псевдокод для простого queueобход в обратном порядке, требующий пространства, пропорционального максимальному количеству узлов на заданной глубине. Она может составлять до половины от общего количества узлов.

levelorder(root)

q —> empty queue
s —> empty stack
q.enqueue(root)
while (not q.isEmpty())
node —> q.dequeue()
s.push(node)
if (node.right <> null)
q.enqueue(node.right)
if (node.left <> null)
q.enqueue(node.left)

while (not s.isEmpty())
node —> s.pop()
print(node)

Алгоритм может быть реализован следующим образом на C++, Java и Python:

Источник