Рубрики

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

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

Примеры :

Input : 
          5 
        /   \ 
       3     7 
      / \   / \ 
     2   4 6   8 
Output : 3 5 7

Input :
          14 
        /   \ 
       12    17 
      / \   / \ 
     8  13 16   19 
Output : 13 17 19

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

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

C ++

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

using namespace std;

  
// создаем дерево

struct Node {

    int key;

    struct Node *left, *right;

};

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

Node* newNode(int item)

{

    Node* temp = new Node;

    temp->key = item;

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

    return temp;

}

  
// Утилита для обхода порядка следования BST

void inorder(Node* root)

{

    if (root != NULL) {

        inorder(root->left);

        printf("%d ", root->key);

        inorder(root->right);

    }

}

  
/ * Утилита для вставки нового узла

   с заданным ключом в BST * /

Node* insert(Node* node, int key)

{

    / * Если дерево пустое, вернуть новый узел * /

    if (node == NULL)

        return newNode(key);

  

    / * В противном случае вернемся вниз по дереву * /

    if (key < node->key)

        node->left = insert(node->left, key);

    else

        node->right = insert(node->right, key);

  

    / * вернуть (неизмененный) указатель узла * /

    return node;

}

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

void oddNode(Node* root)

{

    if (root != NULL) {

        oddNode(root->left);

  

        // если узел нечетный, то вывести его

        if (root->key % 2 != 0)

            printf("%d ", root->key);

  

        oddNode(root->right);

    }

}

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

int main()

{

    / * Давайте создадим следующий BST

        5

      / /

     3 7

    / / / /

    2 4 6 8 * /

    Node* root = NULL;

    root = insert(root, 5);

    root = insert(root, 3);

    root = insert(root, 2);

    root = insert(root, 4);

    root = insert(root, 7);

    root = insert(root, 6);

    root = insert(root, 8);

  

    oddNode(root);

  

    return 0;

}

Джава

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

class GfG { 

  
// создаем дерево

static class Node { 

    int key; 

    Node left, right; 

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

static Node newNode(int item) 

    Node temp = new Node(); 

    temp.key = item; 

    temp.left = null;

    temp.right = null

    return temp; 

  
// Утилита для обхода порядка следования BST

static void inorder(Node root) 

    if (root != null) { 

        inorder(root.left); 

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

        inorder(root.right); 

    

  
/ * Утилита для вставки нового узла
с заданным ключом в BST * /

static Node insert(Node node, int key) 

    / * Если дерево пустое, вернуть новый узел * /

    if (node == null

        return newNode(key); 

  

    / * В противном случае вернемся вниз по дереву * /

    if (key < node.key) 

        node.left = insert(node.left, key); 

    else

        node.right = insert(node.right, key); 

  

    / * вернуть (неизмененный) указатель узла * /

    return node; 

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

static void oddNode(Node root) 

    if (root != null) { 

        oddNode(root.left); 

  

        // если узел нечетный, то вывести его

        if (root.key % 2 != 0

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

  

        oddNode(root.right); 

    

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

public static void main(String[] args) 

    / * Давайте создадим следующий BST

        5

    / /

    3 7

    / / / /

    2 4 6 8 * /

    Node root = null

    root = insert(root, 5); 

    root = insert(root, 3); 

    root = insert(root, 2); 

    root = insert(root, 4); 

    root = insert(root, 7); 

    root = insert(root, 6); 

    root = insert(root, 8); 

  

    oddNode(root); 

  

python3

# Python3 программа для печати всех нечетных
# узел BST

  
# создать дерево
# создать новый узел BST

class newNode: 

  

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

    def __init__(self, key): 

        self.key = key

        self.left = None

        self.right = None

  
# Полезная функция, чтобы сделать заказ
# обход BST

def inorder( root) :

  

    if (root != None): 

        inorder(root.left) 

        print(root.key, end = " "

        inorder(root.right) 

      
"" "Вспомогательная функция для вставки
новый узел с данным ключом в BST "" "

def insert(node, key): 

  

    "" "Если дерево пусто,

    вернуть новый узел "" "

    if (node == None): 

        return newNode(key) 

  

    "" "В противном случае вернемся вниз по дереву" ""

    if (key < node.key): 

        node.left = insert(node.left, key) 

    else:

        node.right = insert(node.right, key) 

  

    "" "вернуть (неизмененный) указатель узла" ""

    return node 

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

def oddNode(root) :

  

    if (root != None): 

        oddNode(root.left) 

          

        # если узел четный, то распечатать его

        if (root.key % 2 != 0):

            print(root.key, end = " "

        oddNode(root.right) 

  
Код водителя

if __name__ == '__main__':

      

    "" "Давайте создадим следующий BST

    5

    / /

    3 7

    / / / /

    2 4 6 8 "" "

    root = None

    root = insert(root, 5

    root = insert(root, 3

    root = insert(root, 2

    root = insert(root, 4

    root = insert(root, 7

    root = insert(root, 6

    root = insert(root, 8

  

    oddNode(root) 

  
# Этот код предоставлен
# Шубхам Сингх (SHUBHAMSINGH10)

C #

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

using System;

  

public class GfG 

  
// создаем дерево

class Node 

    public int key; 

    public Node left, right; 

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

static Node newNode(int item) 

    Node temp = new Node(); 

    temp.key = item; 

    temp.left = null

    temp.right = null

    return temp; 

  
// Полезная функция для выполнения
// обход порядка BST

static void inorder(Node root) 

    if (root != null)

    

        inorder(root.left); 

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

        inorder(root.right); 

    

  
/ * Утилита для вставки нового узла
с заданным ключом в BST * /

static Node insert(Node node, int key) 

    / * Если дерево пустое, вернуть новый узел * /

    if (node == null

        return newNode(key); 

  

    / * В противном случае вернемся вниз по дереву * /

    if (key < node.key) 

        node.left = insert(node.left, key); 

    else

        node.right = insert(node.right, key); 

  

    / * вернуть (неизмененный) указатель узла * /

    return node; 

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

static void oddNode(Node root) 

    if (root != null

    

        oddNode(root.left); 

  

        // если узел нечетный, то вывести его

        if (root.key % 2 != 0) 

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

  

        oddNode(root.right); 

    

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

public static void Main(String[] args) 

    / * Давайте создадим следующий BST

        5

    / /

    3 7

    / / / /

    2 4 6 8 * /

    Node root = null

    root = insert(root, 5); 

    root = insert(root, 3); 

    root = insert(root, 2); 

    root = insert(root, 4); 

    root = insert(root, 7); 

    root = insert(root, 6); 

    root = insert(root, 8); 

  

    oddNode(root); 

  

  
// Этот код был добавлен
// by PrinciRaj1992

Выход:

3 5 7

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

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

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

0.00 (0%) 0 votes