Рубрики

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

Имея двоичное дерево и ключ, напишите функцию, которая печатает всех предков ключа в данном двоичном дереве.

Например, рассмотрим следующее двоичное дерево

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

Ниже приведены различные клавиши ввода и их предки в вышеприведенном дереве.

Input Key    List of Ancestors 
-------------------------
 1            
 2            1
 3            1
 4            2 1
 5            2 1
 6            3 1
 7            3 1
 8            4 2 1
 9            5 2 1
10            7 3 1

Рекурсивное решение этой проблемы обсуждается здесь .
Понятно, что нам нужно использовать итеративный обход двоичного дерева на основе стека. Идея состоит в том, чтобы все предки были в стеке, когда мы достигнем узла с данным ключом. Как только мы дойдем до ключа, все, что нам нужно сделать, это распечатать содержимое стека.
Как получить всех предков в стеке, когда мы достигаем данного узла? Мы можем пройти все узлы способом Postorder. Если мы поближе рассмотрим рекурсивный обход по порядку, мы можем легко заметить, что когда рекурсивная функция вызывается для узла, стек рекурсивных вызовов содержит предков этого узла. Идея состоит в том, чтобы выполнить итеративный обход Postorder и остановить его, когда мы достигнем нужного узла.

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

С

// C программа для печати всех предков данного ключа
#include <stdio.h>
#include <stdlib.h>

  
// Максимальный размер стека
#define MAX_SIZE 100

  
// Структура для узла дерева

struct Node

{

    int data;

    struct Node *left, *right;

};

  
// Структура для стека

struct Stack

{

    int size;

    int top;

    struct Node* *array;

};

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

struct Node* newNode(int data)

{

    struct Node* node = (struct Node*) malloc(sizeof(struct Node));

    node->data = data;

    node->left = node->right = NULL;

    return node;

}

  
// Вспомогательная функция для создания стека заданного размера

struct Stack* createStack(int size)

{

    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));

    stack->size = size;

    stack->top = -1;

    stack->array = (struct Node**) malloc(stack->size * sizeof(struct Node*));

    return stack;

}

  
// ОСНОВНЫЕ ОПЕРАЦИИ СТЕКА

int isFull(struct Stack* stack)

{

    return ((stack->top + 1) == stack->size);

}

int isEmpty(struct Stack* stack)

{

    return stack->top == -1;

}

void push(struct Stack* stack, struct Node* node)

{

    if (isFull(stack))

        return;

    stack->array[++stack->top] = node;

}

struct Node* pop(struct Stack* stack)

{

    if (isEmpty(stack))

        return NULL;

    return stack->array[stack->top--];

}

struct Node* peek(struct Stack* stack)

{

    if (isEmpty(stack))

        return NULL;

    return stack->array[stack->top];

}

  
// Итеративная функция для печати всех предков данного ключа

void printAncestors(struct Node *root, int key)

{

    if (root == NULL) return;

  

    // Создать стек для хранения предков

    struct Stack* stack = createStack(MAX_SIZE);

  

    // Пройдем по всему дереву по порядку, пока не найдем ключ

    while (1)

    {

        // Пройдите через левую сторону. При прохождении вставьте узлы в

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

        while (root && root->data != key)

        {

            push(stack, root);   // выдвигаем текущий узел

            root = root->left;  // перейти к следующему узлу

        }

  

        // Если найден узел, чьи предки должны быть напечатаны,

        // затем разрываем цикл while.

        if (root && root->data == key)

            break;

  

        // Проверяем, существует ли правильное поддерево для узла сверху

        // Если нет, то вставьте этот узел, потому что нам это не нужно

        // узел больше

        if (peek(stack)->right == NULL)

        {

            root = pop(stack);

  

            // Если извлеченный узел является правым потомком вершины, то удаляем верхнюю

            // также. Левый потомок вершины должен быть обработан раньше.

            // Рассмотрим следующее дерево для примера и key = 3. Если мы

            // удаляем следующий цикл, программа перейдет в

            // бесконечный цикл после достижения 5.

            // 1

            // / /

            // 2 3

            // /

            // 4

            // /

            // 5

            while (!isEmpty(stack) && peek(stack)->right == root)

               root = pop(stack);

        }

  

        // если стек не пустой, просто установите корень как правый дочерний

        // вершины и начало обхода правого поддерева.

        root = isEmpty(stack)? NULL: peek(stack)->right;

    }

  

    // Если стек не пустой, вывести содержимое стека

    // Здесь предполагается, что ключ есть в дереве

    while (!isEmpty(stack))

        printf("%d ", pop(stack)->data);

}

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

