Рубрики

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

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

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

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

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

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

            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