Рубрики

Подключите узлы на одном уровне

Напишите функцию для соединения всех смежных узлов на одном уровне в двоичном дереве. Структура данного узла двоичного дерева выглядит следующим образом.

struct node{

  int data;

  struct node* left;

  struct node* right;

  struct node* nextRight;  

}

Изначально все указатели nextRight указывают на значения мусора. Ваша функция должна установить эти указатели так, чтобы они указывали следующий справа для каждого узла.

Пример:

Input Tree
       A
      / \
     B   C
    / \   \
   D   E   F


Output Tree
       A--->NULL
      / \
     B-->C-->NULL
    / \   \
   D-->E-->F-->NULL

Метод 1 (Расширить уровень обхода порядка или BFS)
Рассмотрим метод 2 прохождения уровня порядка . Способ 2 может быть легко расширен для подключения узлов одного уровня. Мы можем расширить записи очереди, чтобы они также содержали уровень узлов, который равен 0 для root, 1 для дочерних элементов root и так далее. Таким образом, узел очереди теперь будет содержать указатель на узел дерева и целочисленный уровень. Когда мы ставим в очередь узел, мы гарантируем, что в очереди устанавливается правильное значение уровня для узла. Чтобы установить nextRight, для каждого узла N мы исключаем следующий узел из очереди, если номер уровня следующего узла такой же, мы устанавливаем nextRight of N в качестве адреса удаленного узла, в противном случае мы устанавливаем nextRight of N в качестве NULL.

Пожалуйста, обратитесь к подключенным узлам на том же уровне (Level Order Traversal) для реализации.

Сложность времени: O (n)

Метод 2 (Расширение обхода предзаказа)
Этот подход работает только для Полных Двоичных Деревьев . В этом методе мы устанавливаем nextRight в режиме Pre Order, чтобы убедиться, что nextRight родительского объекта установлено перед его дочерними элементами. Когда мы находимся в узле p, мы устанавливаем nextRight его левого и правого потомков. Поскольку дерево является полным деревом, nextRight левого потомка p (p-> left-> nextRight) всегда будет правым потомком p, а nextRight правого потомка p (p-> right-> nextRight) всегда будет дочерним от p nextRight (если p не самый правый узел на своем уровне). Если p — самый правый узел, тогда nextRight правого потомка p будет NULL.

C ++

// Программа CPP для соединения узлов
// на том же уровне, используя расширенный
// предварительный заказ обхода
#include<bits/stdc++.h> 
#include<iostream>

using namespace std; 

  

class node 

    public:

    int data; 

    node* left; 

    node* right; 

    node *nextRight; 

      

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

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

    node(int data)

    {

        this->data = data;

        this->left = NULL;

        this->right = NULL;

        this->nextRight = NULL;

    }

}; 

  

void connectRecur(node* p); 

  
// Устанавливает nextRight из
// root и вызывает connectRecur ()
// для других узлов

void connect(node *p) 

    // Устанавливаем nextRight для root

    p->nextRight = NULL; 

  

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

    // (кроме корня)

    connectRecur(p); 

  
/ * Установить следующее право всех потомков р.
Предположение: p - двоичное дерево с конкуренцией * /

void connectRecur(node* p) 

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

    if (!p) 

        return

      

    // Установить указатель nextRight для левого потомка p

    if (p->left) 

        p->left->nextRight = p->right; 

      

    // Установить указатель nextRight

    // для правого потомка p p-> nextRight

    // будет НЕДЕЙСТВИТЕЛЕН, если p является правильным

    // большинство детей на своем уровне

    if (p->right) 

        p->right->nextRight = (p->nextRight)? p->nextRight->left: NULL; 

      

    // Установить nextRight для других

    // узлы в порядке предзаказа

    connectRecur(p->left); 

    connectRecur(p->right); 

  

  

  
