Рубрики

Отразить бинарное дерево

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

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

Ниже приведен основной код поворота поддерева

        root->left->left = root->right;
    root->left->right = root;
    root->left = NULL;
    root->right = NULL; 

Вышеприведенный код можно понять по следующей схеме:

так как мы храним root-> left в перевернутом корне, перевернутое поддерево сохраняется в каждом рекурсивном вызове.

C ++

/ * C / C ++ программа для переворота двоичного дерева * /
#include <bits/stdc++.h>

using namespace std;

  
/ * Бинарная древовидная структура * /

struct Node

{

    int data;

    Node *left, *right;

};

  
/ * Утилита для создания нового двоичного файла

   Узел дерева * /

struct Node* newNode(int data)

{

    struct Node *temp = new struct Node;

    temp->data = data;

    temp->left = temp->right = NULL;

    return temp;

}

  
// метод для переворота двоичного дерева
Node* flipBinaryTree(Node* root)
{

    // Базовые случаи

    if (root == NULL)

        return root;

    if (root->left == NULL && root->right == NULL)

        return root;

  

    // рекурсивно вызываем тот же метод

    Node* flippedRoot = flipBinaryTree(root->left);

  

    // переставляем основной корневой узел после возврата

    // из рекурсивного вызова

    root->left->left = root->right;

    root->left->right = root;

    root->left = root->right = NULL;

  

    return flippedRoot;

}

  
// Итеративный метод для прохождения уровня порядка
// построчно

void printLevelOrder(Node *root)

{

    // Базовый вариант

    if (root == NULL)  return;

  

    // Создать пустую очередь для прохождения порядка уровней

    queue<Node *> q;

  

    // ставим в очередь Root и инициализируем высоту

    q.push(root);

  

    while (1)

    {

        // nodeCount (размер очереди) указывает число

        // узлов на текущем уровне.

        int nodeCount = q.size();

        if (nodeCount == 0)

            break;

  

        // Выводим из очереди все узлы текущего уровня и

        // ставим в очередь все узлы следующего уровня

        while (nodeCount > 0)

        {

            Node *node = q.front();

            cout << node->data << " ";

            q.pop();

            if (node->left != NULL)

                q.push(node->left);

            if (node->right != NULL)

                q.push(node->right);

            nodeCount--;

        }

        cout << endl;

    }

}

  
// Код драйвера

int main()

{

    Node* root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

    root->right->left = newNode(4);

    root->right->right = newNode(5);

  

    cout << "Level order traversal of given tree\n";

    printLevelOrder(root);

  

    root = flipBinaryTree(root);

  

    cout << "\nLevel order traversal of the flipped"

            " tree\n";

    printLevelOrder(root);

    return 0;

}

Джава

/ * Java-программа для переворота двоичного дерева * /

import java.util.Queue;

import java.util.LinkedList;

public class FlipTree {

  

    // метод для переворота двоичного дерева

    public static Node flipBinaryTree(Node root)

