Рубрики

Обратные альтернативные уровни идеального бинарного дерева

Если задано совершенное двоичное дерево, поменяйте местами узлы альтернативного уровня двоичного дерева.

  
Given tree: 
               a
            /     \
           b       c
         /  \     /  \
        d    e    f    g
       / \  / \  / \  / \
       h  i j  k l  m  n  o 

Modified tree:
             a
            /     \
           c       b
         /  \     /  \
        d    e    f    g
       / \  / \  / \  / \
      o  n m  l k  j  i  h 

Способ 1 (простой)
Простое решение состоит в том, чтобы сделать следующие шаги.
1) Доступ к узлам по уровням.
2) Если текущий уровень нечетный, сохраните узлы этого уровня в массиве.
3) Обратный массив и сохранить элементы обратно в дереве.

Метод 2 (Использование двух обходов)
Другой — сделать два обхода по порядку. Ниже приведены шаги, которым нужно следовать.
1) Пройдите по указанному дереву по порядку и сохраните все нечетные узлы уровня во вспомогательном массиве. Для приведенного выше примера данного дерева содержимое массива становится {h, i, b, j, k, l, m, c, n, o}

2) Обратный массив. Массив теперь становится {o, n, c, m, l, k, j, b, i, h}

3) Пройдите через дерево снова в порядке моды. При обходе дерева один за другим берут элементы из массива и сохраняют элементы из массива на каждом узле, проходящем с нечетным уровнем.
Для приведенного выше примера мы сначала пересекаем «h» в массиве выше и заменяем «h» на «o». Затем мы пересекаем 'i' и заменяем его на n.

Ниже приведена реализация вышеуказанного алгоритма.

C ++

// C ++ программа для обратного изменения альтернативных уровней двоичного дерева
#include<iostream>
#define MAX 100

using namespace std;

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

struct Node

{

    char data;

    struct Node *left, *right;

};

  
// Утилита для создания нового узла Binary Tree

struct Node *newNode(char item)

{

    struct Node *temp =  new Node;

    temp->data = item;

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

    return temp;

}

  
// Функция для хранения узлов альтернативных уровней в массиве

void storeAlternate(Node *root, char arr[], int *index, int l)

{

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

    if (root == NULL) return;

  

    // Сохраняем элементы левого поддерева

    storeAlternate(root->left, arr, index, l+1);

  

    // Сохраняем этот узел, только если это узел нечетного уровня

    if (l%2 != 0)

    {

        arr[*index] = root->data;

        (*index)++;

    }

  

    // Сохраняем элементы правого поддерева

    storeAlternate(root->right, arr, index, l+1);

}

  
// Функция для изменения двоичного дерева (все нечетные узлы уровня
// обновляется, принимая элементы из массива по порядку)

void modifyTree(Node *root, char arr[], int *index, int l)

{

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

    if (root == NULL) return;

  

    // Обновляем узлы в левом поддереве

    modifyTree(root->left, arr, index, l+1);

  

    // Обновляем этот узел, только если это узел нечетного уровня

    if (l%2 != 0)

    {

        root->data = arr[*index];

        (*index)++;

    }

  

    // Обновляем узлы в правом поддереве

    modifyTree(root->right, arr, index, l+1);

}

  
// Вспомогательная функция для обратного массива из индекса
// от 0 до n-1

void reverse(char arr[], int n)

{

    int l = 0, r = n-1;

    while (l < r)

    {

        int temp = arr[l];

        arr[l] = arr[r];

        arr[r] = temp;

        l++; r--;

    }

}

  
// Основная функция для обращения альтернативных узлов двоичного дерева

void reverseAlternate(struct Node *root)

{

    // Создать вспомогательный массив для хранения узлов альтернативных уровней

    char *arr = new char[MAX];

    int index = 0;

  

    // Сначала сохраняем узлы альтернативных уровней

    storeAlternate(root, arr, &index, 0);

  

    // Обратный массив

    reverse(arr, index);

  

    // Обновляем дерево, беря элементы из массива

    index = 0;

    modifyTree(root, arr, &index, 0);

}

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

void printInorder(struct Node *root)

