Рубрики

Преобразуйте бинарное дерево в его зеркальное дерево

Зеркало дерева: Зеркало бинарного дерева T — это еще одно бинарное дерево M (T), в котором левый и правый дочерние элементы всех неконечных узлов меняются местами.

Деревья на рисунке выше являются зеркалами друг друга

Метод 1 (рекурсивный)

Алгоритм — Зеркало (дерево):

(1)  Call Mirror for left-subtree    i.e., Mirror(left-subtree)
(2)  Call Mirror for right-subtree  i.e., Mirror(right-subtree)
(3)  Swap left and right subtrees.
          temp = left-subtree
          left-subtree = right-subtree
          right-subtree = temp

C ++

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

using namespace std;

  
/ * Узел двоичного дерева имеет данные, указатель
левый ребенок и указатель на правый ребенок * /

struct Node 

{

    int data;

    struct Node* left;

    struct Node* right;

};

  
/ * Вспомогательная функция, которая выделяет новый узел с
указанные данные и NULL левый и правый указатели. * /

struct Node* newNode(int data)

{

    struct Node* node = (struct Node*)

                         malloc(sizeof(struct Node));

    node->data = data;

    node->left = NULL;

    node->right = NULL;

      

    return(node);

}

  

  
/ * Изменить дерево так, чтобы роли левого и

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

  
Итак, дерево ...

    4

    / /

    2 5

    / /

1 3

  
изменено на ...

    4

    / /

    5 2

        / /

    3 1

* /

void mirror(struct Node* node) 