/ * Код водителя * /

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); 

      

    // Заполняет указатель nextRight во всех узлах

    connect(root); 

      

    // Давайте проверим значения

    // из указателей nextRight

    cout<<"Following are populated nextRight pointers in the tree"

        " (-1 is printed if there is no nextRight)\n"

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

        << (root->nextRight? root->nextRight->data: -1) <<endl; 

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

        << (root->left->nextRight? root->left->nextRight->data: -1) <<endl;

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

        << (root->right->nextRight? root->right->nextRight->data: -1) <<endl;

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

        << (root->left->left->nextRight? root->left->left->nextRight->data: -1) <<endl;

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

// C-программа для соединения узлов на одном уровне с использованием расширенного
// предварительный заказ обхода
#include <stdio.h>
#include <stdlib.h>

  

struct node

{

  int data;

  struct node *left;

  struct node *right;

  struct node *nextRight;

};

  

void connectRecur(struct node* p);

  
// Устанавливает nextRight корня и вызывает connectRecur ()
// для других узлов

void connect (struct node *p)

{

    // Устанавливаем nextRight для root

    p->nextRight = NULL;

  

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

    // (кроме корня)

    connectRecur(p);

}

  
/ * Установить следующее право всех потомков р.

   Предположение: p - двоичное дерево с конкуренцией * /

void connectRecur(struct node* p)

{

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

  if (!p)

    return;

  

  // Установить указатель nextRight для левого потомка p

  if (p->left)

    p->left->nextRight = p->right;

  

  // Установить указатель nextRight для правого потомка p

  // p-> nextRight будет NULL, если p является правильным

  // большинство детей на своем уровне

  if (p->right)

    p->right->nextRight = (p->nextRight)? p->nextRight->left: NULL;

  

  // Устанавливаем nextRight для других узлов в порядке предварительного заказа

  connectRecur(p->left);

  connectRecur(p->right);

}

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Вспомогательная функция, которая выделяет новый узел с

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

struct node* newnode(int data)

{

  struct node* node = (struct node*)

                       malloc(sizeof(struct node));

  node->data = data;

  node->left = NULL;

  node->right = NULL;

  node->nextRight = NULL;

  

  return(node);

}

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

int main()

{

  

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

            10

          / /

        8 2

      /

    3

  * /

  struct node *root = newnode(10);

  root->left        = newnode(8);

  root->right       = newnode(2);

  root->left->left  = newnode(3);

  

  // Заполняет указатель nextRight во всех узлах

  connect(root);

  

  // Давайте проверим значения указателей nextRight

  printf("Following are populated nextRight pointers in the tree "

    "(-1 is printed if there is no nextRight) \n");

  printf("nextRight of %d is %d \n", root->data,

   root->nextRight? root->nextRight->data: -1);

  printf("nextRight of %d is %d \n", root->left->data,

   root->left->nextRight? root->left->nextRight->data: -1);

  printf("nextRight of %d is %d \n", root->right->data,

   root->right->nextRight? root->right->nextRight->data: -1);

  printf("nextRight of %d is %d \n", root->left->left->data,

   root->left->left->nextRight? root->left->left->nextRight->data: -1);

  return 0;

}

Джава

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

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

class Node 

{

    int data;

    Node left, right, nextRight;

   

    Node(int item) 

    {

        data = item;

        left = right = nextRight = null;

    }

}

   

class BinaryTree 

{

    Node root;

   

    // Устанавливает nextRight корня и вызывает connectRecur ()

    // для других узлов

    void connect(Node p) 

    {

   

        // Устанавливаем nextRight для root

        p.nextRight = null;

   

        // Установить следующее право для остальных узлов (другое

        // чем корень)

        connectRecur(p);

    }

   

    / * Установить следующее право всех потомков р.

       Предположение: p - двоичное дерево с конкуренцией * /

    void connectRecur(Node p) 

