Рубрики

Распечатать все узлы, у которых нет родного брата

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

Например, выходное значение должно быть «4 5 6» для следующего дерева.

Это типичный вопрос обхода дерева. Мы начинаем с корня и проверяем, есть ли у узла один дочерний элемент, если да, то выводим единственный дочерний элемент этого узла. Если у узла есть оба дочерних элемента, то повторите для обоих дочерних элементов.

C ++

/ * Программа для поиска синглов в заданном бинарном дереве * /
#include <iostream>

using namespace std;

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

struct node

{

    struct node *left, *right;

    int key;

};

  
// Сервисная функция для создания нового узла дерева

node* newNode(int key)

{

    node *temp = new node;

    temp->key = key;

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

    return temp;

}

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

void printSingles(struct node *root)

{

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

    if (root == NULL)

      return;

  

    // Если это внутренний узел, повторить для левого

    // и правильные поддеревья

    if (root->left != NULL && root->right != NULL)

    {

        printSingles(root->left);

        printSingles(root->right);

    }

  

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

    // и повторить для правильного ребенка

    else if (root->right != NULL)

    {

        cout << root->right->key << " ";

        printSingles(root->right);

    }

  

    // Если правый потомок равен NULL, а левый - нет, вывести левый потомок

    // и повторить для левого ребенка

    else if (root->left != NULL)

    {

        cout << root->left->key << " ";

        printSingles(root->left);

    }

}

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

int main()

{

    // Давайте создадим двоичное дерево, приведенное в примере выше

    node *root = newNode(1);

    root->left = newNode(2);

    root->right = newNode(3);

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

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

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

    printSingles(root);

    return 0;

}

Джава

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

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

class Node 

{

    int data;

    Node left, right;

  

    Node(int item) 

    {

        data = item;

        left = right = null;

    }

}

  

class BinaryTree 

{

    Node root;

      

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

    void printSingles(Node node)

    {

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

    if (node == null)

      return;

   

    // Если это внутренний узел, повторить для левого

    // и правильные поддеревья

    if (node.left != null && node.right != null)

    {

        printSingles(node.left);

        printSingles(node.right);

    }

   

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

    // и повторить для правильного ребенка

    else if (node.right != null)

    {

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

        printSingles(node.right);

    }

   

    // Если правый потомок равен NULL, а левый - нет, вывести левый потомок

    // и повторить для левого ребенка

    else if (node.left != null)

    {

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

        printSingles(node.left);

    }

}

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

    public static void main(String args[]) 

    {

        BinaryTree tree = new BinaryTree();

  

        / * Построим дерево, показанное на диаграмме выше * /

        tree.root = new Node(1);

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

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

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

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

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

        tree.printSingles(tree.root);

    }

}

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

питон

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

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

class Node:

      

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

    def __init__(self, key):

        self.key = key

        self.left = None

        self.right = None

  
# Функция для печати всех некорневых узлов, которые не имеют
# брат

def printSingles(root):

  

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

    if root is None:

        return 

  

    # Если это внутренний узел, повторить для левого

    # и правильные поддеревья

    if root.left is not None and root.right is not None:

        printSingles(root.left)

        printSingles(root.right)

  

    # Если левый ребенок равен NULL, а правый - нет, выведите

    # Правильный ребенок и верный для правильного ребенка

    elif root.right is not None:

        print root.right.key,

        printSingles(root.right)

  

    # Если правый потомок равен NULL, а левый - нет, выведите

    # оставленный ребенок и повторение для оставленного ребенка

    elif root.left is not None:

        print root.left.key, 

        printSingles(root.left)

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

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.right = Node(4)

root.right.left = Node(5)

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

printSingles(root)

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

C #

using System;

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

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

public class Node

{

    public int data;

    public Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  

public class BinaryTree

{

    public Node root;

  

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

    public virtual void printSingles(Node node)

    {

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

    if (node == null)

    {

      return;

    }

  

    // Если это внутренний узел, повторить для левого

    // и правильные поддеревья

    if (node.left != null && node.right != null)

    {

        printSingles(node.left);

        printSingles(node.right);

    }

  

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

    // и повторить для правильного ребенка

    else if (node.right != null)

    {

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

        printSingles(node.right);

    }

  

    // Если правый потомок равен NULL, а левый - нет, вывести левый потомок

    // и повторить для левого ребенка

    else if (node.left != null)

    {

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

        printSingles(node.left);

    }

    }

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

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

  

        / * Построим дерево, показанное на диаграмме выше * /

        tree.root = new Node(1);

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

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

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

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

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

        tree.printSingles(tree.root);

    }

}

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


Выход:

4 5 6 

Сложность по времени вышеприведенного кода равна O (n), так как код выполняет простой обход дерева.

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

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

Распечатать все узлы, у которых нет родного брата

0.00 (0%) 0 votes