Преобразовать лево-правое представление двоичного дерева в нисходящее

01.01.2020Деревья

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

Представление «вниз-вправо» — это альтернативное представление, в котором каждый узел имеет указатель на левого (или первого) дочернего элемента и другой указатель на следующего родного элемента. Таким образом, братья и сестры на каждом уровне связаны слева направо.

Дано двоичное дерево в лево-правом представлении, как показано ниже

                               1
                    /    \
                   2      3
                   /    \
                   4      5
                     /     /   \
                    6    7      8

Преобразуйте структуру дерева в нисходящее представление, как показано ниже.

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

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

C ++

/ * C ++ программа для преобразования слева направо в право вниз

представление двоичного дерева * /

#include <iostream>
#include <queue>

using namespace std;

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

struct node

{

int key;

struct node *left, *right;

};

// Итеративная функция, основанная на обходе порядка
// преобразование левого-правого в нижнее правое представление.

void convert(node *root)

{

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

if (root == NULL) return;

// Рекурсивно конвертируем левые и правые поддеревья

convert(root->left);

convert(root->right);

// Если левый потомок равен NULL, сделать правым потомком левый

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

if (root->left == NULL)

root->left = root->right;

// Если левый потомок НЕ НЕДЕЙСТВИТЕЛЕН, то сделать правым потомком

// как справа от левого ребенка

else

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

// Установить права root как NULL

root->right = NULL;

}

// Полезная функция для обхода дерева, хранящегося в
// вниз-вправо.

void downRightTraversal(node *root)

{

if (root != NULL)

{

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

downRightTraversal(root->right);

downRightTraversal(root->left);

}

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

node* newNode(int key)

{

node *temp = new node;

temp->key = key;

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

return temp;

}

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

int main()

{

// Давайте создадим двоичное дерево, показанное на диаграмме выше

/ *

1

/ /

2 3

/ /

4 5

///

6 7 8

* /

node *root = newNode(1);

root->left = newNode(2);

root->right = newNode(3);

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

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

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

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

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

convert(root);

cout << "Traversal of the tree converted to down-right form\n";

downRightTraversal(root);

return 0;

}

Джава

/ * Java-программа для преобразования слева направо в
нисходящее представление бинарного дерева * /

class GFG

{

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

static class node

{

int key;

node left, right;

node(int key)

{

this.key = key;

this.left = null;

this.right = null;

}

// Итеративный уровень обхода порядка
// основанная функция для преобразования влево-вправо
// в нисходящем представлении.

static void convert(node root)

{

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

if (root == null) return;

// Рекурсивно конвертировать влево

// правильные поддеревья

convert(root.left);

convert(root.right);

// Если левый ребенок равен NULL, сделать правый

// дочерний элемент, оставленный первым.

if (root.left == null)

root.left = root.right;

// Если оставленный дочерний элемент НЕ равен NULL, то make

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

else

root.left.right = root.right;

// Установить права root как NULL

root.right = null;

}

// Полезная функция для обхода
// дерево хранится в нисходящем виде.

static void downRightTraversal(node root)

{

if (root != null)

{

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

downRightTraversal(root.right);

downRightTraversal(root.left);

}

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

static node newNode(int key)

{

node temp = new node(0);

temp.key = key;

temp.left = null;

temp.right = null;

return temp;

}

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

public static void main(String[] args)

{

// Давайте создадим бинарное дерево

// показано на диаграмме выше

/ *

1

/ /

2 3

/ /

4 5

///

6 7 8

* /

node root = new node(1);

root.left = newNode(2);

root.right = newNode(3);

root.right.left = newNode(4);

root.right.right = newNode(5);

root.right.left.left = newNode(6);

root.right.right.left = newNode(7);

root.right.right.right = newNode(8);

convert(root);

System.out.println("Traversal of the tree " +

"converted to down-right form");

downRightTraversal(root);

}
}

// Этот код добавлен
// Прерна Сайни

python3

# Python3 программа для преобразования влево-вправо в
# представление бинарного дерева внизу справа

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

class newNode:

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

def __init__(self, key):

self.key = key

self.left = None

self.right = None

# Итеративный уровень на основе обхода порядка
# функция для преобразования слева направо вниз
# представление.

def convert(root):

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

if (root == None):

return

# Рекурсивно конвертировать влево

# правильные поддеревья

convert(root.left)

convert(root.right)

# Если левого ребенка нет, сделайте правый

# ребенок, оставленный как первый ребенок.

if (root.left == None):

root.left = root.right

# Если левого ребенка НЕ None, то сделайте

# правый ребенок как правый левый ребенок

else:

root.left.right = root.right

# Установить права root как None

root.right = None

# Функция полезности, чтобы пройти
# дерево хранится в нисходящем виде.

def downRightTraversal(root):

if (root != None):

print( root.key, end = " ")

downRightTraversal(root.right)

downRightTraversal(root.left)

Код водителя

if __name__ == '__main__':

# Давайте создадим двоичное дерево, показанное

# на диаграмме выше

«»»

1

/ /

2 3

/ /

4 5

///

6 7 8

«»»

root = newNode(1)

root.left = newNode(2)

root.right = newNode(3)

root.right.left = newNode(4)

root.right.right = newNode(5)

root.right.left.left = newNode(6)

root.right.right.left = newNode(7)

root.right.right.right = newNode(8)

convert(root)

print("Traversal of the tree converted",

"to down-right form")

downRightTraversal(root)

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

C #

// C # программа для преобразования влево-вправо в
// представление бинарного дерева внизу справа

using System;

class GFG

{

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

public class node

{

public int key;

public node left, right;

public node(int key)

{

this.key = key;

this.left = null;

this.right = null;

}

public static void convert(node root)

{

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

if (root == null)

{

return;

}

// Рекурсивно конвертировать влево

// правильные поддеревья

convert(root.left);

convert(root.right);

// Если левый ребенок равен NULL, сделать правый

// дочерний элемент, оставленный первым.

if (root.left == null)

{

root.left = root.right;

}

// Если оставленный дочерний элемент НЕ равен NULL, то make

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

else

{

root.left.right = root.right;

}

// Установить права root как NULL

root.right = null;

}

// Полезная функция для обхода
// дерево хранится в нисходящем виде.

public static void downRightTraversal(node root)

{

if (root != null)

{

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

downRightTraversal(root.right);

downRightTraversal(root.left);

}

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

public static node newNode(int key)

{

node temp = new node(0);

temp.key = key;

temp.left = null;

temp.right = null;

return temp;

}

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

public static void Main(string[] args)

{

// Давайте создадим бинарное дерево

// показано на диаграмме выше

/ *

1

/ /

2 3

/ /

4 5

///

6 7 8

* /

node root = new node(1);

root.left = newNode(2);

root.right = newNode(3);

root.right.left = newNode(4);

root.right.right = newNode(5);

root.right.left.left = newNode(6);

root.right.right.left = newNode(7);

root.right.right.right = newNode(8);

convert(root);

Console.WriteLine("Traversal of the tree " +

"converted to down-right form");

downRightTraversal(root);

}
}

// Этот код добавлен
// от Shrikant13

Выход:

Traversal of the tree converted to down-right form
1 2 3 4 5 7 8 6

Временная сложность вышеуказанной программы составляет O (n).

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

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

Преобразовать лево-правое представление двоичного дерева в нисходящее

0.00 (0%) 0 votes