Рубрики

Заполнить преемник Inorder для всех узлов

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

struct node

{

  int data;

  struct node* left;

  struct node* right;

  struct node* next;

}

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

Решение (использовать обратный обход Inorder)
Пройдите заданное дерево в обратном порядке и следите за ранее посещенным узлом. Когда узел посещается, назначьте ранее посещенный узел как следующий.

C ++

// C ++ программа для заполнения заказа
// обход всех узлов
#include<bits/stdc++.h>

using namespace std;

  

class node 

    public:

    int data; 

    node *left; 

    node *right; 

    node *next; 

}; 

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

void populateNext(node* p) 

    // Первый посещенный узел будет

    // самый правый узел, следующий за самым правым

    // узел будет NULL

    static node *next = NULL; 

  

    if (p) 

    

        // Сначала устанавливаем следующий указатель

        // в правом поддереве

        populateNext(p->right); 

  

        // Установить следующий как посещенный ранее

        // узел в обратном порядке

        p->next = next; 

  

        // Изменить предыдущий узел

        next = p; 

  

        // Наконец, установите следующий указатель в

        // левое поддерево

        populateNext(p->left); 

    

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

node* newnode(int data) 

    node* Node = new node();

    Node->data = data; 

    Node->left = NULL; 

    Node->right = NULL; 

    Node->next = NULL; 

  

    return(Node); 

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

int main() 

  

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

            10

            / /

        8 12

        /

    3

    * /

    node *root = newnode(10); 

    root->left = newnode(8); 

    root->right = newnode(12); 

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

  

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

    populateNext(root); 

  

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

    node *ptr = root->left->left; 

    while(ptr) 

    

        // -1 печатается, если преемника нет

        cout << "Next of " << ptr->data << " is "

             << (ptr->next? ptr->next->data: -1) 

             << endl; 

        ptr = ptr->next; 

    

  

    return 0; 

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

С

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

  

struct node

{

    int data;

    struct node *left;

    struct node *right;

    struct node *next;

};

  
/ * Установить следующий из p и всех потомков p, пройдя их в обратном порядке * /

void populateNext(struct node* p)

{

    // Первый посещенный узел будет самым правым узлом

    // следующий самый правый узел будет NULL

    static struct node *next = NULL;

  

    if (p)

    {

        // Сначала устанавливаем следующий указатель в правом поддереве

        populateNext(p->right);

  

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

        p->next = next;

  

        // Изменить предыдущий узел

        next = p;

  

        // Наконец, установить следующий указатель в левом поддереве

        populateNext(p->left);

    }

}

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

   данные даны и 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->next = NULL;

  

    return(node);

}

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

int main()

{

  

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

              10

            / /

          8 12

        /

      3

    * /

    struct node *root = newnode(10);

    root->left        = newnode(8);

    root->right       = newnode(12);

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

  

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

    populateNext(root);

  

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

    struct node *ptr = root->left->left;

    while(ptr)

    {

        // -1 печатается, если преемника нет

        printf("Next of %d is %d \n", ptr->data, ptr->next? ptr->next->data: -1);

        ptr = ptr->next;

    }

  

    return 0;

}

Джава

// Java-программа для заполнения обхода всех узлов

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

class Node 

{

    int data;

    Node left, right, next;

   

    Node(int item) 

    {

        data = item;

        left = right = next = null;

    }

}

   

class BinaryTree 

{

    Node root;

    static Node next = null;

   

    / * Установить следующий из p и всех потомков p, пройдя их в

       обратный порядок * /

    void populateNext(Node node) 