int main()

{

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

    struct Node* root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

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

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

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

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

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

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

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

  

    printf("Following are all keys and their ancestors\n");

    for (int key = 1; key <= 10; key++)

    {

        printf("%d: ", key);

        printAncestors(root, key);

        printf("\n");

    }

  

    getchar();

    return 0;

}

C ++

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

using namespace std;

  

  
// Структура для узла дерева

struct Node

{

    int data;

    struct Node *left, *right;

};

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

struct Node* newNode(int data)

{

    struct Node* node = (struct Node*) malloc(sizeof(struct Node));

    node->data = data;

    node->left = node->right = NULL;

    return node;

}

  
// Итеративная функция для печати всех предков данного ключа

void printAncestors(struct Node *root, int key)

{

    if (root == NULL) return;

  

    // Создать стек для хранения предков

    stack<struct Node* > st;

  

    // Пройдем по всему дереву по порядку, пока не найдем ключ

    while (1)

    {

        // Пройдите через левую сторону. При прохождении вставьте узлы в

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

        while (root && root->data != key)

        {

            st.push(root);   // выдвигаем текущий узел

            root = root->left;  // перейти к следующему узлу

        }

  

        // Если найден узел, чьи предки должны быть напечатаны,

        // затем разрываем цикл while.

        if (root && root->data == key)

            break;

  

        // Проверяем, существует ли правильное поддерево для узла сверху

        // Если нет, то вставьте этот узел, потому что нам это не нужно

        // узел больше

        if (st.top()->right == NULL)

        {

            root = st.top();

            st.pop();

  

            // Если извлеченный узел является правым потомком вершины, то удаляем верхнюю

            // также. Левый потомок вершины должен быть обработан раньше.

  

            while (!st.empty() && st.top()->right == root)

               {root = st.top();

               st.pop();

               }

        }

  

        // если стек не пустой, просто установите корень как правый дочерний

        // вершины и начало обхода правого поддерева.

        root = st.empty()? NULL: st.top()->right;

    }

  

    // Если стек не пустой, вывести содержимое стека

    // Здесь предполагается, что ключ есть в дереве

    while (!st.empty())

    {

        cout<<st.top()->data<<" ";

        st.pop();

    }

}

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

int main()

{

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

    struct Node* root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

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

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

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

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

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

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

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

  

    cout<<"Following are all keys and their ancestors"<<endl;

    for (int key = 1; key <= 10; key++)

    {

        cout<<key<<":"<<" ";

        printAncestors(root, key);

        cout<<endl;

    }

  

    return 0;

}
// Этот код предоставлен Гаутамом Сингхом

Джава

// Java-программа для печати всех предков данного ключа

import java.util.Stack;

  

public class GFG

{

    // Класс для узла дерева

    static class Node

    {

        int data;

        Node left,right;

          

        // конструктор для создания узла

        // слева и справа по умолчанию

        Node(int data)

        {

            this.data = data;

        }

    }

      

    // Итеративная функция для печати всех предков данного ключа

    static void printAncestors(Node root,int key)

