Dado un árbol binario y un Node, imprime todos los primos del Node dado. Tenga en cuenta que los hermanos no deben imprimirse.
Ejemplo:
Input : root of below tree 1 / \ 2 3 / \ / \ 4 5 6 7 and pointer to a node say 5. Output : 6, 7
La idea de encontrar primero el nivel de un Node dado usando el enfoque discutido aquí . Una vez que hayamos encontrado el nivel, podemos imprimir todos los Nodes en un nivel dado utilizando el enfoque discutido aquí . Lo único que debe cuidarse es que el hermano no debe imprimirse. Para manejar esto, cambiamos la función de impresión para que primero verifique el Node hermano e imprima solo si no es hermano.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to print cousins of a node #include <bits/stdc++.h> using namespace std; // A Binary Tree Node struct Node { int data; Node *left, *right; }; // A utility function to create a new // Binary Tree Node Node *newNode(int item) { Node *temp = new Node; temp->data = item; temp->left = temp->right = NULL; return temp; } /* It returns level of the node if it is present in tree, otherwise returns 0.*/ int getLevel(Node *root, Node *node, int level) { // base cases if (root == NULL) return 0; if (root == node) return level; // If node is present in left subtree int downlevel = getLevel(root->left, node, level + 1); if (downlevel != 0) return downlevel; // If node is not present in left subtree return getLevel(root->right, node, level + 1); } /* Print nodes at a given level such that sibling of node is not printed if it exists */ void printGivenLevel(Node* root, Node *node, int level) { // Base cases if (root == NULL || level < 2) return; // If current node is parent of a node // with given level if (level == 2) { if (root->left == node || root->right == node) return; if (root->left) cout << root->left->data << " "; if (root->right) cout << root->right->data; } // Recur for left and right subtrees else if (level > 2) { printGivenLevel(root->left, node, level - 1); printGivenLevel(root->right, node, level - 1); } } // This function prints cousins of a given node void printCousins(Node *root, Node *node) { // Get level of given node int level = getLevel(root, node, 1); // Print nodes of given level. printGivenLevel(root, node, level); } // Driver Code int main() { Node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->left->right->right = newNode(15); root->right->left = newNode(6); root->right->right = newNode(7); root->right->left->right = newNode(8); printCousins(root, root->left->right); return 0; } // This code is contributed // by Akanksha Rai
C
// C program to print cousins of a node #include <stdio.h> #include <stdlib.h> // A Binary Tree Node struct Node { int data; Node *left, *right; }; // A utility function to create a new Binary // Tree Node Node *newNode(int item) { Node *temp = new Node; temp->data = item; temp->left = temp->right = NULL; return temp; } /* It returns level of the node if it is present in tree, otherwise returns 0.*/ int getLevel(Node *root, Node *node, int level) { // base cases if (root == NULL) return 0; if (root == node) return level; // If node is present in left subtree int downlevel = getLevel(root->left, node, level+1); if (downlevel != 0) return downlevel; // If node is not present in left subtree return getLevel(root->right, node, level+1); } /* Print nodes at a given level such that sibling of node is not printed if it exists */ void printGivenLevel(Node* root, Node *node, int level) { // Base cases if (root == NULL || level < 2) return; // If current node is parent of a node with // given level if (level == 2) { if (root->left == node || root->right == node) return; if (root->left) printf("%d ", root->left->data); if (root->right) printf("%d ", root->right->data); } // Recur for left and right subtrees else if (level > 2) { printGivenLevel(root->left, node, level-1); printGivenLevel(root->right, node, level-1); } } // This function prints cousins of a given node void printCousins(Node *root, Node *node) { // Get level of given node int level = getLevel(root, node, 1); // Print nodes of given level. printGivenLevel(root, node, level); } // Driver Program to test above functions int main() { Node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->left->right->right = newNode(15); root->right->left = newNode(6); root->right->right = newNode(7); root->right->left->right = newNode(8); printCousins(root, root->left->right); return 0; }
Java
// Java program to print cousins of a node class GfG { // A Binary Tree Node static class Node { int data; Node left, right; } // A utility function to create a new Binary // Tree Node static Node newNode(int item) { Node temp = new Node(); temp.data = item; temp.left = null; temp.right = null; return temp; } /* It returns level of the node if it is present in tree, otherwise returns 0.*/ static int getLevel(Node root, Node node, int level) { // base cases if (root == null) return 0; if (root == node) return level; // If node is present in left subtree int downlevel = getLevel(root.left, node, level+1); if (downlevel != 0) return downlevel; // If node is not present in left subtree return getLevel(root.right, node, level+1); } /* Print nodes at a given level such that sibling of node is not printed if it exists */ static void printGivenLevel(Node root, Node node, int level) { // Base cases if (root == null || level < 2) return; // If current node is parent of a node with // given level if (level == 2) { if (root.left == node || root.right == node) return; if (root.left != null) System.out.print(root.left.data + " "); if (root.right != null) System.out.print(root.right.data + " "); } // Recur for left and right subtrees else if (level > 2) { printGivenLevel(root.left, node, level-1); printGivenLevel(root.right, node, level-1); } } // This function prints cousins of a given node static void printCousins(Node root, Node node) { // Get level of given node int level = getLevel(root, node, 1); // Print nodes of given level. printGivenLevel(root, node, level); } // Driver Program to test above functions public static void main(String[] args) { Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.left.right.right = newNode(15); root.right.left = newNode(6); root.right.right = newNode(7); root.right.left.right = newNode(8); printCousins(root, root.left.right); } }
Python3
# Python3 program to print cousins of a node # A utility function to create a new # Binary Tree Node class newNode: def __init__(self, item): self.data = item self.left = self.right = None # It returns level of the node if it is # present in tree, otherwise returns 0. def getLevel(root, node, level): # base cases if (root == None): return 0 if (root == node): return level # If node is present in left subtree downlevel = getLevel(root.left, node, level + 1) if (downlevel != 0): return downlevel # If node is not present in left subtree return getLevel(root.right, node, level + 1) # Print nodes at a given level such that # sibling of node is not printed if # it exists def printGivenLevel(root, node, level): # Base cases if (root == None or level < 2): return # If current node is parent of a # node with given level if (level == 2): if (root.left == node or root.right == node): return if (root.left): print(root.left.data, end = " ") if (root.right): print(root.right.data, end = " ") # Recur for left and right subtrees else if (level > 2): printGivenLevel(root.left, node, level - 1) printGivenLevel(root.right, node, level - 1) # This function prints cousins of a given node def printCousins(root, node): # Get level of given node level = getLevel(root, node, 1) # Print nodes of given level. printGivenLevel(root, node, level) # Driver Code if __name__ == '__main__': root = newNode(1) root.left = newNode(2) root.right = newNode(3) root.left.left = newNode(4) root.left.right = newNode(5) root.left.right.right = newNode(15) root.right.left = newNode(6) root.right.right = newNode(7) root.right.left.right = newNode(8) printCousins(root, root.left.right) # This code is contributed by PranchalK
C#
// C# program to print cousins of a node using System; public class GfG { // A Binary Tree Node class Node { public int data; public Node left, right; } // A utility function to create // a new Binary Tree Node static Node newNode(int item) { Node temp = new Node(); temp.data = item; temp.left = null; temp.right = null; return temp; } /* It returns level of the node if it is present in tree, otherwise returns 0.*/ static int getLevel(Node root, Node node, int level) { // base cases if (root == null) return 0; if (root == node) return level; // If node is present in left subtree int downlevel = getLevel(root.left, node, level + 1); if (downlevel != 0) return downlevel; // If node is not present in left subtree return getLevel(root.right, node, level + 1); } /* Print nodes at a given level such that sibling of node is not printed if it exists */ static void printGivenLevel(Node root, Node node, int level) { // Base cases if (root == null || level < 2) return; // If current node is parent of a node with // given level if (level == 2) { if (root.left == node || root.right == node) return; if (root.left != null) Console.Write(root.left.data + " "); if (root.right != null) Console.Write(root.right.data + " "); } // Recur for left and right subtrees else if (level > 2) { printGivenLevel(root.left, node, level - 1); printGivenLevel(root.right, node, level - 1); } } // This function prints cousins of a given node static void printCousins(Node root, Node node) { // Get level of given node int level = getLevel(root, node, 1); // Print nodes of given level. printGivenLevel(root, node, level); } // Driver code public static void Main(String[] args) { Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.left.right.right = newNode(15); root.right.left = newNode(6); root.right.right = newNode(7); root.right.left.right = newNode(8); printCousins(root, root.left.right); } } // This code is contributed Rajput-Ji
Javascript
<script> // JavaScript program to print cousins of a node // A Binary Tree Node class Node { constructor() { this.data=0; this.left= null; this.right = null; } } // A utility function to create // a new Binary Tree Node function newNode(item) { var temp = new Node(); temp.data = item; temp.left = null; temp.right = null; return temp; } /* It returns level of the node if it is present in tree, otherwise returns 0.*/ function getLevel(root, node, level) { // base cases if (root == null) return 0; if (root == node) return level; // If node is present in left subtree var downlevel = getLevel(root.left, node, level + 1); if (downlevel != 0) return downlevel; // If node is not present in left subtree return getLevel(root.right, node, level + 1); } /* Print nodes at a given level such that sibling of node is not printed if it exists */ function printGivenLevel(root, node, level) { // Base cases if (root == null || level < 2) return; // If current node is parent of a node with // given level if (level == 2) { if (root.left == node || root.right == node) return; if (root.left != null) document.write(root.left.data + " "); if (root.right != null) document.write(root.right.data + " "); } // Recur for left and right subtrees else if (level > 2) { printGivenLevel(root.left, node, level - 1); printGivenLevel(root.right, node, level - 1); } } // This function prints cousins of a given node function printCousins(root, node) { // Get level of given node var level = getLevel(root, node, 1); // Print nodes of given level. printGivenLevel(root, node, level); } // Driver code var root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); root.left.right.right = newNode(15); root.right.left = newNode(6); root.right.right = newNode(7); root.right.left.right = newNode(8); printCousins(root, root.left.right); </script>
6 7
Complejidad de tiempo : O(n)
¿Podemos resolver este problema usando un solo recorrido? Consulte el artículo a continuación
Imprimir primos de un Node determinado en Binary Tree | Travesía única
Este artículo es una contribución de Shivam Gupta . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA