Рубрики

Соединяйте узлы на одном уровне, используя постоянное дополнительное пространство

Деревья

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

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

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

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

Рекурсивное решение
В методе 2 предыдущего поста мы прошли узлы в порядке предварительного заказа. Вместо обхода в порядке предварительного заказа (root, left, right), если мы пройдем узел nextRight до левого и правого потомка (root, nextRight, left), то мы можем убедиться, что все узлы на уровне i имеют значение nextRight. До уровня я + 1 узлов. Давайте рассмотрим следующий пример (тот же пример, что и в предыдущем посте ). Метод 2 завершается неудачно для правого потомка узла 4. В этом методе мы проверяем, что все узлы на уровне 4 (уровень 2) имеют значение nextRight, прежде чем мы попытаемся установить значение nextRight, равное 9. Поэтому, когда мы устанавливаем nextRight из 9, мы ищем нелистный узел на правой стороне узла 4 (getNextRight () делает это для нас).

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

С

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

void connectRecur(struct node* p);

struct node *getNextRight(struct node *p);

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

void connect (struct node *p)

{

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

    p->nextRight = NULL;

  

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

    connectRecur(p);

}

  
/ * Установить следующее право всех потомков р. Эта функция гарантирует, что
nextRight узлов ar уровня i устанавливается перед уровнями i + 1 узлов. * /

void connectRecur(struct node* p)

{

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

    if (!p)

       return;

  

    / * Перед установкой nextRight левого и правого потомка, установите nextRight

    дочерних узлов других узлов на том же уровне (потому что мы можем получить доступ

    потомки других узлов, использующих только nextRight p) * /

    if (p->nextRight != NULL)

       connectRecur(p->nextRight);

  

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

    if (p->left)

    {

       if (p->right)

       {

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

           p->right->nextRight = getNextRight(p);

       }

       else

           p->left->nextRight = getNextRight(p);

  

       / * Рекурсивный вызов для узлов следующего уровня. Обратите внимание, что мы звоним только

       для левого ребенка. Звонок для левого ребенка будет звонить для правого ребенка * /

       connectRecur(p->left);

    }

  

    / * Если оставленный дочерний элемент равен NULL, то первый узел следующего уровня будет либо

      p-> right или getNextRight (p) * /

    else if (p->right)

    {

        p->right->nextRight = getNextRight(p);

        connectRecur(p->right);

    }

    else

       connectRecur(getNextRight(p));

}

  
/ * Эта функция возвращает самого левого потомка узлов того же уровня, что и p.

   Эта функция используется для получения права справа от правого потомка p

   Если правый потомок p равен NULL, то это также можно использовать для левого потомка * /

struct node *getNextRight(struct node *p)

{

    struct node *temp = p->nextRight;

  

    / * Обходить узлы на уровне p, находить и возвращать

       первый дочерний узел первого узла * /

    while(temp != NULL)

    {

        if(temp->left != NULL)

            return temp->left;

        if(temp->right != NULL)

            return temp->right;

        temp = temp->nextRight;

    }

  

    // Если все узлы на уровне p являются листовыми узлами, тогда возвращаем NULL

    return NULL;

}

Джава

// Рекурсивная Java-программа для соединения узлов на одном уровне
// используя постоянное дополнительное пространство

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

class Node 

{

    int data;

    Node left, right, nextRight;

   

    Node(int item) 

    {

        data = item;

        left = right = nextRight = null;

    }

}

   

class BinaryTree 

{

    Node root;

   

    / * Установить следующее право всех потомков р. Эта функция гарантирует, что

       nextRight узлов ar уровня i устанавливается перед уровнями i + 1 узлов. * /

    void connectRecur(Node p) 

