Рубрики

Сумма узлов зеркального отображения полного бинарного дерева по порядку

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

Примеры:

Input:

Output:
20
51
19
10
Inorder traversal of the left sub-tree of the given tree is 4 23 11 5.
Adding the mirror nodes,
4 + 16 = 20
23 + 28 = 51
11 + 8 = 19
5 + 5 = 10

Подход: мы будем использовать 2 указателя для поддержки 2 узлов, которые являются зеркальным отображением друг друга. Итак, давайте возьмем root1 и root2 2 узла зеркального отображения. Теперь левый потомок root1 и правый потомок root2 будут зеркальным отображением друг друга. Мы передадим эти два узла (root1-> left и root2-> right) для следующего рекурсивного вызова. Так как мы должны пройти по порядку, поэтому, как только левое поддерево пройдено, мы печатаем текущие корневые данные, а затем переходим правое поддерево. Аналогично для правого поддерева, поэтому правый дочерний элемент root1 и левый дочерний элемент root2 будут зеркальным отображением друг друга. Мы передадим эти два узла (root1-> right и root2-> left) для следующего рекурсивного вызова.

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

C ++

// C ++ реализация подхода
#include <iostream>

using namespace std;

typedef struct node {

  

    // структура для хранения данных и ссылок на

    // его левый и правый ребенок

    int data;

    struct node* l;

    struct node* r;

    node(int d)

    {

  

        // Инициализируем данные для текущего узла

        // с переданным значением как d

        data = d;

  

        // Инициализируем левого потомка в NULL

        l = NULL;

  

        // Инициализируем правого потомка в NULL

        r = NULL;

    }

} Node;

  
// Функция для печати требуемого обхода заказа

void printInorder(Node* rootL, Node* rootR)

{

    // Мы используем 2 указателя для узлов

    // которые являются зеркальным отражением друг друга

    // Если оба потомка имеют значение NULL, возвращаем

    if (rootL->l == NULL && rootR->r == NULL)

        return;

  

    // Поскольку обход по заказу необходим

    // Сначала налево, затем root, а затем направо

    printInorder(rootL->l, rootR->r);

    cout << rootL->l->data + rootR->r->data << endl;

    printInorder(rootL->r, rootR->l);

}

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

int main()

{

    Node* root = new Node(5);

    root->l = new Node(23);

    root->r = new Node(28);

    root->l->l = new Node(4);

    root->l->r = new Node(11);

    root->r->l = new Node(8);

    root->r->r = new Node(16);

  

    printInorder(root, root);

  

    // Поскольку корень является зеркальным отражением самого себя

    if (root)

        cout << root->data * 2 << endl;

  

    return 0;

}

Джава

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

import java.util.*;

  

class GFG

    static class Node 

    {

  

        // структура для хранения данных и ссылок на

        // его левый и правый ребенок

        int data;

        Node l;

        Node r;

        Node(int d)

        {

      

            // Инициализируем данные для текущего узла

            // с переданным значением как d

            data = d;

      

            // Инициализируем левого потомка в ноль

            l = null;

      

            // Инициализируем правого потомка в ноль

            r = null;

        }

    

  

    // Функция для печати требуемого обхода заказа

    static void printInorder(Node rootL, Node rootR)

    {

        // Мы используем 2 указателя для узлов

        // которые являются зеркальным отражением друг друга

        // Если оба дочерних элемента равны нулю, возвращаем

        if (rootL.l == null && rootR.r == null)

            return;

      

        // Поскольку обход по заказу необходим

        // Сначала налево, затем root, а затем направо

        printInorder(rootL.l, rootR.r);

        System.out.println(rootL.l.data + rootR.r.data );

        printInorder(rootL.r, rootR.l);

    }

  

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

    public static void main(String args[])

    {

        Node root = new Node(5);

        root.l = new Node(23);

        root.r = new Node(28);

        root.l.l = new Node(4);

        root.l.r = new Node(11);

        root.r.l = new Node(8);

        root.r.r = new Node(16);

      

        printInorder(root, root);

      

        // Поскольку корень является зеркальным отражением самого себя

        if (root != null)

            System.out.println(root.data * 2 );

      

    }

}

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

python3

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

  

class Node:

      

    def __init__(self, d):

        self.data = d

        self.l = None

        self.r = None

  
# Функция для печати требуемого обхода заказа

def printInorder(rootL, rootR): 

   

    # Мы используем 2 указателя для узлов

    # которые являются зеркальным отображением друг друга

    # Если оба ребенка не возвращены

    if rootL.l == None and rootR.r == None

        return 

  

    # Так как требуется обход заказа

    # Сначала слева, затем root, а затем направо

    printInorder(rootL.l, rootR.r) 

    print(rootL.l.data + rootR.r.data) 

    printInorder(rootL.r, rootR.l) 

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

if __name__ == "__main__"

   

    root = Node(5

    root.l = Node(23

    root.r = Node(28

    root.l.l = Node(4

    root.l.r = Node(11

    root.r.l = Node(8

    root.r.r = Node(16

  

    printInorder(root, root) 

  

    # Поскольку корень является зеркальным отражением самого себя

    if root:

        print(root.data * 2

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

C #

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

using System;

  

class GFG

    public class Node 

    {

  

        // структура для хранения данных и ссылок на

        // его левый и правый ребенок

        public int data;

        public Node l;

        public Node r;

        public Node(int d)

        {

      

            // Инициализируем данные для текущего узла

            // с переданным значением как d

            data = d;

      

            // Инициализируем левого потомка в ноль

            l = null;

      

            // Инициализируем правого потомка в ноль

            r = null;

        }

    

  

    // Функция для печати требуемого обхода заказа

    static void printInorder(Node rootL, Node rootR)

    {

        // Мы используем 2 указателя для узлов

        // которые являются зеркальным отражением друг друга

        // Если оба дочерних элемента равны нулю, возвращаем

        if (rootL.l == null && rootR.r == null)

            return;

      

        // Поскольку обход по заказу необходим

        // Сначала налево, затем root, а затем направо

        printInorder(rootL.l, rootR.r);

        Console.WriteLine(rootL.l.data + rootR.r.data );

        printInorder(rootL.r, rootR.l);

    }

  

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

    public static void Main(String []args)

    {

        Node root = new Node(5);

        root.l = new Node(23);

        root.r = new Node(28);

        root.l.l = new Node(4);

        root.l.r = new Node(11);

        root.r.l = new Node(8);

        root.r.r = new Node(16);

      

        printInorder(root, root);

      

        // Поскольку корень является зеркальным отражением самого себя

        if (root != null)

            Console.WriteLine(root.data * 2 );

      

    }

}

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

Выход:

20
51
19
10

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

Сумма узлов зеркального отображения полного бинарного дерева по порядку

0.00 (0%) 0 votes