{

    if (root == NULL) return;

    printInorder(root->left);

    cout << root->data << " ";

    printInorder(root->right);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    struct Node *root = newNode('a');

    root->left = newNode('b');

    root->right = newNode('c');

    root->left->left = newNode('d');

    root->left->right = newNode('e');

    root->right->left = newNode('f');

    root->right->right = newNode('g');

    root->left->left->left = newNode('h');

    root->left->left->right = newNode('i');

    root->left->right->left = newNode('j');

    root->left->right->right = newNode('k');

    root->right->left->left = newNode('l');

    root->right->left->right = newNode('m');

    root->right->right->left = newNode('n');

    root->right->right->right = newNode('o');

  

    cout << "Inorder Traversal of given tree\n";

    printInorder(root);

  

    reverseAlternate(root);

  

    cout << "\n\nInorder Traversal of modified tree\n";

    printInorder(root);

  

    return 0;

}

Джава

// Java-программа для обращения альтернативных уровней идеального бинарного дерева
// Узел двоичного дерева

class Node {

  

    char data;

    Node left, right;

  

    Node(char item) {

        data = item;

        left = right = null;

    }

}

  
// класс для доступа к значению индекса по ссылке

class Index {

  

    int index;

}

  

class BinaryTree {

  

    Node root;

    Index index_obj = new Index();

  

    // функция для хранения альтернативных уровней в дереве

    void storeAlternate(Node node, char arr[], Index index, int l) {

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

        if (node == null) {

            return;

        }

        // сохраняем элементы левого поддерева

        storeAlternate(node.left, arr, index, l + 1);

  

        // сохранить этот узел, только если уровень нечетный

        if (l % 2 != 0) {

            arr[index.index] = node.data;

            index.index++;

        }

  

        storeAlternate(node.right, arr, index, l + 1);

    }

  

    // Функция для изменения двоичного дерева (все нечетные узлы уровня

    // обновляется, принимая элементы из массива по порядку)

    void modifyTree(Node node, char arr[], Index index, int l) {

  

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

        if (node == null) {

            return;

        }

  

        // Обновляем узлы в левом поддереве

        modifyTree(node.left, arr, index, l + 1);

  

        // Обновляем этот узел, только если это узел нечетного уровня

        if (l % 2 != 0) {

            node.data = arr[index.index];

            (index.index)++;

        }

  

        // Обновляем узлы в правом поддереве

        modifyTree(node.right, arr, index, l + 1);

    }

  

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

    // от 0 до n-1

    void reverse(char arr[], int n) {

        int l = 0, r = n - 1;

        while (l < r) {

            char temp = arr[l];

            arr[l] = arr[r];

            arr[r] = temp;

            l++;

            r--;

        }

    }

  

    void reverseAlternate() {

        reverseAlternate(root);

    }

  

    // Основная функция для обращения альтернативных узлов двоичного дерева

    void reverseAlternate(Node node) {

  

        // Создать вспомогательный массив для хранения узлов альтернативных уровней

        char[] arr = new char[100];

  

        // Сначала сохраняем узлы альтернативных уровней

        storeAlternate(node, arr, index_obj, 0);

  

        //index_obj.index = 0;

          

        // Обратный массив

        reverse(arr, index_obj.index);

  

        // Обновляем дерево, беря элементы из массива

        index_obj.index = 0;

        modifyTree(node, arr, index_obj, 0);

    }

  

    void printInorder() {

        printInorder(root);

    }

  

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

    // двоичное дерево

    void printInorder(Node node) {

        if (node == null) {

            return;

        }

        printInorder(node.left);

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

        printInorder(node.right);

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String args[]) {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node('a');

        tree.root.left = new Node('b');

        tree.root.right = new Node('c');

        tree.root.left.left = new Node('d');

        tree.root.left.right = new Node('e');

        tree.root.right.left = new Node('f');

        tree.root.right.right = new Node('g');

        tree.root.left.left.left = new Node('h');

        tree.root.left.left.right = new Node('i');

        tree.root.left.right.left = new Node('j');

        tree.root.left.right.right = new Node('k');

        tree.root.right.left.left = new Node('l');

        tree.root.right.left.right = new Node('m');

        tree.root.right.right.left = new Node('n');

        tree.root.right.right.right = new Node('o');

        System.out.println("Inorder Traversal of given tree");

        tree.printInorder();

  

        tree.reverseAlternate();

        System.out.println("");

        System.out.println("");

        System.out.println("Inorder Traversal of modified tree");

        tree.printInorder();

    }

}

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

