Рубрики

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

Задав двоичное дерево, выведите угловые узлы на каждом уровне. Узел слева и узел справа.

Например, выходные данные для следующих 15, 10, 20, 8, 25 .

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

Можем ли мы распечатать все угловые узлы, используя один обход?
Идея состоит в том, чтобы использовать Level Order Traversal . Каждый раз мы сохраняем размер очереди в переменной n, которая является количеством узлов на этом уровне. Для каждого уровня мы проверяем три условия, есть ли один узел или более одного узла, в случае, если есть только один узел, мы печатаем его один раз, и если у нас более 1 узла, мы печатаем первый (т. Е. Узел с индексом 0 ) и узел с последним индексом (то есть узел с индексом n-1).

C ++

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

using namespace std;

  
/ * Узел двоичного дерева имеет ключ, указатель налево

   дочерний элемент и указатель на правый дочерний элемент * /

struct Node

{

    int key;

    struct Node* left, *right;

};

  
/ * Создать новый узел дерева и вернуть указатель * /

struct Node* newNode(int key)

{

    Node* temp = new Node;

    temp->key = key;

    temp->left = temp->right = NULL;

    return (temp);

}

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

void printCorner(Node *root)

{

    // Если корень нулевой, просто вернем

    if(root == NULL)

        return;

    // Делаем прохождение порядка уровней, используя очередь

    queue<Node*> q;

    q.push(root);

      

    // Вектор будет хранить ответ

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

    vector<int> ans;

      

    while(!q.empty())

    {

        // n обозначает размер текущей очереди

        int n = q.size();

          

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

        {

            Node *temp = q.front();

            q.pop();

              

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

            if(i==0)

                ans.push_back(temp->key);

           // значение правого угла

            else if(i==n-1)

                ans.push_back(temp->key);

             

                  

            // выдвигаем левого и правого потомков временного узла

            if(temp->left)

                q.push(temp->left);

            if(temp->right)

                q.push(temp->right);

        }

    }

    // перебираем переменную и печатаем ответы

    for(auto i : ans)

        cout << i << " ";

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

int main ()

{

    Node *root =  newNode(15);

    root->left = newNode(10);

    root->right = newNode(20);

    root->left->left = newNode(8);

    root->left->right = newNode(12);

    root->right->left = newNode(16);

    root->right->right = newNode(25);

    printCorner(root);

    return 0; 

}

Джава

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

  

import java.util.*;

  
/ * Узел двоичного дерева имеет ключ, указатель налево

   дочерний элемент и указатель на правый дочерний элемент * /

class Node 

{

    int key;

    Node left, right;

  

    public Node(int key) 

    {

        this.key = key;

        left = right = null;

    }

}

  

class BinaryTree 

{

    Node root;

  

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

    void printCorner(Node root)

    {

        // звездный узел для отслеживания уровней

        Queue<Node> q = new LinkedList<Node>();

  

        // толкаем корневой узел и звездный узел

        q.add(root);

        q.add(null);

  

        // если isFirst = true, то левый крайний узел этого уровня

        // будет напечатан

        boolean isFirst = false;

  

        // если isOne = true, тогда этот уровень имеет только один узел

        boolean isOne = false;

  

        // last будет хранить самый правый узел этого уровня

        int last = 0;

  

        // Осуществляем обход уровня бинарного дерева

        while (!q.isEmpty()) 

        {

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

            Node temp = q.peek();

            q.poll();

  

            // если isFirst имеет значение true, то temp является самым левым узлом

            if (isFirst) 

            {

                System.out.print(temp.key + "  ");

  

                if (temp.left != null)

                    q.add(temp.left);

                if (temp.right != null)

                    q.add(temp.right);

                  

                // сделать isFirst как false и one = 1

                isFirst = false;

                isOne = true;

            

              

            // Иначе, если temp является разделителем между двумя уровнями

            else if (temp == null

            {

                // Вставляем новый разделитель, если в очереди есть элементы

                if (q.size() >= 1

                    q.add(null);

                  

                // сделать isFirst как true, потому что следующий узел будет

                // самый левый узел этого уровня

                isFirst = true;

  

                // печать последнего узла, только если этот уровень

                // иначе не содержит ни одного узла

                // этот единственный узел будет напечатан дважды

                if (!isOne)

                    System.out.print(last + "  ");    

            

            else

            {

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

                last = temp.key;

  

                // Здесь мы делаем isOne = false для обозначения

                // этот уровень имеет более одного узла

                isOne = false;

                if (temp.left != null)

                    q.add(temp.left);

                if (temp.right != null)

                    q.add(temp.right);               

            }

        }

    }

  

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

    public static void main(String[] args) 

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(15);

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

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

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

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

        tree.root.right.left = new Node(16);

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

  

        tree.printCorner(tree.root);

    }

}

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

C #

// C # программа для печати углового узла
// на каждом уровне в двоичном дереве

using System;

using System.Collections.Generic;

  
/ * Узел двоичного дерева имеет ключ, указатель налево
дочерний элемент и указатель на правый дочерний элемент * /

public class Node 

{

    public int key;

    public Node left, right;

  

    public Node(int key) 

    {

        this.key = key;

        left = right = null;

    }

}

  

public class BinaryTree 

{

    Node root;

  

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

    void printCorner(Node root)

    {

        // звездный узел для отслеживания уровней

        Queue<Node> q = new Queue<Node>();

  

        // толкаем корневой узел и звездный узел

        q.Enqueue(root);

        q.Enqueue(null);

  

        // если isFirst = true, то левый крайний узел

        // этого уровня будет напечатан

        Boolean isFirst = false;

  

        // если isOne = true, тогда этот уровень имеет только один узел

        Boolean isOne = false;

  

        // last будет хранить самый правый узел этого уровня

        int last = 0;

  

        // Осуществляем обход уровня бинарного дерева

        while (q.Count != 0) 

        {

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

            Node temp = q.Peek();

            q.Dequeue();

  

            // если isFirst имеет значение true, то temp является самым левым узлом

            if (isFirst) 

            {

                Console.Write(temp.key + " ");

  

                if (temp.left != null)

                    q.Enqueue(temp.left);

                if (temp.right != null)

                    q.Enqueue(temp.right);

                  

                // сделать isFirst как false и one = 1

                isFirst = false;

                isOne = true;

            

              

            // Иначе, если temp является разделителем между двумя уровнями

            else if (temp == null

            {

                // Вставляем новый разделитель, если в очереди есть элементы

                if (q.Count >= 1) 

                    q.Enqueue(null);

                  

                // сделать isFirst как true, потому что следующий узел будет

                // самый левый узел этого уровня

                isFirst = true;

  

                // печать последнего узла, только если этот уровень

                // иначе не содержит ни одного узла

                // этот единственный узел будет напечатан дважды

                if (!isOne)

                    Console.Write(last + " "); 

            

            else

            {

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

                last = temp.key;

  

                // Здесь мы делаем isOne = false для обозначения

                // этот уровень имеет более одного узла

                isOne = false;

                if (temp.left != null)

                    q.Enqueue(temp.left);

                if (temp.right != null)

                    q.Enqueue(temp.right);             

            }

        }

    }

  

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

    public static void Main(String[] args) 

    {

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(15);

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

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

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

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

        tree.root.right.left = new Node(16);

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

  

        tree.printCorner(tree.root);

    }

}

  
// Этот код предоставлен Rajput-Ji


Выход :

15  10  20  8  25  

Сложность времени: O (n), где n — количество узлов в двоичном дереве.

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

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

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

0.00 (0%) 0 votes