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

01.01.2020Деревья

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

  
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("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("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