    {

        if (root == null

            return root; 

        if (root.left == null && root.right ==null

            return root;

  

        // рекурсивно вызываем тот же метод

        Node flippedRoot=flipBinaryTree(root.left);

  

        // переставляем основной корневой узел после возврата

        // из рекурсивного вызова

        root.left.left=root.right;

        root.left.right=root;

        root.left=root.right=null;

        return flippedRoot;

    }

  

    // Итеративный метод для прохождения уровня порядка

    // построчно

    public static void printLevelOrder(Node root)

    {

        // Базовый вариант

        if(root==null)

            return ;

          

        // Создать пустую очередь для прохождения порядка уровней

        Queue<Node> q=new LinkedList<>();

        // ставим в очередь Root и инициализируем высоту

        q.add(root);

        while(true)

        {

            // nodeCount (размер очереди) указывает число

            // узлов на текущем уровне.

            int nodeCount = q.size(); 

            if (nodeCount == 0

                break;

              

            // Выводим из очереди все узлы текущего уровня и

            // ставим в очередь все узлы следующего уровня

            while (nodeCount > 0

            

                Node node = q.remove(); 

                System.out.print(node.data+" ");

                if (node.left != null

                    q.add(node.left); 

                if (node.right != null

                    q.add(node.right); 

                nodeCount--; 

            

            System.out.println();

        }

    }

  

    public static void main(String args[]) {

        Node root=new Node(1);

        root.left=new Node(2);

        root.right=new Node(1);

        root.right.left = new Node(4); 

        root.right.right = new Node(5); 

        System.out.println("Level order traversal of given tree");

        printLevelOrder(root); 

    

        root = flipBinaryTree(root); 

        System.out.println("Level order traversal of flipped tree");

        printLevelOrder(root);

    }

}

  
/ * Бинарная древовидная структура * /

class Node 

    int data; 

    Node left, right; 

    Node(int data)

    {

        this.data=data;

    }

};
// Этот код предоставлен Гауравом Тивари

питон

# Python-программа для переворота двоичного дерева

  
# Узел двоичного дерева

class Node:

      

    # Конструктор для создания нового узла

    def __init__(self, data):

        self.data = data 

        self.right = None

        self.left = None

  

def flipBinaryTree(root):

      

    # Базовые случаи

    if root is None:

        return root 

      

    if root.left is None and root.right is None:

        return root

  

    # Рекурсивно вызвать тот же метод

    flippedRoot = flipBinaryTree(root.left)

  

    # Перестановка основного корневого узла после возврата

    # от рекурсивного вызова

    root.left.left = root.right

    root.left.right = root

    root.left = root.right = None

  

    return flippedRoot

  
# Итеративный метод для прохождения порядка уровней
# построчно

def printLevelOrder(root):

      

    # Базовый вариант

    if root is None:

        return 

      

    # Создать пустую очередь для прохождения порядка уровней

    from Queue import Queue

    q = Queue()

      

    # Ставить в корень и инициализировать высоту

    q.put(root)

      

    while(True):

  

        # nodeCount (размер очереди) указывает число

        # узлов на текущем уровне

        nodeCount = q.qsize()

        if nodeCount == 0:

            break

  

        # Отключить все узлы текущего уровня и

        # Поставить в очередь все узлы следующего уровня

        while nodeCount > 0:

            node = q.get()

            print node.data,

            if node.left is not None:

                q.put(node.left)

            if node.right is not None:

                q.put(node.right)

            nodeCount -= 1

  

        print 

  

  
# Код драйвера

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.right.left = Node(4)

root.right.right = Node(5)

  

print "Level order traversal of given tree"

printLevelOrder(root)

  

root = flipBinaryTree(root)

  

print "\nLevel order traversal of the flipped tree"

printLevelOrder(root)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

// C # программа для переворота двоичного дерева

using System;

using System.Collections.Generic; 

  

public class FlipTree 

{

  

    // метод для переворота двоичного дерева

    public static Node flipBinaryTree(Node root)

    {

        if (root == null

            return root; 

        if (root.left == null && root.right ==null

            return root;

  

        // рекурсивно вызываем тот же метод

        Node flippedRoot = flipBinaryTree(root.left);

  

        // переставляем основной корневой узел после возврата

        // из рекурсивного вызова

        root.left.left = root.right;

        root.left.right = root;

        root.left = root.right = null;

        return flippedRoot;

    }

  

    // Итеративный метод для прохождения уровня порядка

    // построчно

    public static void printLevelOrder(Node root)

    {

        // Базовый вариант

        if(root == null)

            return ;

          

        // Создать пустую очередь для прохождения порядка уровней

        Queue<Node> q = new Queue<Node>();

          

        // ставим в очередь Root и инициализируем высоту

        q.Enqueue(root);

        while(true)

        {

            // nodeCount (размер очереди) указывает число

            // узлов на текущем уровне.

            int nodeCount = q.Count; 

            if (nodeCount == 0) 

                break;

              

            // Выводим из очереди все узлы текущего уровня и

            // ставим в очередь все узлы следующего уровня

            while (nodeCount > 0) 

            

                Node node = q.Dequeue(); 

                Console.Write(node.data+" ");

                if (node.left != null

                    q.Enqueue(node.left); 

                if (node.right != null

                    q.Enqueue(node.right); 

                nodeCount--; 

            

            Console.WriteLine();

        }

    }

  

    // Код драйвера

    public static void Main(String []args) 

    {

        Node root = new Node(1);

        root.left = new Node(2);

        root.right = new Node(1);

        root.right.left = new Node(4); 

        root.right.right = new Node(5); 

        Console.WriteLine("Level order traversal of given tree");

        printLevelOrder(root); 

      

        root = flipBinaryTree(root); 

        Console.WriteLine("Level order traversal of flipped tree");

        printLevelOrder(root);

    }

}

  
/ * Бинарная древовидная структура * /

public class Node 

    public int data; 

    public Node left, right; 

    public Node(int data)

    {

        this.data = data;

    }

};

  
// Этот код предоставлен Принчи Сингхом


Выход:

Level order traversal of given tree
1 
2 3 
4 5 

Level order traversal of the flipped tree
2 
3 1 
4 5 

Итеративный подход
Этот подход предоставлен Pal13 .
Итеративное решение следует тому же подходу, что и рекурсивное, единственное, на что мы должны обратить внимание, это сохранить информацию об узле, которая будет перезаписана.

C ++

// C / C ++ программа для переворота двоичного дерева
#include <bits/stdc++.h>

using namespace std;

  
// Бинарная древовидная структура

struct Node

{

    int data;

    Node *left, *right;

};

  
// Служебная функция для создания нового двоичного файла
// Tree Node

struct Node* newNode(int data)

{

    struct Node *temp = new struct Node;

    temp->data = data;

    temp->left = temp->right = NULL;

    return temp;

}

  
// метод для переворота двоичного дерева
Node* flipBinaryTree(Node* root)
{

    // Инициализация указателей

    Node *curr = root;

    Node *next = NULL;

    Node *temp = NULL;

    Node *prev = NULL;

      

    // Итерация по всем левым узлам

    while(curr) 

    {

        next = curr->left;

          

        // Теперь нужно поменять местами узлы, нужно, чтобы temp оставил предыдущего правого потомка

          

        // Делаем правее prev как левый ребенок curr

        curr->left = temp;         

          

        // Сохранение правого потомка курсора

        temp = curr->right;         

          

        // Делаем prev как правого ребенка curr

        curr->right = prev;         

          

        prev = curr;

        curr = next;

    }

    return prev;

}

  
// Итеративный метод для прохождения уровня порядка
// построчно

void printLevelOrder(Node *root)

{

    // Базовый вариант

    if (root == NULL) return;

  

    // Создать пустую очередь для прохождения порядка уровней

    queue<Node *> q;

  

    // ставим в очередь Root и инициализируем высоту

    q.push(root);

  

    while (1)

    {

        // nodeCount (размер очереди) указывает число

        // узлов на текущем уровне.

        int nodeCount = q.size();

        if (nodeCount == 0)

            break;

  

        // Выводим из очереди все узлы текущего уровня и

        // ставим в очередь все узлы следующего уровня

        while (nodeCount > 0)

        {

            Node *node = q.front();

            cout << node->data << " ";

            q.pop();

              

            if (node->left != NULL)

                q.push(node->left);

              

            if (node->right != NULL)

                q.push(node->right);

            nodeCount--;

        }

        cout << endl;

    }

}

  
// Код драйвера

int main()

{

      

    Node* root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

    root->right->left = newNode(4);

    root->right->right = newNode(5);

  

    cout << "Level order traversal of given tree\n";

    printLevelOrder(root);

  

    root = flipBinaryTree(root);

  

    cout << "\nLevel order traversal of the flipped"

            " tree\n";

    printLevelOrder(root);

    return 0;

}

  
// Эта статья предоставлена Pal13

Джава

// Java-программа для переворота двоичного дерева

import java.util.*;

class GFG

{

      
// Узел двоичного дерева

static class Node 

    int data; 

    Node left, right; 

}; 

  
// Сервисная функция для создания
// новый узел двоичного дерева

  

static Node newNode(int data) 

    Node temp = new Node(); 

    temp.data = data; 

    temp.left = temp.right = null

    return temp; 

  
// метод для переворота двоичного дерева

static Node flipBinaryTree(Node root) 

    // Инициализация указателей

    Node curr = root; 

    Node next = null

    Node temp = null

    Node prev = null

      

    // Итерация по всем левым узлам

    while(curr != null

    

        next = curr.left; 

          

        // Теперь нужно поменять узлы

        // временно сохранить предыдущий

        // правый ребенок

          

        // Делаем правее

        // как левый потомок курсора

        curr.left = temp;         

          

        // Сохранение правого потомка курсора

        temp = curr.right;         

          

        // Делаем prev as curr

        // правый ребенок

        curr.right = prev;         

          

        prev = curr; 

        curr = next; 

    

    return prev; 

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

static void printLevelOrder(Node root) 

    // Базовый вариант

    if (root == null) return

  

    // Создать пустую очередь для

    // уровень прохождения заказа

    Queue<Node> q = new LinkedList<Node>(); 

  

    // ставим в очередь Root и

    // инициализировать высоту

    q.add(root); 

  

    while (true

    

        // nodeCount (размер очереди)

        // указывает количество узлов

        // на текущем уровне.

        int nodeCount = q.size(); 

        if (nodeCount == 0

            break

  

        // Удаление всех узлов текущего

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

        // следующего уровня

        while (nodeCount > 0

        

            Node node = q.peek(); 

            System.out.print(node.data + " "); 

            q.remove(); 

              

            if (node.left != null

                q.add(node.left); 

              

            if (node.right != null

                q.add(node.right); 

            nodeCount--; 

        

        System.out.println();

    

  
// Код драйвера

public static void main(String args[])

    Node root = newNode(1); 

    root.left = newNode(2); 

    root.right = newNode(3); 

    root.right.left = newNode(4); 

    root.right.right = newNode(5); 

  

    System.out.print("Level order traversal "

                            "of given tree\n"); 

    printLevelOrder(root); 

  

    root = flipBinaryTree(root); 

  

    System.out.print("\nLevel order traversal "

                        "of the flipped tree\n"); 

    printLevelOrder(root); 


}

  
// Этот код добавлен
// Арнаб Кунду

C #

// C # программа для переворота двоичного дерева

using System;

using System.Collections.Generic;

  

class GFG

{

  
// Узел двоичного дерева

public class Node

{

    public int data;

    public Node left, right;

}

  
// Сервисная функция для создания
// новый узел двоичного дерева

public static Node newNode(int data)

{

    Node temp = new Node();

    temp.data = data;

    temp.left = temp.right = null;

    return temp;

}

  
// метод для переворота двоичного дерева

public static Node flipBinaryTree(Node root)

{

    // Инициализация указателей

    Node curr = root;

    Node next = null;

    Node temp = null;

    Node prev = null;

  

    // Итерация по всем левым узлам

    while (curr != null)

    {

        next = curr.left;

  

        // Теперь нужно поменять узлы

        // временно сохранить предыдущий

        // правый ребенок

  

        // Делаем правее

        // как левый потомок курсора

        curr.left = temp;

  

        // Сохранение правого потомка курсора

        temp = curr.right;

  

        // Делаем prev as curr

        // правый ребенок

        curr.right = prev;

  

        prev = curr;

        curr = next;

    }

    return prev;

}

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

public static void printLevelOrder(Node root)

{

    // Базовый вариант

    if (root == null)

    {

        return;

    }

  

    // Создать пустую очередь для

    // уровень прохождения заказа

    LinkedList<Node> q = new LinkedList<Node>();

  

    // ставим в очередь Root и

    // инициализировать высоту

    q.AddLast(root);

  

    while (true)

    {

        // nodeCount (размер очереди)

        // указывает количество узлов

        // на текущем уровне.

        int nodeCount = q.Count;

        if (nodeCount == 0)

        {

            break;

        }

  

        // Удаление всех узлов текущего

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

        // следующего уровня

        while (nodeCount > 0)

        {

            Node node = q.First.Value;

            Console.Write(node.data + " ");

            q.RemoveFirst();

  

            if (node.left != null)

            {

                q.AddLast(node.left);

            }

  

            if (node.right != null)

            {

                q.AddLast(node.right);

            }

            nodeCount--;

        }

        Console.WriteLine();

    }

}

  
// Код драйвера

public static void Main(string[] args)

{

    Node root = newNode(1);

    root.left = newNode(2);

    root.right = newNode(3);

    root.right.left = newNode(4);

    root.right.right = newNode(5);

  

    Console.Write("Level order traversal "

                         "of given tree\n");

    printLevelOrder(root);

  

    root = flipBinaryTree(root);

  

    Console.Write("\nLevel order traversal "

                     "of the flipped tree\n");

    printLevelOrder(root);

}
}

  
// Этот код предоставлен Shrikant13


Выход:

Level order traversal of given tree
1 
2 3 
4 5 

Level order traversal of the flipped tree
2 
3 1 
4 5 

Анализ сложности:
Сложность по времени: O (n), так как в худшем случае глубина двоичного дерева будет равна n.
Вспомогательное пространство: O (1).

Эта статья предоставлена Уткаршем Триведи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Отразить бинарное дерево

0.00 (0%) 0 votes