C #

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

using System;

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

public class Node

{

    public char data;

    public Node left, right;

  

    public Node(char item)

    {

        data = item;

        left = right = null;

    }

}

  
// класс для доступа к значению индекса
// по ссылке

public class Index

{

    public int index;

}

  

class GFG

{

public Node root;

public Index index_obj = new Index();

  
// функция для хранения альтернативы
// уровни в дереве

public virtual void storeAlternate(Node node, char[] arr, 

                                   Index index, int l)

{

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

    if (node == null)

    {

        return;

    }

      

    // сохраняем элементы левого поддерева

    storeAlternate(node.left, arr, index, l + 1);

  

    // сохранить этот узел, только если уровень нечетный

    if (l % 2 != 0)

    {

        arr[index.index] = node.data;

        index.index++;

    }

  

    storeAlternate(node.right, arr, index, l + 1);

}

  
// Функция для изменения двоичного дерева (все нечетно
// узлы уровня обновляются путем взятия элементов
// из массива по порядку)

public virtual void modifyTree(Node node, char[] arr, 

                               Index index, int l)

{

  

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

    if (node == null)

    {

        return;

    }

  

    // Обновляем узлы в левом поддереве

    modifyTree(node.left, arr, index, l + 1);

  

    // Обновляем этот узел, только если этот

    // узел нечетного уровня

    if (l % 2 != 0)

    {

        node.data = arr[index.index];

        (index.index)++;

    }

  

    // Обновляем узлы в правом поддереве

    modifyTree(node.right, arr, index, l + 1);

}

  
// Вспомогательная функция для обратного
// массив от индекса 0 до n-1

public virtual void reverse(char[] arr, int n)

{

    int l = 0, r = n - 1;

    while (l < r)

    {

        char temp = arr[l];

        arr[l] = arr[r];

        arr[r] = temp;

        l++;

        r--;

    }

}

  

public virtual void reverseAlternate()

{

    reverseAlternate(root);

}

  
// Основная функция для обратного
// альтернативные узлы двоичного дерева

public virtual void reverseAlternate(Node node)

{

  

    // Создать вспомогательный массив для

    // храним узлы альтернативных уровней

    char[] arr = new char[100];

  

    // Сначала сохраняем узлы альтернативных уровней

    storeAlternate(node, arr, index_obj, 0);

  

    //index_obj.index = 0;

  

    // Обратный массив

    reverse(arr, index_obj.index);

  

    // Обновляем дерево, беря элементы из массива

    index_obj.index = 0;

    modifyTree(node, arr, index_obj, 0);

}

  

public virtual void printInorder()

{

    printInorder(root);

}

  
// Утилита для печати indorder
// обход бинарного дерева

public virtual void printInorder(Node node)

{

    if (node == null)

    {

        return;

    }

    printInorder(node.left);

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

    printInorder(node.right);

}

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

public static void Main(string[] args)

{

    GFG tree = new GFG();

    tree.root = new Node('a');

    tree.root.left = new Node('b');

    tree.root.right = new Node('c');

    tree.root.left.left = new Node('d');

    tree.root.left.right = new Node('e');

    tree.root.right.left = new Node('f');

    tree.root.right.right = new Node('g');

    tree.root.left.left.left = new Node('h');

    tree.root.left.left.right = new Node('i');

    tree.root.left.right.left = new Node('j');

    tree.root.left.right.right = new Node('k');

    tree.root.right.left.left = new Node('l');

    tree.root.right.left.right = new Node('m');

    tree.root.right.right.left = new Node('n');

    tree.root.right.right.right = new Node('o');

    Console.WriteLine("Inorder Traversal of given tree");

    tree.printInorder();

  

    tree.reverseAlternate();

    Console.WriteLine("");

    Console.WriteLine("");

    Console.WriteLine("Inorder Traversal of modified tree");

    tree.printInorder();

}
}

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


Выход:

Inorder Traversal of given tree
h d i b j e k a l f m c n g o

Inorder Traversal of modified tree
o d n c m e l a k f j b i g h

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

Метод 3 (с использованием одного обхода)

C ++

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

using namespace std;

  

struct Node

{

    char key;

    Node *left, *right;

};

  

void preorder(struct Node *root1, struct Node* root2, int lvl)

