Рубрики

Соедините все узлы с их левыми соседями в двоичном дереве

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

Примеры:

Input : 
       A
      / \
     B   C
    / \   \
   D   E   F
Output :
       NULL<--A
             / \
     NULL<--B<--C
           / \   \
   NULL<--D<--E<--F

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

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

C ++

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

  
#include <bits/stdc++.h>
#include <iostream>

using namespace std;

  
// Узел двоичного дерева, с дополнительным указателем leftNeighbour
// сохранить соседний узел слева

class node {

public:

    int data;

    node* left;

    node* right;

    node* leftNeighbour;

  

    / * Конструктор, который выделяет новый узел с

       данные даны и NULL левый и правый указатели. * /

    node(int data)

    {

        this->data = data;

        this->left = NULL;

        this->right = NULL;

        this->leftNeighbour = NULL;

    }

};

  
// Массив для хранения последних посещенных
// узел на отдельном уровне представлен
// по показателям
node* a[100];

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

void connectNodes(node* p, int l)

{

    if (p == NULL)

        return;

  

    // назначаем левого соседа

    p->leftNeighbour = a[l];

  

    // обновляем значение недавнего

    // узел на уровне

    a[l] = p;

    connectNodes(p->left, l + 1);

    connectNodes(p->right, l + 1);

}

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

void connectNodesUtil(node* root)

{   

    // Инициализировать узлы на каждом уровне в NULL

    for (int i = 0; i < 100; i++)

        a[i] = NULL;

          

    // Заполняет следующий левый указатель во всех узлах

    connectNodes(root, 0);

      

    // Давайте проверим значения следующих левых указателей

    cout << "Following are populated leftNeighbour"

            <<" pointers in the tree:\n";

              

    cout << "leftNeighbour of " << root->data << " is "

            << (root->leftNeighbour ? 

                root->leftNeighbour->data : -1) << endl;

                  

    cout << "leftNeighbour of " << root->left->data << " is "

            << (root->left->leftNeighbour ?

                root->left->leftNeighbour->data : -1) << endl;

                  

    cout << "leftNeighbour of " << root->right->data << " is "

            << (root->right->leftNeighbour ? 

                root->right->leftNeighbour->data : -1) << endl;

                  

    cout << "leftNeighbour of " << root->left->left->data << " is "

            << (root->left->left->leftNeighbour ? 

                root->left->left->leftNeighbour->data : -1) << endl;

}

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

int main()

{

  

    / * Построенное двоичное дерево

            10

            / /

           8 2

          /

         3

    * /

    node* root = new node(10);

    root->left = new node(8);

    root->right = new node(2);

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

  

    connectNodesUtil(root);

      

    return 0;

}

Джава

// Java-программа для соединения узлов
// на том же уровне, используя расширенный
// предварительный заказ обхода

import java.util.*;

  

class GFG

{

  
// Узел двоичного дерева, с дополнительным указателем leftNeighbour
// сохранить соседний узел слева

static class node 

{

    int data;

    node left;

    node right;

    node leftNeighbour;

  

    / * Конструктор, который выделяет новый узел с

    данные и нулевые левый и правый указатели. * /

    node(int data)

    {

        this.data = data;

        this.left = null;

        this.right = null;

        this.leftNeighbour = null;

    }

}

  
// Массив для хранения последних посещенных
// узел на отдельном уровне представлен
// по показателям

static node a[] = new node[100];

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

static void connectNodes(node p, int l)

{

    if (p == null)

        return;

  

    // назначаем левого соседа

    p.leftNeighbour = a[l];

  

    // обновляем значение недавнего

    // узел на уровне

    a[l] = p;

    connectNodes(p.left, l + 1);

    connectNodes(p.right, l + 1);

}

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

static void connectNodesUtil(node root)

    // Инициализировать узлы на каждом уровне, чтобы обнулить

    for (int i = 0; i < 100; i++)

        a[i] = new node(-1);

          

    // Заполняет следующий левый указатель во всех узлах

    connectNodes(root, 0);

      

    // Давайте проверим значения следующих левых указателей

    System.out.println( "Following are populated leftNeighbour"

                        " pointers in the tree:");

              

    System.out.println( "leftNeighbour of " + root.data + 

                        " is " + (root.leftNeighbour != null

                                  root.leftNeighbour.data : -1));

                  

    System.out.println( "leftNeighbour of " + root.left.data + 

                        " is " + (root.left.leftNeighbour != null ?

                                  root.left.leftNeighbour.data : -1));

                  

    System.out.println( "leftNeighbour of " + root.right.data + 

                        " is " + (root.right.leftNeighbour != null

                                  root.right.leftNeighbour.data : -1) );

                  

    System.out.println( "leftNeighbour of " + root.left.left.data + 

                        " is " + (root.left.left.leftNeighbour != null

                                  root.left.left.leftNeighbour.data : -1));

}

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

public static void main(String args[])

{

  

    / * Построенное двоичное дерево

            10

            / /

        8 2

        /

        3

    * /

    node root = new node(10);

    root.left = new node(8);

    root.right = new node(2);

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

  

    connectNodesUtil(root);

}
}

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

Выход:

Following are populated leftNeighbour pointers in the tree:
leftNeighbour of 10 is -1
leftNeighbour of 8 is -1
leftNeighbour of 2 is 8
leftNeighbour of 3 is -1

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

Соедините все узлы с их левыми соседями в двоичном дереве

0.00 (0%) 0 votes