Рубрики

Выровнять двоичное дерево в порядке обхода порядка уровней

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

Примеры:

Input: 
          1 
        /   \ 
       5     2 
      / \   / \ 
     6   4 9   3 
Output: 1 5 2 6 4 9 3

Input:
      1
       \
        2
         \
          3
           \
            4
             \
              5
Output: 1 2 3 4 5

Подход: мы решим эту проблему путем моделирования обхода порядка двоичного дерева следующим образом:

  1. Создайте очередь для хранения узлов двоичного дерева.
  2. Создайте переменную «prev» и инициализируйте ее по родительскому узлу.
  3. Выдвиньте левого и правого потомка родителя в очередь.
  4. Применить уровень порядка обхода. Допустим, «curr» — самый передний элемент в очереди. Потом,
    • Если curr равен NULL, продолжайте.
    • Иначе нажмите curr-> left и curr-> right в очереди
    • Установить пред = курс

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

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

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

struct node {

    int data;

    node* left;

    node* right;

    node(int data)

    {

        this->data = data;

        left = NULL;

        right = NULL;

    }

};

  
// Функция для выравнивания бинарного дерева с помощью
// уровень прохождения заказа

void flatten(node* parent)

{

    // Очередь для хранения узлов

    // для BFS

    queue<node*> q;

    q.push(parent->left);

    q.push(parent->right);

    node* prev = parent;

  

    // Код для BFS

    while (q.size()) {

          

        // размер очереди

        int s = q.size();

        while (s--) {

              

            // Передний крайний узел в

            // очередь

            node* curr = q.front();

            q.pop();

  

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

            if (curr == NULL)

                continue;

            prev->right = curr;

            prev->left = NULL;

            prev = curr;

  

            // толкаем новые элементы

            // в очереди

            q.push(curr->left);

            q.push(curr->right);

        }

    }

  

    prev->left = NULL;

    prev->right = NULL;

}

  
// Функция для печати расплющенного
// Двоичное дерево

void print(node* parent)

{

    node* curr = parent;

    while (curr != NULL)

        cout << curr->data << " ", curr = curr->right;

}

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

int main()

{

    node* root = new node(1);

    root->left = new node(5);

    root->right = new node(2);

    root->left->left = new node(6);

    root->left->right = new node(4);

    root->right->left = new node(9);

    root->right->right = new node(3);

  

    // Вызов необходимых функций

    flatten(root);

    print(root);

      

    return 0;

}

Джава

// Java реализация подхода

import java.util.*;

  

class GFG

{

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

static class node 

{

    int data;

    node left;

    node right;

    node(int data)

    {

        this.data = data;

        left = null;

        right = null;

    }

};

  
// Функция для выравнивания бинарного дерева с помощью
// уровень прохождения заказа

static void flatten(node parent)

{

    // Очередь для хранения узлов

    // для BFS

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

    q.add(parent.left);

    q.add(parent.right);

    node prev = parent;

  

    // Код для BFS

    while (q.size() > 0

    {

          

        // размер очереди

        int s = q.size();

        while (s-- > 0

        {

              

            // Передний крайний узел в

            // очередь

            node curr = q.peek();

            q.remove();

  

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

            if (curr == null)

                continue;

            prev.right = curr;

            prev.left = null;

            prev = curr;

  

            // толкаем новые элементы

            // в очереди

            q.add(curr.left);

            q.add(curr.right);

        }

    }

    prev.left = null;

    prev.right = null;

}

  
// Функция для печати расплющенного
// Двоичное дерево

static void print(node parent)

{

    node curr = parent;

    while (curr != null)

    {

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

        curr = curr.right;

    }

}

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

public static void main(String[] args) 

{

    node root = new node(1);

    root.left = new node(5);

    root.right = new node(2);

    root.left.left = new node(6);

    root.left.right = new node(4);

    root.right.left = new node(9);

    root.right.right = new node(3);

  

    // Вызов необходимых функций

    flatten(root);

    print(root);

}
}

  
// Этот код предоставлен Rajput-Ji

C #

// C # реализация подхода

using System;

using System.Collections.Generic;

  

class GFG

{

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

public class node 

{

    public int data;

    public node left;

    public node right;

    public node(int data)

    {

        this.data = data;

        left = null;

        right = null;

    }

};

  
// Функция для выравнивания бинарного дерева с помощью
// уровень прохождения заказа

static void flatten(node parent)

{

    // Очередь для хранения узлов

    // для BFS

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

    q.Enqueue(parent.left);

    q.Enqueue(parent.right);

    node prev = parent;

  

    // Код для BFS

    while (q.Count > 0) 

    {

          

        // размер очереди

        int s = q.Count;

        while (s-- > 0) 

        {

              

            // Передний крайний узел в

            // очередь

            node curr = q.Peek();

            q.Dequeue();

  

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

            if (curr == null)

                continue;

            prev.right = curr;

            prev.left = null;

            prev = curr;

  

            // толкаем новые элементы

            // в очереди

            q.Enqueue(curr.left);

            q.Enqueue(curr.right);

        }

    }

    prev.left = null;

    prev.right = null;

}

  
// Функция для печати расплющенного
// Двоичное дерево

static void print(node parent)

{

    node curr = parent;

    while (curr != null)

    {

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

        curr = curr.right;

    }

}

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

public static void Main(String[] args) 

{

    node root = new node(1);

    root.left = new node(5);

    root.right = new node(2);

    root.left.left = new node(6);

    root.left.right = new node(4);

    root.right.left = new node(9);

    root.right.right = new node(3);

  

    // Вызов необходимых функций

    flatten(root);

    print(root);

}
}

  
// Этот код предоставлен Rajput-Ji

Сложность времени: O (N)
Сложность пространства: O (N), где N — размер бинарного дерева.

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

Выровнять двоичное дерево в порядке обхода порядка уровней

0.00 (0%) 0 votes