    {

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

        if (p == null)

            return;

   

        / * Перед установкой nextRight левого и правого потомка, установите nextRight

           дочерних узлов других узлов на том же уровне (потому что мы можем получить доступ

           потомки других узлов, использующих только nextRight p) * /

        if (p.nextRight != null)

            connectRecur(p.nextRight);

   

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

        if (p.left != null)

        {

            if (p.right != null) 

            {

                p.left.nextRight = p.right;

                p.right.nextRight = getNextRight(p);

            } 

            else

                p.left.nextRight = getNextRight(p);

   

            / * Рекурсивный вызов для узлов следующего уровня. Обратите внимание, что мы звоним только

             для левого ребенка. Звонок для левого ребенка будет звонить для правого ребенка * /

            connectRecur(p.left);

        }

           

        / * Если оставленный дочерний элемент равен NULL, то первый узел следующего уровня будет либо

         p-> right или getNextRight (p) * /

        else if (p.right != null) 

        {

            p.right.nextRight = getNextRight(p);

            connectRecur(p.right);

        } 

        else

            connectRecur(getNextRight(p));

    }

   

    / * Эта функция возвращает самого левого потомка узлов одновременно

       уровень как р. Эта функция используется для получения права справа от правого потомка p

       Если правый потомок p равен NULL, то это также можно использовать для

       левый ребенок * /

    Node getNextRight(Node p) 

    {

        Node temp = p.nextRight;

   

        / * Обходить узлы на уровне p, находить и возвращать

         первый дочерний узел первого узла * /

        while (temp != null) 

        {

            if (temp.left != null)

                return temp.left;

            if (temp.right != null)

                return temp.right;

            temp = temp.nextRight;

        }

   

        // Если все узлы на уровне p являются листовыми узлами, тогда возвращаем NULL

        return null;

    }

   

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

    public static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(10);

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

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

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

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

   

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

        tree.connectRecur(tree.root);

   

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

        int a = tree.root.nextRight != null ? 

                          tree.root.nextRight.data : -1;

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

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

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

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

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

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

        int e = tree.root.right.right.nextRight != null ? 

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

           

        // Теперь давайте напечатаем значения

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

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

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

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

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

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

                                                              " is " + d);

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

                                                              " is " + e);

    }

}

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

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 узлов ar уровня i устанавливается перед уровнями i + 1 узлов. * /

    public virtual void connectRecur(Node p)

    {

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

        if (p == null)

        {

            return;

        }

  

        / * Перед установкой nextRight левого и правого потомка, установите nextRight

           дочерних узлов других узлов на том же уровне (потому что мы можем получить доступ

           потомки других узлов, использующих только nextRight p) * /

        if (p.nextRight != null)

        {

            connectRecur(p.nextRight);

        }

  

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

        if (p.left != null)

        {

            if (p.right != null)

            {

                p.left.nextRight = p.right;

                p.right.nextRight = getNextRight(p);

            }

            else

            {

                p.left.nextRight = getNextRight(p);

            }

  

            / * Рекурсивный вызов для узлов следующего уровня. Обратите внимание, что мы звоним только

             для левого ребенка. Звонок для левого ребенка будет звонить для правого ребенка * /

            connectRecur(p.left);

        }

  

        / * Если оставленный дочерний элемент равен NULL, то первый узел следующего уровня будет либо

         p-> right или getNextRight (p) * /

        else if (p.right != null)

        {

            p.right.nextRight = getNextRight(p);

            connectRecur(p.right);

        }

        else

        {

            connectRecur(getNextRight(p));

        }

    }

  

    / * Эта функция возвращает самого левого потомка узлов одновременно

       уровень как р. Эта функция используется для получения права справа от правого потомка p

       Если правый потомок p равен NULL, то это также можно использовать для

       левый ребенок * /

    public virtual Node getNextRight(Node p)

    {

        Node temp = p.nextRight;

  

        / * Обходить узлы на уровне p, находить и возвращать

         первый дочерний узел первого узла * /

        while (temp != null)

        {

            if (temp.left != null)

            {

                return temp.left;

            }

            if (temp.right != null)

            {

                return temp.right;

            }

            temp = temp.nextRight;

        }

  

        // Если все узлы на уровне p являются листовыми узлами, тогда возвращаем NULL

        return null;

    }

  

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

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(10);

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

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

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

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

  

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

        tree.connectRecur(tree.root);

  

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

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

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

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

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

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

  

        // Теперь давайте напечатаем значения

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

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

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

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

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

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

    }

}

  

  // Этот код предоставлен 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 90
nextRight of 90 is -1