    {

        // Первый посещенный узел будет самым правым узлом

        // следующий самый правый узел будет NULL

        if (node != null

        {

            // Сначала устанавливаем следующий указатель в правом поддереве

            populateNext(node.right);

   

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

            node.next = next;

   

            // Изменить предыдущий узел

            next = node;

   

            // Наконец, установить следующий указатель в левом поддереве

            populateNext(node.left);

        }

    }

   

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

    public static void main(String args[]) 

    {

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

            10

           / /

          8 12

         /

        3 * /

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(10);

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

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

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

   

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

        tree.populateNext(tree.root);

   

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

        Node ptr = tree.root.left.left;

        while (ptr != null

        {

            // -1 печатается, если преемника нет

            int print = ptr.next != null ? ptr.next.data : -1;

            System.out.println("Next of " + ptr.data + " is: " + print);

            ptr = ptr.next;

        }

    }

}

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

python3

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

  
# Узел дерева

class Node: 

    def __init__(self, data): 

        self.data = data 

        self.left = None

        self.right = None

        self.next = None

          
# Первый посещенный узел будет
# самый правый узел рядом с
# самый правый узел будет Нет

next = None

  
# Установить следующий из р и всех потомков р
# обходя их в обратном порядке

def populateNext(p):

  

    global next

  

    if (p != None):

      

        # Сначала установите следующий указатель

        # в правом поддереве

        populateNext(p.right)

  

        # Установить следующий как ранее посещенный узел

        # в обратном порядке

        p.next = next

  

        # Изменить предыдущий для последующего узла

        next = p

  

        # Наконец, установите следующий указатель

        # в левом поддереве

        populateNext(p.left)

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

def newnode(data):

  

    node = Node(0)

    node.data = data

    node.left = None

    node.right = None

    node.next = None

  

    return(node)

  
Код водителя

  
# Коническое двоичное дерево
№ 10
# / /
# 8 12
# /
№ 3

root = newnode(10)

root.left = newnode(8)

root.right = newnode(12)

root.left.left = newnode(3)

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

p = populateNext(root)

  
# Давайте посмотрим на заполненные значения

ptr = root.left.left

while(ptr != None):

      

    out = 0

    if(ptr.next != None):

        out = ptr.next.data

    else:

        out = -1

          

    # -1 печатается, если нет преемника

    print("Next of", ptr.data, "is", out)

    ptr = ptr.next

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

C #

// C # программа для заполнения обхода всех узлов

using System; 

  

    

class BinaryTree 

{

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

    class Node 

    {

       public int data;

       public Node left, right, next;

    

      public Node(int item) 

     {

          data = item;

          left = right = next = null;

      }

    }

    Node root;

    static Node next = null;

    

    / * Установить следующий из p и всех потомков p, пройдя их в

       обратный порядок * /

    void populateNext(Node node) 

    {

        // Первый посещенный узел будет самым правым узлом

        // следующий самый правый узел будет NULL

        if (node != null

        {

            // Сначала устанавливаем следующий указатель в правом поддереве

            populateNext(node.right);

    

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

            node.next = next;

    

            // Изменить предыдущий узел

            next = node;

    

            // Наконец, установить следующий указатель в левом поддереве

            populateNext(node.left);

        }

    }

    

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

     static public void Main(String []args )

    {

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

            10

           / /

          8 12

         /

        3 * /

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(10);

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

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

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

    

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

        tree.populateNext(tree.root);

    

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

        Node ptr = tree.root.left.left;

        while (ptr != null

        {

            // -1 печатается, если преемника нет

            int print = ptr.next != null ? ptr.next.data : -1;

            Console.WriteLine("Next of " + ptr.data + " is: " + print);

            ptr = ptr.next;

        }

    }

}

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


Выход:

Next of 3 is 8
Next of 8 is 10
Next of 10 is 12
Next of 12 is -1

Мы можем избежать использования статической переменной, передавая параметр next в качестве параметра.

C ++

// Реализация, которая не использует статическую переменную

  
// Оболочка над populateNextRecur

void populateNext(node *root) 

    // Первый посещенный узел будет самым правым узлом

    // следующий самый правый узел будет NULL

    node *next = NULL; 

  

    populateNextRecur(root, &next); 

  
/ * Установить следующий из всех потомков р по
прохождение их в обратном порядке *

void populateNextRecur(node* p, node **next_ref) 

    if (p) 

    

        // Сначала устанавливаем следующий указатель в правом поддереве

        populateNextRecur(p->right, next_ref); 

  

        // Установить следующий как посещенный ранее

        // узел в обратном порядке

        p->next = *next_ref; 

  

        // Изменить предыдущий узел

        *next_ref = p; 

  

        // Наконец, установить следующий указатель в правом поддереве

        populateNextRecur(p->left, next_ref); 

    

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

С

// Реализация, которая не использует статическую переменную

  
// Оболочка над populateNextRecur

void populateNext(struct node *root)

{

    // Первый посещенный узел будет самым правым узлом

    // следующий самый правый узел будет NULL

    struct node *next = NULL;

  

    populateNextRecur(root, &next);

}

  
/ * Установить следующий из всех потомков р, пройдя их в обратном порядке * /

void populateNextRecur(struct node* p, struct node **next_ref)

{

    if (p)

    {

        // Сначала устанавливаем следующий указатель в правом поддереве

        populateNextRecur(p->right, next_ref);

  

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

        p->next = *next_ref;

  

        // Изменить предыдущий узел

        *next_ref = p;

  

        // Наконец, установить следующий указатель в правом поддереве

        populateNextRecur(p->left, next_ref);

    }

}

Джава

// Оболочка над populateNextRecur

    void populateNext(Node node) {

  

        // Первый посещенный узел будет самым правым узлом

        // следующий самый правый узел будет NULL

        populateNextRecur(node, next);

    }

  

    / * Установить следующий из всех потомков р, пройдя их в обратном порядке * /

    void populateNextRecur(Node p, Node next_ref) {

        if (p != null) {

              

           // Сначала устанавливаем следующий указатель в правом поддереве

            populateNextRecur(p.right, next_ref);

  

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

            p.next = next_ref;

  

            // Изменить предыдущий узел

            next_ref = p;

  

            // Наконец, установить следующий указатель в правом поддереве

            populateNextRecur(p.left, next_ref);

        }

    }

C #

      

      

    // Оболочка над populateNextRecur

    void populateNext(Node node)

    {

  

        // Первый посещенный узел будет самым правым узлом

        // следующий самый правый узел будет NULL

        populateNextRecur(node, next);

    }

  

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

    прохождение их в обратном порядке *

    void populateNextRecur(Node p, Node next_ref)

    {

        if (p != null)

        {

              

            // Сначала устанавливаем следующий указатель в правом поддереве

            populateNextRecur(p.right, next_ref);

  

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

            p.next = next_ref;

  

            // Изменить предыдущий узел

            next_ref = p;

  

            // Наконец, установить следующий указатель в правом поддереве

            populateNextRecur(p.left, next_ref);

        }

    }

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


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

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

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

Заполнить преемник Inorder для всех узлов

0.00 (0%) 0 votes