Распечатать все нечетные узлы двоичного дерева поиска
Опубликовано: 3 Декабря, 2021
Учитывая двоичное дерево поиска. Задача - распечатать все нечетные узлы двоичного дерева поиска.
Примеры :
Вход :
5
/
3 7
/ /
2 4 6 8
Выход : 3 5 7
Вход :
14
/
12 17
/ /
8 13 16 19
Выход : 13 17 19
Подход : просмотрите дерево двоичного поиска, используя любой из обходов дерева, и проверьте, является ли значение текущего узла нечетным. Если да, то распечатайте его, иначе пропустите этот узел.
Ниже представлена реализация вышеуказанного подхода:
C ++
// C++ program to print all odd node of BST#include <bits/stdc++.h>using namespace std; // create Treestruct Node { int key; struct Node *left, *right;}; // A utility function to create a new BST nodeNode* newNode( item) int{ Node* temp = new Node; temp->key = item; temp->left = temp->right = NULL; return temp;} // A utility function to do inorder traversal of BSTvoid inorder(Node* root){ if (root != NULL) { inorder(root->left); printf ( "%d " , root->key); inorder(root->right); }} /* A utility function to insert a new node with given key in BST */Node* insert(Node* node, key) int{ /* If the tree is empty, return a new node */ if (node == NULL) return newNode(key); /* Otherwise, recur down the tree */ if (key < node->key) node->left = insert(node->left, key); else node->right = insert(node->right, key); /* return the (unchanged) node pointer */ return node;} // Function to print all odd nodesvoid oddNode(Node* root){ if (root != NULL) { oddNode(root->left); // if node is odd then print it if (root->key % 2 != 0) printf ( "%d " , root->key); oddNode(root->right); }} // Driver Codeint main(){ /* Let us create following 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 program to print all odd node of BSTclass GfG { // create Treestatic class Node { int key; Node left, right;} // A utility function to create a new BST nodestatic Node newNode( item) int{ Node temp = new Node(); temp.key = item; temp.left = null ; temp.right = null ; return temp;} // A utility function to do inorder traversal of BSTstatic void inorder(Node root){ if (root != null ) { inorder(root.left); System.out.print(root.key + " " ); inorder(root.right); }} /* A utility function to insert a new nodewith given key in BST */static Node insert(Node node, key) int{ /* If the tree is empty, return a new node */ if (node == null ) return newNode(key); /* Otherwise, recur down the tree */ if (key < node.key) node.left = insert(node.left, key); else node.right = insert(node.right, key); /* return the (unchanged) node pointer */ return node;} // Function to print all odd nodesstatic void oddNode(Node root){ if (root != null ) { oddNode(root.left); // if node is odd then print it if (root.key % 2 != 0 ) System.out.print(root.key + " " ); oddNode(root.right); }} // Driver Codepublic static void main(String[] args){ /* Let us create following 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 program to print all odd# node of BST # create Tree# to create a new BST nodeclass newNode: # Construct to create a new node def __init__( self , key): self .key = key self .left = None self .right = None # A utility function to do inorder# traversal of BSTdef inorder( root) : if (root ! = None ): inorder(root.left) print (root.key, end = " " ) inorder(root.right) """ A utility function to insert anew node with given key in BST """def insert(node, key): """ If the tree is empty, return a new node """ if (node = = None ): return newNode(key) """ Otherwise, recur down the tree """ if (key < node.key): node.left = insert(node.left, key) else : node.right = insert(node.right, key) """ return the (unchanged) node pointer """ return node # Function to print all even nodesdef oddNode(root) : if (root ! = None ): oddNode(root.left) # if node is even then print it if (root.key % 2 ! = 0 ): print (root.key, end = " " ) oddNode(root.right) # Driver Codeif __name__ = = '__main__' : """ Let us create following 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) # This code is contributed by# Shubham Singh(SHUBHAMSINGH10) |
C #
// C# program to print all odd node of BSTusing System; public class GfG{ // create Treeclass Node{ public key; int public Node left, right;} // A utility function to create a new BST nodestatic Node newNode( item) int{ Node temp = new Node(); temp.key = item; temp.left = null ; temp.right = null ; return temp;} // A utility function to do// inorder traversal of BSTstatic void inorder(Node root){ if (root != null ) { inorder(root.left); Console.Write(root.key + " " ); inorder(root.right); }} /* A utility function to insert a new nodewith given key in BST */static Node insert(Node node, key) int{ /* If the tree is empty, return a new node */ if (node == null ) return newNode(key); /* Otherwise, recur down the tree */ if (key < node.key) node.left = insert(node.left, key); else node.right = insert(node.right, key); /* return the (unchanged) node pointer */ return node;} // Function to print all odd nodesstatic void oddNode(Node root){ if (root != null ) { oddNode(root.left); // if node is odd then print it if (root.key % 2 != 0) Console.Write(root.key + " " ); oddNode(root.right); }} // Driver Codepublic static void Main(String[] args){ /* Let us create following 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); }} // This code has been contributed// by PrinciRaj1992 |
Выход:
3 5 7