{

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

    if (root1 == NULL || root2==NULL)

        return;

  

    // Меняем местами поддеревья, если уровень четный

    if (lvl%2 == 0)

        swap(root1->key, root2->key);

  

    // Повторение для левого и правого поддеревьев (Примечание: слева от root1

    // передается и право root2 при первом вызове и наоборот

    // во втором вызове.

    preorder(root1->left, root2->right, lvl+1);

    preorder(root1->right, root2->left, lvl+1);

}

  
// Эта функция вызывает preorder () для левого и правого потомка
// корня

void reverseAlternate(struct Node *root)

{

   preorder(root->left, root->right, 0);

}

  
// обход обхода (используется для печати начального и
// модифицированные деревья)

void printInorder(struct Node *root)

{

    if (root == NULL)

       return;

    printInorder(root->left);

    cout << root->key << " ";

    printInorder(root->right);

}

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

Node *newNode(int key)

{

    Node *temp = new Node;

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

    temp->key = key;

    return temp;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    struct Node *root = newNode('a');

    root->left = newNode('b');

    root->right = newNode('c');

    root->left->left = newNode('d');

    root->left->right = newNode('e');

    root->right->left = newNode('f');

    root->right->right = newNode('g');

    root->left->left->left = newNode('h');

    root->left->left->right = newNode('i');

    root->left->right->left = newNode('j');

    root->left->right->right = newNode('k');

    root->right->left->left = newNode('l');

    root->right->left->right = newNode('m');

    root->right->right->left = newNode('n');

    root->right->right->right = newNode('o');

  

    cout << "Inorder Traversal of given tree\n";

    printInorder(root);

  

    reverseAlternate(root);

  

    cout << "\n\nInorder Traversal of modified tree\n";

    printInorder(root);

    return 0;

}

Джава

// Java-программа для обращения альтернативных уровней дерева

class Sol

{

      

static class Node 

    char key; 

    Node left, right; 

}; 

  

