Рубрики

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

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

Например, если заданное дерево следует за двоичным деревом, а ключ равен 7, ваша функция должна вывести 4, 2 и 1.


              1
            /   \
          2      3
        /  \
      4     5
     /
    7

Спасибо Майку, Самбасиве и wgpshashank за их вклад.

C ++

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

  

using namespace std;

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

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

struct node

{

   int data;

   struct node* left;

   struct node* right;

};

  
/ * Если цель присутствует в дереве, то печатает предков

   и возвращает истину, в противном случае возвращает ложь. * /

bool printAncestors(struct node *root, int target)

{

  / * базовые случаи * /

  if (root == NULL)

     return false;

  

  if (root->data == target)

     return true;

  

  / * Если цель присутствует в левом или правом поддереве этого узла,

     затем распечатайте этот узел * /

  if ( printAncestors(root->left, target) ||

       printAncestors(root->right, target) )

  {

    cout << root->data << " ";

    return true;

  }

  

  / * Иначе вернем false * /

  return false;

}

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

   данные даны и NULL левый и правый указатели. * /

struct node* newnode(int data)

{

  struct node* node = (struct node*)

                       malloc(sizeof(struct node));

  node->data = data;

  node->left = NULL;

  node->right = NULL;

  

  return(node);

}

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

int main()

{

  

  / * Построить следующее двоичное дерево

              1

            / /

          2 3

        / /

      4 5

     /

    7

  * /

  struct node *root = newnode(1);

  root->left        = newnode(2);

  root->right       = newnode(3);

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

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

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

  

  printAncestors(root, 7);

  

  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;

   

    / * Если цель присутствует в дереве, то печатает предков

       и возвращает истину, в противном случае возвращает ложь. * /

    boolean printAncestors(Node node, int target) 

    {

         / * базовые случаи * /

        if (node == null)

            return false;

   

        if (node.data == target)

            return true;

   

        / * Если цель присутствует в левом или правом поддереве

           этого узла, затем выведите этот узел * /

        if (printAncestors(node.left, target)

                || printAncestors(node.right, target)) 

        {

            System.out.print(node.data + " ");

            return true;

        }

   

        / * Иначе вернем false * /

        return false;

    }

   

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

    public static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

          

        / * Построить следующее двоичное дерево

                  1

                / /

               2 3

              / /

             4 5

            /

           7

        * /

        tree.root = new Node(1);

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

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

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

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

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

   

        tree.printAncestors(tree.root, 7);

   

    }

}

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

питон

# Программа Python для печати предков данного узла в
# двоичное дерево

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

class Node:

  

    # Конструктор для создания нового узла

    def __init__(self, data):

        self.data = data 

        self.left = None

        self.right = None

  
# Если цель присутствует в дереве, то печатает предков
# и возвращает true, иначе возвращает false

def printAncestors(root, target):

      

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

    if root == None:

        return False 

      

    if root.data == target:

        return True 

  

    # Если цель присутствует в левом или правом поддереве

    # этого узла, затем распечатайте этот узел

    if (printAncestors(root.left, target) or 

        printAncestors(root.right, target)):

        print root.data,

        return True

  

    # Остальное вернуть False

    return False

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

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

root.left.left.left = Node(7)

  

printAncestors(root, 7)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

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;

  

    / * Если цель присутствует в дереве, то печатает предков

    и возвращает истину, в противном случае возвращает ложь. * /

    public virtual bool printAncestors(Node node, int target)

    {

        / * базовые случаи * /

        if (node == null)

        {

            return false;

        }

  

        if (node.data == target)

        {

            return true;

        }

  

        / * Если цель присутствует в левом или правом поддереве

        этого узла, затем выведите этот узел * /

        if (printAncestors(node.left, target) 

        || printAncestors(node.right, target))

        {

            Console.Write(node.data + " ");

            return true;

        }

  

        / * Иначе вернем false * /

        return false;

    }

  

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

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

  

        / * Построить следующее двоичное дерево

                1

                / /

            2 3

            / /

            4 5

            /

        7

        * /

        tree.root = new Node(1);

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

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

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

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

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

  

        tree.printAncestors(tree.root, 7);

  

    }

}

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

Выход:
4 2 1

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

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

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

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

0.00 (0%) 0 votes