{

    if (node == NULL) 

        return

    else

    {

        struct Node* temp;

          

        / * сделать поддеревья * /

        mirror(node->left);

        mirror(node->right);

      

        / * поменять местами указатели в этом узле * /

        temp     = node->left;

        node->left = node->right;

        node->right = temp;

    }

  
/ * Вспомогательная функция для печати
Порядок обхода. * /

void inOrder(struct Node* node) 

{

    if (node == NULL) 

        return;

      

    inOrder(node->left);

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

    inOrder(node->right);

  

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

int main()

{

    struct Node *root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

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

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

      

    / * Вывести порядок обхода дерева ввода * /

    cout << "Inorder traversal of the constructed"

         << " tree is" << endl;

    inOrder(root);

      

    / * Преобразовать дерево в его зеркало * /

    mirror(root); 

      

    / * Печать по порядку обхода зеркального дерева * /

    cout << "\nInorder traversal of the mirror tree"

         << " is \n"

    inOrder(root);

      

    return 0; 

}

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

С

// C программа для преобразования двоичного дерева
// к его зеркалу
#include<stdio.h>
#include<stdlib.h>

  
/ * Узел двоичного дерева имеет данные, указатель

   левый ребенок и указатель на правый ребенок * /

struct Node 

{

    int data;

    struct Node* left;

    struct Node* right;

};

  
/ * Вспомогательная функция, которая выделяет новый узел с

   данные даны и NULL левый и правый указатели. * /

struct Node* newNode(int data)

  
{

  struct Node* node = (struct Node*)

                       malloc(sizeof(struct Node));

  node->data = data;

  node->left = NULL;

  node->right = NULL;

    

  return(node);

}

  

  
/ * Изменить дерево так, чтобы роли левого и

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

  

 Итак, дерево ...

       4

      / /

     2 5

    / /

   1 3

  

 изменено на ...

       4

      / /

     5 2

        / /

       3 1

* /

void mirror(struct Node* node) 

{

  if (node==NULL) 

    return;  

  else 

  {

    struct Node* temp;

      

    / * сделать поддеревья * /

    mirror(node->left);

    mirror(node->right);

  

    / * поменять местами указатели в этом узле * /

    temp        = node->left;

    node->left  = node->right;

    node->right = temp;

  }

  
/ * Вспомогательная функция для печати обхода Inorder. * /

void inOrder(struct Node* node) 

{

  if (node == NULL) 

    return;

    

  inOrder(node->left);

  printf("%d ", node->data);

  inOrder(node->right);

}  

  

  
/ * Программа драйвера для проверки зеркала () * /

int main()

{

  struct Node *root = newNode(1);

  root->left        = newNode(2);

  root->right       = newNode(3);

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

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

    

  / * Вывести порядок обхода дерева ввода * /

  printf("Inorder traversal of the constructed"

           " tree is \n");

  inOrder(root);

    

  / * Преобразовать дерево в его зеркало * /

  mirror(root); 

    

  / * Печать по порядку обхода зеркального дерева * /

  printf("\nInorder traversal of the mirror tree"

         " is \n");  

  inOrder(root);

    

  return 0;  

}

Джава

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

  
/ * Класс, содержащий левого и правого потомка текущего

   значение узла и ключа * /

class Node

{

    int data;

    Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

class BinaryTree

{

    Node root;

  

    void mirror()

    {

        root = mirror(root);

    }

  

    Node mirror(Node node)

    {

        if (node == null)

            return node;

  

        / * сделать поддеревья * /

        Node left = mirror(node.left);

        Node right = mirror(node.right);

  

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

        node.left = right;

        node.right = left;

  

        return node;

    }

  

    void inOrder()

    {

        inOrder(root);

    }

  

    / * Вспомогательная функция для проверки зеркала (). Учитывая бинарный

       поиск дерева, распечатать его элементы данных в

       увеличение отсортированного заказа. * /

    void inOrder(Node node)

    {

        if (node == null)

            return;

  

        inOrder(node.left);

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

  

        inOrder(node.right);

    }

  

    / * тестирование на примере узлов * /

    public static void main(String args[])

    {

        / * создание бинарного дерева и ввод узлов * /

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(1);

        tree.root.left = new Node(2);

        tree.root.right = new Node(3);

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

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

  

        / * распечатать порядок обхода входного дерева * /

        System.out.println("Inorder traversal of input tree is :");

        tree.inOrder();

        System.out.println("");

  

        / * преобразовать дерево в его зеркало * /

        tree.mirror();

  

        / * печать обхода второстепенного дерева * /

        System.out.println("Inorder traversal of binary tree is : ");

        tree.inOrder();

  

    }

}

python3

# Python3 программа для преобразования двоичного файла
# дерево к зеркалу

  
# Сервисная функция для создания нового
# узел дерева

class newNode:

    def __init__(self,data):

        self.data = data

        self.left = self.right = None

  
"" "Измените дерево так, чтобы роли

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

    каждый узел.

  
Итак, дерево ...

        4

        / /

    2 5

    / /

    1 3

  
изменено на ...

    4

    / /

    5 2

    / /

    3 1

«»»

def mirror(node): 

  

    if (node == None):

        return

    else:

  

        temp = node 

          

        "" "сделать поддеревья" ""

        mirror(node.left) 

        mirror(node.right) 

  

        "" "поменяйте местами указатели в этом узле" ""

        temp = node.left 

        node.left = node.right 

        node.right = temp 

  
"" "Вспомогательная функция для печати обхода Inorder." ""

def inOrder(node) :

  

    if (node == None): 

        return

          

    inOrder(node.left) 

    print(node.data, end = " "

    inOrder(node.right) 

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

if __name__ =="__main__"

  

    root = newNode(1

    root.left = newNode(2

    root.right = newNode(3

    root.left.left = newNode(4

    root.left.right = newNode(5

  

    "" "Печать по порядку обхода

        дерево ввода "" "

    print("Inorder traversal of the"

               "constructed tree is"

    inOrder(root) 

      

    "" "Преобразовать дерево в его зеркало" ""

    mirror(root) 

  

    "" "Печать по порядку обхода

        зеркальное дерево "" "

    print("\nInorder traversal of"

              "the mirror treeis "

    inOrder(root) 

  
# Этот код предоставлен
# Шубхам Сингх (SHUBHAMSINGH10)

C #

// C # программа для преобразования двоичного файла
// дерево в его зеркало

using System;

  
// Класс, содержащий влево и вправо
// потомок текущего узла и значения ключа

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

class GFG

{

public Node root;

  

public virtual void mirror()

{

    root = mirror(root);

}

  

public virtual Node mirror(Node node)

{

    if (node == null)

    {

        return node;

    }

  

    / * сделать поддеревья * /

    Node left = mirror(node.left);

    Node right = mirror(node.right);

  

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

    node.left = right;

    node.right = left;

  

    return node;

}

  

public virtual void inOrder()

{

    inOrder(root);

}

  
/ * Вспомогательная функция для проверки зеркала ().
Учитывая двоичное дерево поиска, распечатайте его
элементы данных в порядке сортировки по возрастанию. * /

public virtual void inOrder(Node node)

{

    if (node == null)

    {

        return;

    }

  

    inOrder(node.left);

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

  

    inOrder(node.right);

}

  
/ * тестирование на примере узлов * /

public static void Main(string[] args)

{

    / * создание двоичного дерева и

    вход в узлы * /

    GFG tree = new GFG();

    tree.root = new Node(1);

    tree.root.left = new Node(2);

    tree.root.right = new Node(3);

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

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

  

    / * распечатать порядок обхода входного дерева * /

    Console.WriteLine("Inorder traversal "

                      "of input tree is :");

    tree.inOrder();

    Console.WriteLine("");

  

    / * преобразовать дерево в его зеркало * /

    tree.mirror();

  

    / * печать обхода второстепенного дерева * /

    Console.WriteLine("Inorder traversal "

                    "of binary tree is : ");

    tree.inOrder();

}
}

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


Выход :

Inorder traversal of the constructed tree is 
4 2 5 1 3 
Inorder traversal of the mirror tree is 
3 1 5 2 4 

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

Метод 2 (итеративный)

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

C ++

// Итеративная программа CPP для преобразования двоичного файла
// Дерево к его зеркалу
#include<bits/stdc++.h>

using namespace std;

  
/ * Узел двоичного дерева содержит данные, указатель на

   левый ребенок и указатель на правый ребенок * /

struct Node

{

    int data;

    struct Node* left;

    struct Node* right;

};

  
/ * Вспомогательная функция, которая выделяет новый узел

   с данными данными и NULL влево и вправо

   указатели. * /

struct Node* newNode(int data)

  
{

    struct Node* node = new Node;

    node->data = data;

    node->left = node->right = NULL;

    return(node);

}

  
/ * Изменить дерево так, чтобы роли левого и

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

 Итак, дерево ...

       4

      / /

     2 5

    / /

   1 3

  

 изменено на ...

       4

      / /

     5 2

        / /

       3 1

* /

void mirror(Node* root)

{

    if (root == NULL)

        return;

  

    queue<Node*> q;

    q.push(root);

  

    // Делаем BFS. Делая BFS, продолжайте менять

    // левый и правый дети

    while (!q.empty())

    {

        // поп топ узел из очереди

        Node* curr = q.front();

        q.pop();

  

        // поменять местами левого и правого ребенка

        swap(curr->left, curr->right);

  

        // толкаем левых и правых детей

        if (curr->left)

            q.push(curr->left);

        if (curr->right)

            q.push(curr->right);

    }

}

  

  
/ * Вспомогательная функция для печати обхода Inorder. * /

void inOrder(struct Node* node)

{

    if (node == NULL)

        return;

    inOrder(node->left);

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

    inOrder(node->right);

}

  

  
/ * Программа драйвера для проверки зеркала () * /

int main()

{

    struct Node *root = newNode(1);

    root->left        = newNode(2);

    root->right       = newNode(3);

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

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

  

    / * Вывести порядок обхода дерева ввода * /

    cout << "\n Inorder traversal of the"

            " constructed tree is \n";

    inOrder(root);

  

    / * Преобразовать дерево в его зеркало * /

    mirror(root);

  

    / * Печать по порядку обхода зеркального дерева * /

    cout << "\n Inorder traversal of the "

           "mirror tree is \n";

    inOrder(root);

  

    return 0;

}

Джава

// Итеративная Java-программа для преобразования двоичного
// Дерево к его зеркалу

import java.util.*;

  

class GFG

{

      
/ * Узел двоичного дерева содержит данные, указатель на
левый ребенок и указатель на правый ребенок * /

static class Node

{

    int data;

    Node left;

    Node right;

};

  
/ * Вспомогательная функция, которая выделяет новый узел
с заданными данными и нулем влево и вправо
указатели. * /

static Node newNode(int data)

  
{

    Node node = new Node();

    node.data = data;

    node.left = node.right = null;

    return(node);

}

  
/ * Изменить дерево так, чтобы роли левого и

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

Итак, дерево ...

    4

    / /

    2 5

    / /

1 3

  
изменено на ...

    4

    / /

    5 2

        / /

    3 1

* /

static void mirror(Node root)

{

    if (root == null)

        return;

  

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

    q.add(root);

  

    // Делаем BFS. Делая BFS, продолжайте менять

    // левый и правый дети

    while (q.size() > 0)

    {

        // поп топ узел из очереди

        Node curr = q.peek();

        q.remove();

  

        // поменять местами левого и правого ребенка

        Node temp = curr.left;

        curr.left = curr.right;

        curr.right = temp;;

  

        // толкаем левых и правых детей

        if (curr.left != null)

            q.add(curr.left);

        if (curr.right != null)

            q.add(curr.right);

    }

}

  

  
/ * Вспомогательная функция для печати обхода Inorder. * /

static void inOrder( Node node)

{

    if (node == null)

        return;

    inOrder(node.left);

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

    inOrder(node.right);

}

  

  
/ * Код водителя * /

public static void main(String args[])

{

    Node root = newNode(1);

    root.left = newNode(2);

    root.right = newNode(3);

    root.left.left = newNode(4);

    root.left.right = newNode(5);

  

    / * Вывести порядок обхода дерева ввода * /

    System.out.print( "\n Inorder traversal of the"

            +" coned tree is \n");

    inOrder(root);

  

    / * Преобразовать дерево в его зеркало * /

    mirror(root);

  

    / * Печать по порядку обхода зеркального дерева * /

    System.out.print( "\n Inorder traversal of the "+

        "mirror tree is \n");

    inOrder(root);

}
}

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

python3

# Python3 программа для преобразования двоичного
# Дерево к своему зеркалу

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

class newNode:

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  
'' 'Измените дерево так, чтобы роли ушли

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

    Итак, дерево ...

        4

        / /

        2 5

        / /

    1 3

      

    изменено на ...

        4

        / /

        5 2

            / /

        3 1

    «»»

      

def mirror( root):

  

    if (root == None):

        return

  

    q = []

    q.append(root)

  

    # Делай БФС. Делая BFS, продолжайте менять

    # левые и правые дети

    while (len(q)):

  

        # pop top узел из очереди

        curr = q[0]

        q.pop(0)

  

        # поменять местами левого ребенка с правым ребенком

        curr.left, curr.right = curr.right, curr.left

  

        # добавить левого и правого детей

        if (curr.left):

            q.append(curr.left)

        if (curr.right):

            q.append(curr.right)

  
"" "Вспомогательная функция для печати обхода Inorder." ""

def inOrder( node):

    if (node == None):

        return

    inOrder(node.left)

    print(node.data, end = " ")

    inOrder(node.right) 

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

root = newNode(1

root.left = newNode(2

root.right = newNode(3

root.left.left = newNode(4

root.left.right = newNode(5

  
"" "Печать по порядку обхода дерева ввода" ""

print("Inorder traversal of the constructed tree is"

inOrder(root) 

  
"" "Преобразовать дерево в его зеркало" ""
mirror(root) 

  
"" "Печать по порядку обхода зеркального дерева" ""

print("\nInorder traversal of the mirror tree is"

inOrder(root) 

  
# Этот код предоставлен SHUBHAMSINGH10

C #

// C # Итеративная Java-программа для преобразования двоичного файла
// Дерево к его зеркалу

using System.Collections.Generic;

using System;

      

class GFG

{

      
/ * Узел двоичного дерева содержит данные, указатель на
левый ребенок и указатель на правый ребенок * /

public class Node

{

    public int data;

    public Node left;

    public Node right;

};

  
/ * Вспомогательная функция, которая выделяет новый узел
с заданными данными и нулем влево и вправо
указатели. * /

static Node newNode(int data)

  
{

    Node node = new Node();

    node.data = data;

    node.left = node.right = null;

    return(node);

}

  
/ * Изменить дерево так, чтобы роли левого и

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

Итак, дерево ...

    4

    / /

    2 5

    / /

1 3

  
изменено на ...

    4

    / /

    5 2

        / /

    3 1

* /

static void mirror(Node root)

{

    if (root == null)

        return;

  

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

    q.Enqueue(root);

  

    // Делаем BFS. Делая BFS, продолжайте менять

    // левый и правый дети

    while (q.Count > 0)

    {

        // поп топ узел из очереди

        Node curr = q.Peek();

        q.Dequeue();

  

        // поменять местами левого и правого ребенка

        Node temp = curr.left;

        curr.left = curr.right;

        curr.right = temp;;

  

        // толкаем левых и правых детей

        if (curr.left != null)

            q.Enqueue(curr.left);

        if (curr.right != null)

            q.Enqueue(curr.right);

    }

}

  

  
/ * Вспомогательная функция для печати обхода Inorder. * /

static void inOrder( Node node)

{

    if (node == null)

        return;

    inOrder(node.left);

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

    inOrder(node.right);

}

  

  
/ * Код водителя * /

public static void Main(String []args)

{

    Node root = newNode(1);

    root.left = newNode(2);

    root.right = newNode(3);

    root.left.left = newNode(4);

    root.left.right = newNode(5);

  

    / * Вывести порядок обхода дерева ввода * /

    Console.Write( "\n Inorder traversal of the"

            +" coned tree is \n");

    inOrder(root);

  

    / * Преобразовать дерево в его зеркало * /

    mirror(root);

  

    / * Печать по порядку обхода зеркального дерева * /

    Console.Write( "\n Inorder traversal of the "+

        "mirror tree is \n");

    inOrder(root);

}
}

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


Выход:

 Inorder traversal of the constructed tree is 
4 2 5 1 3 
 Inorder traversal of the mirror tree is 
3 1 5 2 4 

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

Преобразуйте бинарное дерево в его зеркальное дерево

0.00 (0%) 0 votes