    {

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

        if (p == null)

            return;

   

        // Установить указатель nextRight для левого потомка p

        if (p.left != null)

            p.left.nextRight = p.right;

   

        // Установить указатель nextRight для правого потомка p

        // p-> nextRight будет NULL, если p - самый правый дочерний элемент

        // на своем уровне

        if (p.right != null

            p.right.nextRight = (p.nextRight != null) ? 

                                         p.nextRight.left : null;

   

        // Устанавливаем nextRight для других узлов в порядке предварительного заказа

        connectRecur(p.left);

        connectRecur(p.right);

    }

   

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

    public static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

          

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

             10

            / /

          8 2

         /

        3

        * /

        tree.root = new Node(10);

        tree.root.left = new Node(8);

        tree.root.right = new Node(2);

        tree.root.left.left = new Node(3);

   

        // Заполняет указатель nextRight во всех узлах

        tree.connect(tree.root);

   

        // Давайте проверим значения указателей nextRight

        System.out.println("Following are populated nextRight pointers in "

                + "the tree" + "(-1 is printed if there is no nextRight)");

        int a = tree.root.nextRight != null ? tree.root.nextRight.data : -1;

        System.out.println("nextRight of " + tree.root.data + " is "

                + a);

        int b = tree.root.left.nextRight != null

                                    tree.root.left.nextRight.data : -1;

        System.out.println("nextRight of " + tree.root.left.data + " is "

                + b);

        int c = tree.root.right.nextRight != null

                                   tree.root.right.nextRight.data : -1;

        System.out.println("nextRight of " + tree.root.right.data + " is "

                + c);

        int d = tree.root.left.left.nextRight != null

                              tree.root.left.left.nextRight.data : -1;

        System.out.println("nextRight of " + tree.root.left.left.data + " is "

                + d); 

    }

}

   
// Этот код предоставлен Mayank Jaiswal

python3

# Python3 программа для подключения узлов одновременно
# уровень с использованием расширенного обхода предварительного заказа

  

class newnode:

    def __init__(self, data):

        self.data = data

        self.left = self.right = self.nextRight = None

          
# Устанавливает nextRight от root и вызывает
# connectRecur () для других узлов

def connect (p):

      

    # Установите nextRight для root

    p.nextRight = None

  

    # Установите следующее право на отдых

    # узлы (кроме корневых)

    connectRecur(p)

  
# Установить следующее право всех потомков р.
# Предположение: p - двоичное дерево

def connectRecur(p):

      

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

    if (not p):

        return

      

    # Установить указатель nextRight для p

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

    if (p.left): 

        p.left.nextRight = p.right 

      

    # Установить указатель nextRight для права p

    # child p.nextRight будет None, если p

    # самый правый ребенок на своем уровне

    if (p.right):

        if p.nextRight:

            p.right.nextRight = p.nextRight.left

        else:

            p.right.nextRight = None

      

    # Установите nextRight для других узлов в

    # предзаказ мода

    connectRecur(p.left) 

    connectRecur(p.right)

  
Код водителя