Итеративное решение
Рассмотренный выше рекурсивный подход может быть легко преобразован в итеративный. В итерационной версии мы используем вложенный цикл. Внешний цикл проходит через все уровни, а внутренний цикл проходит через все узлы на каждом уровне. Это решение использует постоянное пространство.

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;

    }

}; 

  
/ * Эта функция возвращает крайний левый
дочерний узел на том же уровне, что и p.
Эта функция используется, чтобы получить право
правильного ребенка р Если правильного ребенка
NULL, то это также может быть использовано для
левый ребенок * /
node *getNextRight(node *p) 
{ 

    node *temp = p->nextRight; 

  

    / * Обход узлов на уровне р

    и найти и вернуть первый

    первый дочерний узел * /

    while (temp != NULL) 

    { 

        if (temp->left != NULL) 

            return temp->left; 

        if (temp->right != NULL) 

            return temp->right; 

        temp = temp->nextRight; 

    } 

  

    // Если все узлы на уровне р

    // являются листовыми узлами и возвращаем NULL

    return NULL; 

} 

  
/ * Устанавливает nextRight всех узлов
дерева с корнем как p * /

void connectRecur(node* p) 

{ 

    node *temp; 

  

    if (!p) 

    return; 

  

    // Установить nextRight для root

    p->nextRight = NULL; 

  

    // устанавливаем nextRight всех уровней один за другим

    while (p != NULL) 

    { 

        node *q = p; 

  

        / * Соединить все дочерние узлы p и

        дочерние узлы всех других узлов в

        тот же уровень, что и p * /

        while (q != NULL) 

        { 

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

            // для левого ребенка р

            if (q->left) 

            { 

                // Если q имеет правильного потомка, то

                // правый ребенок - следующее право

                // р и нам также нужно установить

                // nextRight правого ребенка

                if (q->right) 

                    q->left->nextRight = q->right; 

                else

                    q->left->nextRight = getNextRight(q); 

            } 

  

            if (q->right) 

                q->right->nextRight = getNextRight(q); 

  

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

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

            q = q->nextRight; 

        } 

  

        // начинаем с первого

        // узел следующего уровня

        if (p->left) 

            p = p->left; 

        else if (p->right) 

            p = p->right; 

        else

            p = getNextRight(p); 

    } 

} 

  

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

int main() 