    {

        if(root == null)

            return;

          

         // Создать стек для хранения предков

        Stack<Node> st = new Stack<>();

          

        // Пройдем по всему дереву по порядку, пока не найдем ключ

        while(true)

        {

              

            // Пройдите через левую сторону. При прохождении вставьте узлы в

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

            while(root != null && root.data != key)

            {

                st.push(root);   // выдвигаем текущий узел

                root = root.left;   // перейти к следующему узлу

            }

              

            // Если найден узел, чьи предки должны быть напечатаны,

            // затем разрываем цикл while.

            if(root != null && root.data == key)

                break;

              

            // Проверяем, существует ли правильное поддерево для узла сверху

            // Если нет, то вставьте этот узел, потому что нам это не нужно

            // узел больше

            if(st.peek().right == null)

            {

                root =st.peek();

                st.pop();

                  

                // Если извлеченный узел является правым потомком вершины, то удаляем верхнюю

                // также. Левый потомок вершины должен быть обработан раньше.

                while( st.empty() == false && st.peek().right == root)

                {

                    root = st.peek();

                    st.pop();

                }

            }

              

            // если стек не пустой, просто установите корень как правый дочерний

            // вершины и начало обхода правого поддерева.

            root = st.empty() ? null : st.peek().right;

        }

          

        // Если стек не пустой, вывести содержимое стека

        // Здесь предполагается, что ключ есть в дереве

        while( !st.empty() )

        {

            System.out.print(st.peek().data+" ");

            st.pop();

        }

    }

      

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

    public static void main(String[] args) 

    {

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

        Node root = new Node(1);

        root.left = new Node(2);

        root.right = new Node(3);

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

        root.left.right = new Node(5);

        root.right.left = new Node(6);

        root.right.right = new Node(7);

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

        root.left.right.right = new Node(9);

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

          

        System.out.println("Following are all keys and their ancestors");

        for(int key = 1;key <= 10;key++)

        {

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

            printAncestors(root, key);

            System.out.println();

        }

    }

  
}
// Этот код предоставлен Sumit Ghosh

C #

// C # программа для печати всех предков
// данного ключа

using System;

using System.Collections.Generic;

  

class GFG

{
// Класс для узла дерева

public class Node

{

    public int data;

    public Node left, right;

  

    // конструктор для создания узла

    // слева и справа по умолчанию

    public Node(int data)

    {

        this.data = data;

    }

}

  
// Итеративная функция для печати
// все предки данного ключа

public static void printAncestors(Node root, 

                                  int key)

{

    if (root == null)

    {

        return;

    }

  

    // Создать стек для хранения предков

    Stack<Node> st = new Stack<Node>();

  

    // Пройдите по всему дереву в

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

    while (true)

    {

  

        // Пройдите через левую сторону. Пока

        // прохождение, подтолкнуть узлы в

        // стек, чтобы их право

        // поддеревья могут быть пройдены позже

        while (root != null && root.data != key)

        {

            st.Push(root); // выдвигаем текущий узел

            root = root.left; // перейти к следующему узлу

        }

  

        // Если узел, чьи предки

        // должен быть напечатан найден,

        // затем разрываем цикл while.

        if (root != null && root.data == key)

        {

            break;

        }

  

        // Проверяем, существует ли правильное поддерево для

        // узел сверху. Если нет, то поп

        // этот узел, потому что нам не нужно

        // этот узел больше

        if (st.Peek().right == null)

        {

            root = st.Peek();

            st.Pop();

  

            // Если извлеченный узел является правильным потомком

            // сверху, затем удаляем также верх.

            // Левый потомок вершины должен иметь

            // обработано раньше

            while (st.Count > 0 && 

                   st.Peek().right == root)

            {

                root = st.Peek();

                st.Pop();

            }

        }

  

        // если стек не пуст, тогда просто

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

        // и начинаем обходить правое поддерево.

        root = st.Count == 0 ? 

                        null : st.Peek().right;

    }

  

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

    // стека Здесь предполагается, что

    // ключ есть в дереве

    while (st.Count > 0)

    {

        Console.Write(st.Peek().data + " ");

        st.Pop();

    }

}

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

public static void Main(string[] args)

{

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

    Node root = new Node(1);

    root.left = new Node(2);

    root.right = new Node(3);

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

    root.left.right = new Node(5);

    root.right.left = new Node(6);

    root.right.right = new Node(7);

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

    root.left.right.right = new Node(9);

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

  

    Console.WriteLine("Following are all keys " +

                          "and their ancestors");

    for (int key = 1; key <= 10; key++)

    {

        Console.Write(key + ": ");

        printAncestors(root, key);

        Console.WriteLine();

    }

}
}

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


Выход:

Following are all keys and their ancestors
1:
2: 1
3: 1
4: 2 1
5: 2 1
6: 3 1
7: 3 1
8: 4 2 1
9: 5 2 1
10: 7 3 1

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

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

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

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

0.00 (0%) 0 votes