if __name__ == '__main__':

  

    # Построенное двоичное дерево

    № 10

    # / /

    № 8 2

    # /

    № 3

    root = newnode(10

    root.left     = newnode(8

    root.right     = newnode(2

    root.left.left = newnode(3

  

    # Заполняет указатель nextRight во всех узлах

    connect(root) 

  

    # Давайте проверим значения указателей nextRight

    print("Following are populated nextRight"

          "pointers in the tree (-1 is printed",

                    "if there is no nextRight)")

    print("nextRight of", root.data, "is ", end = "")

    if root.nextRight:

        print(root.nextRight.data)

    else:

        print(-1)

    print("nextRight of", root.left.data, "is ", end = "") 

    if root.left.nextRight:

        print(root.left.nextRight.data)

    else:

        print(-1)

    print("nextRight of", root.right.data, "is ", end = "") 

    if root.right.nextRight:

        print(root.right.nextRight.data)

    else:

        print(-1)

    print("nextRight of", root.left.left.data, "is ", end = "") 

    if root.left.left.nextRight:

        print(root.left.left.nextRight.data)

    else:

        print(-1)

  
# Этот код предоставлен PranchalK

C #

using System;

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

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

public class Node

{

    public int data;

    public Node left, right, nextRight;

  

    public Node(int item)

    {

        data = item;

        left = right = nextRight = null;

    }

}

  

public class BinaryTree

{

    public Node root;

  

    // Устанавливает nextRight корня и вызывает connectRecur ()

    // для других узлов

    public virtual void connect(Node p)

    {

  

        // Устанавливаем nextRight для root

        p.nextRight = null;

  

        // Установить следующее право для остальных узлов (другое

        // чем корень)

        connectRecur(p);

    }

  

    / * Установить следующее право всех потомков р.

       Предположение: p - двоичное дерево с конкуренцией * /

    public virtual void connectRecur(Node p)

    {

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

        if (p == null)

        {

            return;

        }

  

        // Установить указатель nextRight для левого потомка p

        if (p.left != null)

        {

            p.left.nextRight = p.right;

        }

  

        // Установить указатель nextRight для правого потомка p

        // p-> nextRight будет NULL, если p - самый правый дочерний элемент

        // на своем уровне

        if (p.right != null)

        {

            p.right.nextRight = (p.nextRight != null) ? p.nextRight.left : null;

        }

  

        // Устанавливаем nextRight для других узлов в порядке предварительного заказа

        connectRecur(p.left);

        connectRecur(p.right);

    }

  

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

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

  

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

             10

            / /

          8 2

         /

        3

        * /

        tree.root = new Node(10);

        tree.root.left = new Node(8);

        tree.root.right = new Node(2);

        tree.root.left.left = new Node(3);

  

        // Заполняет указатель nextRight во всех узлах

        tree.connect(tree.root);

  

        // Давайте проверим значения указателей nextRight

        Console.WriteLine("Following are populated nextRight pointers in " + "the tree" + "(-1 is printed if there is no nextRight)");

        int a = tree.root.nextRight != null ? tree.root.nextRight.data : -1;

        Console.WriteLine("nextRight of " + tree.root.data + " is " + a);

        int b = tree.root.left.nextRight != null ? tree.root.left.nextRight.data : -1;

        Console.WriteLine("nextRight of " + tree.root.left.data + " is " + b);

        int c = tree.root.right.nextRight != null ? tree.root.right.nextRight.data : -1;

        Console.WriteLine("nextRight of " + tree.root.right.data + " is " + c);

        int d = tree.root.left.left.nextRight != null ? tree.root.left.left.nextRight.data : -1;

        Console.WriteLine("nextRight of " + tree.root.left.left.data + " is " + d);

    }

}

  

  // Этот код предоставлен Shrikant13


Выход:

Following are populated nextRight pointers in the tree(-1 is printed if there is no nextRight)
nextRight of 10 is -1
nextRight of 8 is 2
nextRight of 2 is -1
nextRight of 3 is -1

Спасибо Дханье за предложенный подход.

Сложность времени: O (n)

Почему метод 2 не работает для деревьев, которые не являются полными двоичными деревьями?
Давайте рассмотрим следующее дерево в качестве примера. В методе 2 мы устанавливаем указатель nextRight в порядке предварительного заказа. Когда мы находимся в узле 4, мы устанавливаем nextRight его дочерних элементов, которые равны 8 и 9 (nextRight из 4 уже установлен как узел 5). nextRight of 8 будет просто установлено как 9, но nextRight of 9 будет установлено как NULL, что неверно. Мы не можем установить правильный nextRight, потому что когда мы устанавливаем nextRight равным 9, у нас есть только nextRight узла 4 и предки узла 4, у нас нет nextRight узлов в правом поддереве корня.

            1
          /    \
        2        3
       / \      /  \
      4   5    6    7
     / \           / \  
    8   9        10   11

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

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

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

Подключите узлы на одном уровне

0.00 (0%) 0 votes