{ 

  

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

            10

            / /

        8 2

        / /

    3 90

    * /

    node *root = new node(10); 

    root->left = new node(8); 

    root->right = new node(2); 

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

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

  

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

    connectRecur(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;

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

        << (root->right->right->nextRight? root->right->right->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;

};

  
/ * Эта функция возвращает самого левого потомка узлов того же уровня, что и p.

   Эта функция используется для получения права справа от правого потомка p

   Если правый потомок равен NULL, то это также можно использовать для левого потомка * /

struct node *getNextRight(struct node *p)

{

    struct node *temp = p->nextRight;

  

    / * Обходить узлы на уровне p, находить и возвращать

       первый дочерний узел первого узла * /

    while (temp != NULL)

    {

        if (temp->left != NULL)

            return temp->left;

        if (temp->right != NULL)

            return temp->right;

        temp = temp->nextRight;

    }

  

    // Если все узлы на уровне p являются листовыми узлами, тогда возвращаем NULL

    return NULL;

}

  
/ * Устанавливает nextRight всех узлов дерева с корнем как p * /

void connect(struct node* p)

{

    struct node *temp;

  

    if (!p)

      return;

  

    // Установить nextRight для root

    p->nextRight = NULL;

  

    // устанавливаем nextRight всех уровней один за другим

    while (p != NULL)

    {

        struct node *q = p;

  

        / * Соединить все дочерние узлы p и дочерние узлы всех других узлов

          на том же уровне, что и р * /

        while (q != NULL)

        {

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

            if (q->left)

            {

                // Если q имеет правильного потомка, то правильным потомком является nextRight

                // p и нам также нужно установить nextRight правого потомка

                if (q->right)

                    q->left->nextRight = q->right;

                else

                    q->left->nextRight = getNextRight(q);

            }

  

            if (q->right)

                q->right->nextRight = getNextRight(q);

  

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

            q = q->nextRight;

        }

  

        // начать с первого узла следующего уровня

        if (p->left)

           p = p->left;

        else if (p->right)

           p = p->right;

        else

           p = getNextRight(p);

    }

}

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

   данные даны и 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 90

    * /

    struct node *root = newnode(10);

    root->left        = newnode(8);

    root->right       = newnode(2);

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

    root->right->right       = newnode(90);

  

    // Заполняет указатель 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);

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

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

  

    getchar();

    return 0;

}

Джава

// Итеративная Java-программа для соединения узлов на одном уровне
// используя постоянное дополнительное пространство

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

class Node 

{

    int data;

    Node left, right, nextRight;

   

    Node(int item) 

    {

        data = item;

        left = right = nextRight = null;

    }

}

   

class BinaryTree 

{

    Node root;

   

    / * Эта функция возвращает самого левого потомка узлов на том же уровне

       как стр. Эта функция используется для получения права справа от правого потомка p

       Если правый потомок равен NULL, то это также может быть использовано для

       оставленный ребенок * /

    Node getNextRight(Node p) 

    {

        Node temp = p.nextRight;

   

        / * Обходить узлы на уровне p, находить и возвращать

           первый дочерний узел первого узла * /

        while (temp != null) 

        {

            if (temp.left != null)

                return temp.left;

            if (temp.right != null)

                return temp.right;

            temp = temp.nextRight;

        }

   

        // Если все узлы на уровне p являются листовыми узлами, тогда возвращаем NULL

        return null;

    }

   

    / * Устанавливает nextRight всех узлов дерева с корнем как p * /

    void connect(Node p) {

        Node temp = null;

   

        if (p == null)

            return;

   

        // Установить nextRight для root

        p.nextRight = null;

   

        // устанавливаем nextRight всех уровней один за другим

        while (p != null) 

        {

            Node q = p;

   

            / * Соединить все дочерние узлы p и дочерние узлы всех остальных

               узлы на том же уровне, что и p * /

            while (q != null) 

            {

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

                if (q.left != null) 

                {

                   

                    // Если q имеет правильного потомка, то правильным потомком является nextRight

                    // p и нам также нужно установить nextRight правого потомка

                    if (q.right != null)

                        q.left.nextRight = q.right;

                    else

                        q.left.nextRight = getNextRight(q);

                }

   

                if (q.right != null)

                    q.right.nextRight = getNextRight(q);

   

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

                q = q.nextRight;

            }

   

            // начать с первого узла следующего уровня

            if (p.left != null)

                p = p.left;

            else if (p.right != null)

                p = p.right;

            else

                p = getNextRight(p);

        }

    }

      

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

    public static void main(String args[]) 

    {

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

                 10

               / /

             8 2

           / /

         3 90

        * /

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(10);

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

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

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

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

   

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

        tree.connect(tree.root);

           

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

        int a = tree.root.nextRight != null ? 

                                     tree.root.nextRight.data : -1;

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

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

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

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

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

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

        int e = tree.root.right.right.nextRight != null ? 

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

           

        // Теперь давайте напечатаем значения

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

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

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

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

                                                       + " is " + b);

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

                                                           " is " + c);

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

                                                            " is " + d);

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

                                                             " is " + e);

    }

}

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

python3

# Итеративная программа Python для соединения узлов
# на том же уровне, используя постоянное дополнительное пространство

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

class newnode:

    def __init__(self,data):

        self.data = data 

        self.left = None

        self.right = None

        self.nextRight = None

          
# Эта функция возвращает самого левого потомка
# узлы на том же уровне, что и p. Эта функция
# используется для получения права справа от правого потомка p
# Если правильное дитя None, то это также может
# использоваться для левого ребенка

def getNextRight(p):

    temp = p.nextRight 

  

    # Пройти узлы на уровне р и найти

    # и вернуть первый дочерний узел первого узла

    while (temp != None):

        if (temp.left != None):

            return temp.left 

        if (temp.right != None): 

            return temp.right 

        temp = temp.nextRight

  

    # Если все узлы на уровне р

    # листовые узлы затем возвращают None

    return None

  
