给定一棵N元树，找出给定节点x的同级数。假设给定N元树中存在x。
null
![图片[1]-n元树中给定节点的同级数-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_siblings.png)
例子：
Input : 30Output : 3
方法： 对于给定n元树中的每个节点，将当前节点的子节点推送到队列中。在队列中添加当前节点的子节点时，检查是否有子节点等于给定值x。如果是，则返回x的兄弟姐妹数。 以下是上述理念的实施情况：
C++
// C++ program to find number // of siblings of a given node #include <bits/stdc++.h> using namespace std; // Represents a node of an n-ary tree class Node { public : int key; vector<Node*> child; Node( int data) { key = data; } }; // Function to calculate number // of siblings of a given node int numberOfSiblings(Node* root, int x) { if (root == NULL) return 0; // Creating a queue and // pushing the root queue<Node*> q; q.push(root); while (!q.empty()) { // Dequeue an item from queue and // check if it is equal to x If YES, // then return number of children Node* p = q.front(); q.pop(); // Enqueue all children of // the dequeued item for ( int i = 0; i < p->child.size(); i++) { // If the value of children // is equal to x, then return // the number of siblings if (p->child[i]->key == x) return p->child.size() - 1; q.push(p->child[i]); } } } // Driver program int main() { // Creating a generic tree as shown in above figure Node* root = new Node(50); (root->child).push_back( new Node(2)); (root->child).push_back( new Node(30)); (root->child).push_back( new Node(14)); (root->child).push_back( new Node(60)); (root->child[0]->child).push_back( new Node(15)); (root->child[0]->child).push_back( new Node(25)); (root->child[0]->child[1]->child).push_back( new Node(70)); (root->child[0]->child[1]->child).push_back( new Node(100)); (root->child[1]->child).push_back( new Node(6)); (root->child[1]->child).push_back( new Node(1)); (root->child[2]->child).push_back( new Node(7)); (root->child[2]->child[0]->child).push_back( new Node(17)); (root->child[2]->child[0]->child).push_back( new Node(99)); (root->child[2]->child[0]->child).push_back( new Node(27)); (root->child[3]->child).push_back( new Node(16)); // Node whose number of // siblings is to be calculated int x = 100; // Function calling cout << numberOfSiblings(root, x) << endl; return 0; } |
JAVA
// Java program to find number // of siblings of a given node import java.util.*; class GFG { // Represents a node of an n-ary tree static class Node { int key; Vector<Node> child; Node( int data) { key = data; child = new Vector<Node>(); } }; // Function to calculate number // of siblings of a given node static int numberOfSiblings(Node root, int x) { if (root == null ) return 0 ; // Creating a queue and // pushing the root Queue<Node> q = new LinkedList<>(); q.add(root); while (q.size() > 0 ) { // Dequeue an item from queue and // check if it is equal to x If YES, // then return number of children Node p = q.peek(); q.remove(); // Enqueue all children of // the dequeued item for ( int i = 0 ; i < p.child.size(); i++) { // If the value of children // is equal to x, then return // the number of siblings if (p.child.get(i).key == x) return p.child.size() - 1 ; q.add(p.child.get(i)); } } return - 1 ; } // Driver code public static void main(String args[]) { // Creating a generic tree as shown in above figure Node root = new Node( 50 ); (root.child).add( new Node( 2 )); (root.child).add( new Node( 30 )); (root.child).add( new Node( 14 )); (root.child).add( new Node( 60 )); (root.child.get( 0 ).child).add( new Node( 15 )); (root.child.get( 0 ).child).add( new Node( 25 )); (root.child.get( 0 ).child.get( 1 ).child).add( new Node( 70 )); (root.child.get( 0 ).child.get( 1 ).child).add( new Node( 100 )); (root.child.get( 1 ).child).add( new Node( 6 )); (root.child.get( 1 ).child).add( new Node( 1 )); (root.child.get( 2 ).child).add( new Node( 7 )); (root.child.get( 2 ).child.get( 0 ).child).add( new Node( 17 )); (root.child.get( 2 ).child.get( 0 ).child).add( new Node( 99 )); (root.child.get( 2 ).child.get( 0 ).child).add( new Node( 27 )); (root.child.get( 3 ).child).add( new Node( 16 )); // Node whose number of // siblings is to be calculated int x = 100 ; // Function calling System.out.println( numberOfSiblings(root, x) ); } } // This code is contributed by Arnab Kundu |
Python3
# Python3 program to find number # of siblings of a given node from queue import Queue # Represents a node of an n-ary tree class newNode: def __init__( self ,data): self .child = [] self .key = data # Function to calculate number # of siblings of a given node def numberOfSiblings(root, x): if (root = = None ): return 0 # Creating a queue and # pushing the root q = Queue() q.put(root) while ( not q.empty()): # Dequeue an item from queue and # check if it is equal to x If YES, # then return number of children p = q.queue[ 0 ] q.get() # Enqueue all children of # the dequeued item for i in range ( len (p.child)): # If the value of children # is equal to x, then return # the number of siblings if (p.child[i].key = = x): return len (p.child) - 1 q.put(p.child[i]) # Driver Code if __name__ = = '__main__' : # Creating a generic tree as # shown in above figure root = newNode( 50 ) (root.child).append(newNode( 2 )) (root.child).append(newNode( 30 )) (root.child).append(newNode( 14 )) (root.child).append(newNode( 60 )) (root.child[ 0 ].child).append(newNode( 15 )) (root.child[ 0 ].child).append(newNode( 25 )) (root.child[ 0 ].child[ 1 ].child).append(newNode( 70 )) (root.child[ 0 ].child[ 1 ].child).append(newNode( 100 )) (root.child[ 1 ].child).append(newNode( 6 )) (root.child[ 1 ].child).append(newNode( 1 )) (root.child[ 2 ].child).append(newNode( 7 )) (root.child[ 2 ].child[ 0 ].child).append(newNode( 17 )) (root.child[ 2 ].child[ 0 ].child).append(newNode( 99 )) (root.child[ 2 ].child[ 0 ].child).append(newNode( 27 )) (root.child[ 3 ].child).append(newNode( 16 )) # Node whose number of # siblings is to be calculated x = 100 # Function calling print (numberOfSiblings(root, x)) # This code is contributed by PranchalK |
C#
// C# program to find number // of siblings of a given node using System; using System.Collections.Generic; class GFG { // Represents a node of an n-ary tree public class Node { public int key; public List<Node> child; public Node( int data) { key = data; child = new List<Node>(); } }; // Function to calculate number // of siblings of a given node static int numberOfSiblings(Node root, int x) { if (root == null ) return 0; // Creating a queue and // pushing the root Queue<Node> q = new Queue<Node>(); q.Enqueue(root); while (q.Count > 0) { // Dequeue an item from queue and // check if it is equal to x If YES, // then return number of children Node p = q.Peek(); q.Dequeue(); // Enqueue all children of // the dequeued item for ( int i = 0; i < p.child.Count; i++) { // If the value of children // is equal to x, then return // the number of siblings if (p.child[i].key == x) return p.child.Count - 1; q.Enqueue(p.child[i]); } } return -1; } // Driver code public static void Main(String []args) { // Creating a generic tree // as shown in above figure Node root = new Node(50); (root.child).Add( new Node(2)); (root.child).Add( new Node(30)); (root.child).Add( new Node(14)); (root.child).Add( new Node(60)); (root.child[0].child).Add( new Node(15)); (root.child[0].child).Add( new Node(25)); (root.child[0].child[1].child).Add( new Node(70)); (root.child[0].child[1].child).Add( new Node(100)); (root.child[1].child).Add( new Node(6)); (root.child[1].child).Add( new Node(1)); (root.child[2].child).Add( new Node(7)); (root.child[2].child[0].child).Add( new Node(17)); (root.child[2].child[0].child).Add( new Node(99)); (root.child[2].child[0].child).Add( new Node(27)); (root.child[3].child).Add( new Node(16)); // Node whose number of // siblings is to be calculated int x = 100; // Function calling Console.WriteLine( numberOfSiblings(root, x)); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript program to find number // of siblings of a given node // Represents a node of an n-ary tree class Node { constructor(data) { this .key = data; this .child = []; } }; // Function to calculate number // of siblings of a given node function numberOfSiblings(root, x) { if (root == null ) return 0; // Creating a queue and // pushing the root var q = []; q.push(root); while (q.length > 0) { // Dequeue an item from queue and // check if it is equal to x If YES, // then return number of children var p = q[0]; q.shift(); // push all children of // the dequeued item for ( var i = 0; i < p.child.length; i++) { // If the value of children // is equal to x, then return // the number of siblings if (p.child[i].key == x) return p.child.length - 1; q.push(p.child[i]); } } return -1; } // Driver code // Creating a generic tree // as shown in above figure var root = new Node(50); (root.child).push( new Node(2)); (root.child).push( new Node(30)); (root.child).push( new Node(14)); (root.child).push( new Node(60)); (root.child[0].child).push( new Node(15)); (root.child[0].child).push( new Node(25)); (root.child[0].child[1].child).push( new Node(70)); (root.child[0].child[1].child).push( new Node(100)); (root.child[1].child).push( new Node(6)); (root.child[1].child).push( new Node(1)); (root.child[2].child).push( new Node(7)); (root.child[2].child[0].child).push( new Node(17)); (root.child[2].child[0].child).push( new Node(99)); (root.child[2].child[0].child).push( new Node(27)); (root.child[3].child).push( new Node(16)); // Node whose number of // siblings is to be calculated var x = 100; // Function calling document.write( numberOfSiblings(root, x)); </script> |
输出：
1
时间复杂性： O（N），其中N是树中的节点数。 辅助空间： O（N），其中N是树中的节点数。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