static void preorder( Node root1, Node root2, int lvl) 

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

    if (root1 == null || root2==null

        return

  

    // Меняем местами поддеревья, если уровень четный

    if (lvl % 2 == 0

        {

            char t = root1.key;

            root1.key = root2.key;

            root2.key = t;

        }

  

    // Повторение для левого и правого поддеревьев (Примечание: слева от root1

    // передается и право root2 при первом вызове и наоборот

    // во втором вызове.

    preorder(root1.left, root2.right, lvl+1); 

    preorder(root1.right, root2.left, lvl+1); 

  
// Эта функция вызывает preorder () для левого и правого потомка
// корня

static void reverseAlternate( Node root) 

    preorder(root.left, root.right, 0); 

  
// обход обхода (используется для печати начального и
// модифицированные деревья)

static void printInorder( Node root) 

    if (root == null

        return

    printInorder(root.left); 

    System.out.print( root.key + " "); 

    printInorder(root.right); 

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

static Node newNode(int key) 

    Node temp = new Node(); 

    temp.left = temp.right = null

    temp.key = (char)key; 

    return temp; 

  
// Программа драйвера для проверки вышеуказанных функций

public static void main(String args[])

    Node root = newNode('a'); 

    root.left = newNode('b'); 

    root.right = newNode('c'); 

    root.left.left = newNode('d'); 

    root.left.right = newNode('e'); 

    root.right.left = newNode('f'); 

    root.right.right = newNode('g'); 

    root.left.left.left = newNode('h'); 

    root.left.left.right = newNode('i'); 

    root.left.right.left = newNode('j'); 

    root.left.right.right = newNode('k'); 

    root.right.left.left = newNode('l'); 

    root.right.left.right = newNode('m'); 

    root.right.right.left = newNode('n'); 

    root.right.right.right = newNode('o'); 

  

    System.out.print("Inorder Traversal of given tree\n"); 

    printInorder(root); 

  

    reverseAlternate(root); 

  

    System.out.print("\n\nInorder Traversal of modified tree\n"); 

    printInorder(root); 

      

}

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

python3

# Python3 программа для реверса
# альтернативные уровни дерева

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

class Node: 

  

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

    def __init__(self, key): 

        self.key = key 

        self.left = None

        self.right = None

  

def preorder(root1, root2, lvl):

      

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

    if (root1 == None or root2 == None):

        return

  

    # Поменять поддеревья, если уровень четный

    if (lvl % 2 == 0):

        t = root1.key

        root1.key = root2.key

        root2.key = t

  

    # Повтор для левого и правого поддеревьев

    # (Примечание: слева от root1 пройдено и

    # право root2 при первом вызове и

    # напротив во втором вызове.

    preorder(root1.left, root2.right, lvl + 1)

    preorder(root1.right, root2.left, lvl + 1)

  
# Эта функция вызывает preorder ()
# для левого и правого потомка root

def reverseAlternate(root):

    preorder(root.left, root.right, 0)

  
# Inorder traversal (используется для печати
# начальные и модифицированные деревья)

def printInorder(root):

    if (root == None):

        return

    printInorder(root.left)

    print( root.key, end = " ")

    printInorder(root.right)

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

def newNode(key):

    temp = Node(' ')

    temp.left = temp.right = None

    temp.key = key

    return temp

  
Код водителя

if __name__ == '__main__'

    root = newNode('a')

    root.left = newNode('b')

    root.right = newNode('c')

    root.left.left = newNode('d')

    root.left.right = newNode('e')

    root.right.left = newNode('f')

    root.right.right = newNode('g')

    root.left.left.left = newNode('h')

    root.left.left.right = newNode('i')

    root.left.right.left = newNode('j')

    root.left.right.right = newNode('k')

    root.right.left.left = newNode('l')

    root.right.left.right = newNode('m')

    root.right.right.left = newNode('n')

    root.right.right.right = newNode('o')

  

    print( "Inorder Traversal of given tree")

    printInorder(root)

  

    reverseAlternate(root)

  

    print("\nInorder Traversal of modified tree")

    printInorder(root)

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

C #

// C # программа для обращения альтернативных уровней дерева

using System;

  

class GFG 

      

public class Node 

    public char key; 

    public Node left, right; 

}; 

  

static void preorder( Node root1, Node root2, int lvl) 

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

    if (root1 == null || root2==null

        return

  

    // Меняем местами поддеревья, если уровень четный

    if (lvl % 2 == 0) 

        

            char t = root1.key; 

            root1.key = root2.key; 

            root2.key = t; 

        

  

    // Повторение для левого и правого поддеревьев (Примечание: слева от root1

    // передается и право root2 при первом вызове и наоборот

    // во втором вызове.

    preorder(root1.left, root2.right, lvl+1); 

    preorder(root1.right, root2.left, lvl+1); 

  
// Эта функция вызывает preorder () для левого и правого потомка
// корня

static void reverseAlternate( Node root) 

    preorder(root.left, root.right, 0); 

  
// обход обхода (используется для печати начального и
// модифицированные деревья)

static void printInorder( Node root) 

    if (root == null

        return

    printInorder(root.left); 

    Console.Write( root.key + " "); 

    printInorder(root.right); 

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

static Node newNode(int key) 

    Node temp = new Node(); 

    temp.left = temp.right = null

    temp.key = (char)key; 

    return temp; 

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

public static void Main(String []args) 

    Node root = newNode('a'); 

    root.left = newNode('b'); 

    root.right = newNode('c'); 

    root.left.left = newNode('d'); 

    root.left.right = newNode('e'); 

    root.right.left = newNode('f'); 

    root.right.right = newNode('g'); 

    root.left.left.left = newNode('h'); 

    root.left.left.right = newNode('i'); 

    root.left.right.left = newNode('j'); 

    root.left.right.right = newNode('k'); 

    root.right.left.left = newNode('l'); 

    root.right.left.right = newNode('m'); 

    root.right.right.left = newNode('n'); 

    root.right.right.right = newNode('o'); 

  

    Console.Write("Inorder Traversal of given tree\n"); 

    printInorder(root); 

  

    reverseAlternate(root); 

  

    Console.Write("\n\nInorder Traversal of modified tree\n"); 

    printInorder(root); 

      

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


Выход :

Inorder Traversal of given tree
h d i b j e k a l f m c n g o 

Inorder Traversal of modified tree
o d n c m e l a k f j b i g h 

Спасибо Soumyajit Bhattacharyay за предложенное решение.

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

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

Обратные альтернативные уровни идеального бинарного дерева

0.00 (0%) 0 votes