# Устанавливает nextRight всех узлов дерева
# с корнем как p

def connect(p):

    temp = None

  

    if (not p): 

        return

  

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

    p.nextRight = None

  

    # установить nextRight всех уровней один за другим

    while (p != None):

        q = p 

  

        # Соединить все дочерние узлы p и

        # дочерние узлы всех остальных узлов

        # на том же уровне, что и p

        while (q != None):

              

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

            # р оставил ребенка

            if (q.left):

                  

                # Если q имеет правильного потомка, то право

                # child is nextRight of p и мы

                # также нужно установить nextRight из

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

                if (q.right): 

                    q.left.nextRight = q.right 

                else:

                    q.left.nextRight = getNextRight(q)

  

            if (q.right):

                q.right.nextRight = getNextRight(q) 

  

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

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

            q = q.nextRight

  

        # начать с первого узла

        № следующего уровня

        if (p.left):

            p = p.left 

        elif (p.right):

            p = p.right 

        else:

            p = getNextRight(p)

  
Код водителя

if __name__ == '__main__':

  

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

    № 10

    # / /

    № 8 2

    # / /

    № 3 90

    root = newnode(10) 

    root.left     = newnode(8) 

    root.right     = newnode(2) 

    root.left.left = newnode(3) 

    root.right.right     = newnode(90) 

  

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

    connect(root) 

  

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

    print("Following are populated nextRight "

          "pointers in the tree (-1 is printed " 

          "if there is no nextRight) \n") 

    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)

    print("nextRight of", root.right.right.data,

                                "is", end = " ") 

    if root.right.right.nextRight:

        print(root.right.right.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;

  

    / * Эта функция возвращает самого левого потомка узлов на том же уровне

       как стр. Эта функция используется для получения права справа от правого потомка p

       Если правый потомок равен NULL, то это также может быть использовано для

       оставленный ребенок * /

    public virtual Node getNextRight(Node p)

    {

        Node temp = p.nextRight;

  

        / * Обходить узлы на уровне p, находить и возвращать

           первый дочерний узел первого узла * /

        while (temp != null)

        {

            if (temp.left != null)

            {

                return temp.left;

            }

            if (temp.right != null)

            {

                return temp.right;

            }

            temp = temp.nextRight;

        }

  

        // Если все узлы на уровне p являются листовыми узлами, тогда возвращаем NULL

        return null;

    }

  

    / * Устанавливает nextRight всех узлов дерева с корнем как p * /

    public virtual void connect(Node p)

    {

        Node temp = null;

  

        if (p == null)

        {

            return;

        }

  

        // Установить nextRight для root

        p.nextRight = null;

  

        // устанавливаем nextRight всех уровней один за другим

        while (p != null)

        {

            Node q = p;

  

            / * Соединить все дочерние узлы p и дочерние узлы всех остальных

               узлы на том же уровне, что и p * /

            while (q != null)

            {

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

                if (q.left != null)

                {

  

                    // Если q имеет правильного потомка, то правильным потомком является nextRight

                    // p и нам также нужно установить nextRight правого потомка

                    if (q.right != null)

                    {

                        q.left.nextRight = q.right;

                    }

                    else

                    {

                        q.left.nextRight = getNextRight(q);

                    }

                }

  

                if (q.right != null)

                {

                    q.right.nextRight = getNextRight(q);

                }

  

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

                q = q.nextRight;

            }

  

            // начать с первого узла следующего уровня

            if (p.left != null)

            {

                p = p.left;

            }

            else if (p.right != null)

            {

                p = p.right;

            }

            else

            {

                p = getNextRight(p);

            }

        }

    }

  

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

    public static void Main(string[] args)

    {

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

                 10

               / /

             8 2

           / /

         3 90

        * /

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(10);

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

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

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

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

  

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

        tree.connect(tree.root);

  

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

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

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

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

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

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

  

        // Теперь давайте напечатаем значения

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

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

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

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

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

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

    }

}

  

  // Этот код предоставлен 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 90
nextRight of 90 is -1

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

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

Соединяйте узлы на одном уровне, используя постоянное дополнительное пространство

0.00 (0%) 0 votes