给定一个二叉树和要在其中搜索的键，编写一个迭代方法，如果二叉树中存在键，则返回true，否则返回false。 例如，在下面的树中，如果搜索的键是3，那么函数应该返回true，如果搜索的键是12，那么函数应该返回false。
null
有一点是肯定的，我们需要遍历完整的树来决定键是否存在。我们可以使用以下任何遍历来迭代搜索给定二叉树中的一个键。 1） 迭代的 水平顺序遍历 . 2) 迭代有序遍历 3) 迭代前序遍历 4) 迭代后序遍历 下面是重复的 水平顺序遍历 在二叉树中搜索项目x的基于。
C++
// Iterative level order traversal // based method to search in Binary Tree #include<bits/stdc++.h> using namespace std; /* A binary tree node has data, left child and right child */ class node { public : int data; node* left; node* right; /* Constructor that allocates a new node with the given data and NULL left and right pointers. */ node( int data){ this ->data = data; this ->left = NULL; this ->right = NULL; } }; // An iterative process to search // an element x in a given binary tree bool iterativeSearch(node *root, int x) { // Base Case if (root == NULL) return false ; // Create an empty queue for // level order traversal queue<node *> q; // Enqueue Root and initialize height q.push(root); // Queue based level order traversal while (q.empty() == false ) { // See if current node is same as x node *node = q.front(); if (node->data == x) return true ; // Remove current node and enqueue its children q.pop(); if (node->left != NULL) q.push(node->left); if (node->right != NULL) q.push(node->right); } return false ; } // Driver code int main() { node* NewRoot=NULL; node *root = new node(2); root->left = new node(7); root->right = new node(5); root->left->right = new node(6); root->left->right->left= new node(1); root->left->right->right= new node(11); root->right->right= new node(9); root->right->right->left= new node(4); iterativeSearch(root, 6)? cout << "Found" : cout << "Not Found" ; iterativeSearch(root, 12)? cout << "Found" : cout << "Not Found" ; return 0; } // This code is contributed by rathbhupendra |
C
// Iterative level order traversal based method to search in Binary Tree #include <iostream> #include <queue> using namespace std; /* A binary tree node has data, left child and right child */ struct node { int data; struct node* left, *right; }; /* Helper function that allocates a new node with the given data and NULL left and right pointers.*/ struct node* newNode( int data) { struct node* node = new struct node; node->data = data; node->left = node->right = NULL; return (node); } // An iterative process to search an element x in a given binary tree bool iterativeSearch(node *root, int x) { // Base Case if (root == NULL) return false ; // Create an empty queue for level order traversal queue<node *> q; // Enqueue Root and initialize height q.push(root); // Queue based level order traversal while (q.empty() == false ) { // See if current node is same as x node *node = q.front(); if (node->data == x) return true ; // Remove current node and enqueue its children q.pop(); if (node->left != NULL) q.push(node->left); if (node->right != NULL) q.push(node->right); } return false ; } // Driver program int main( void ) { struct node*NewRoot=NULL; struct node *root = newNode(2); root->left = newNode(7); root->right = newNode(5); root->left->right = newNode(6); root->left->right->left=newNode(1); root->left->right->right=newNode(11); root->right->right=newNode(9); root->right->right->left=newNode(4); iterativeSearch(root, 6)? cout << "Found" : cout << "Not Found" ; iterativeSearch(root, 12)? cout << "Found" : cout << "Not Found" ; return 0; } |
JAVA
// Iterative level order traversal // based method to search in Binary Tree import java.util.*; class GFG { /* A binary tree node has data, left child and right child */ static class node { int data; node left; node right; /* Constructor that allocates a new node with the given data and null left and right pointers. */ node( int data) { this .data = data; this .left = null ; this .right = null ; } }; // An iterative process to search // an element x in a given binary tree static boolean iterativeSearch(node root, int x) { // Base Case if (root == null ) return false ; // Create an empty queue for // level order traversal Queue<node > q = new LinkedList(); // Enqueue Root and initialize height q.add(root); // Queue based level order traversal while (q.size() > 0 ) { // See if current node is same as x node node = q.peek(); if (node.data == x) return true ; // Remove current node and enqueue its children q.remove(); if (node.left != null ) q.add(node.left); if (node.right != null ) q.add(node.right); } return false ; } // Driver code public static void main(String ags[]) { node NewRoot = null ; node root = new node( 2 ); root.left = new node( 7 ); root.right = new node( 5 ); root.left.right = new node( 6 ); root.left.right.left = new node( 1 ); root.left.right.right = new node( 11 ); root.right.right = new node( 9 ); root.right.right.left = new node( 4 ); System.out.print((iterativeSearch(root, 6 )? "Found" : "Not Found" )); System.out.print((iterativeSearch(root, 12 )? "Found" : "Not Found" )); } } // This code is contributed by Arnab Kundu |
Python3
# Iterative level order traversal based # method to search in Binary Tree # importing Queue from queue import Queue # Helper function that allocates a # new node with the given data and # None left and right pointers. class newNode: def __init__( self , data): self .data = data self .left = self .right = None # An iterative process to search an # element x in a given binary tree def iterativeSearch(root, x): # Base Case if (root = = None ): return False # Create an empty queue for level # order traversal q = Queue() # Enqueue Root and initialize height q.put(root) # Queue based level order traversal while (q.empty() = = False ): # See if current node is same as x node = q.queue[ 0 ] if (node.data = = x): return True # Remove current node and # enqueue its children q.get() if (node.left ! = None ): q.put(node.left) if (node.right ! = None ): q.put(node.right) return False # Driver Code if __name__ = = '__main__' : root = newNode( 2 ) root.left = newNode( 7 ) root.right = newNode( 5 ) root.left.right = newNode( 6 ) root.left.right.left = newNode( 1 ) root.left.right.right = newNode( 11 ) root.right.right = newNode( 9 ) root.right.right.left = newNode( 4 ) if iterativeSearch(root, 6 ): print ( "Found" ) else : print ( "Not Found" ) if iterativeSearch(root, 12 ): print ( "Found" ) else : print ( "Not Found" ) # This code is contributed by PranchalK |
C#
// Iterative level order traversal // based method to search in Binary Tree using System; using System.Collections.Generic; class GFG { /* A binary tree node has data, left child and right child */ public class node { public int data; public node left; public node right; /* Constructor that allocates a new node with the given data and null left and right pointers. */ public node( int data) { this .data = data; this .left = null ; this .right = null ; } }; // An iterative process to search // an element x in a given binary tree static Boolean iterativeSearch(node root, int x) { // Base Case if (root == null ) return false ; // Create an empty queue for // level order traversal Queue<node > q = new Queue<node>(); // Enqueue Root and initialize height q.Enqueue(root); // Queue based level order traversal while (q.Count > 0) { // See if current node is same as x node node = q.Peek(); if (node.data == x) return true ; // Remove current node and // enqueue its children q.Dequeue(); if (node.left != null ) q.Enqueue(node.left); if (node.right != null ) q.Enqueue(node.right); } return false ; } // Driver code public static void Main(String []ags) { node root = new node(2); root.left = new node(7); root.right = new node(5); root.left.right = new node(6); root.left.right.left = new node(1); root.left.right.right = new node(11); root.right.right = new node(9); root.right.right.left = new node(4); Console.WriteLine((iterativeSearch(root, 6) ? "Found" : "Not Found" )); Console.Write((iterativeSearch(root, 12) ? "Found" : "Not Found" )); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Iterative level order traversal // based method to search in Binary Tree /* A binary tree node has data, left child and right child */ class node { constructor(data) { this .data = data; this .left = null ; this .right = null ; } } // An iterative process to search // an element x in a given binary tree function iterativeSearch(root,x) { // Base Case if (root == null ) return false ; // Create an empty queue for // level order traversal let q = []; // Enqueue Root and initialize height q.push(root); // Queue based level order traversal while (q.length > 0) { // See if current node is same as x let node = q[0]; if (node.data == x) return true ; // Remove current node and enqueue its children q.shift(); if (node.left != null ) q.push(node.left); if (node.right != null ) q.push(node.right); } return false ; } // Driver code let NewRoot = null ; let root = new node(2); root.left = new node(7); root.right = new node(5); root.left.right = new node(6); root.left.right.left = new node(1); root.left.right.right = new node(11); root.right.right = new node(9); root.right.right.left = new node(4); document.write((iterativeSearch(root, 6)? "Found<br>" : "Not Found<br>" )); document.write((iterativeSearch(root, 12)? "Found<br>" : "Not Found<br>" )); // This code is contributed by rag2127 </script> |
输出：
FoundNot Found
下面的实现使用 迭代前序遍历 在二叉树中寻找x
C++
// An iterative method to search an item in Binary Tree #include <iostream> #include <stack> using namespace std; /* A binary tree node has data, left child and right child */ struct node { int data; struct node* left, *right; }; /* Helper function that allocates a new node with the given data and NULL left and right pointers.*/ struct node* newNode( int data) { struct node* node = new struct node; node->data = data; node->left = node->right = NULL; return (node); } // iterative process to search an element x in a given binary tree bool iterativeSearch(node *root, int x) { // Base Case if (root == NULL) return false ; // Create an empty stack and push root to it stack<node *> nodeStack; nodeStack.push(root); // Do iterative preorder traversal to search x while (nodeStack.empty() == false ) { // See the top item from stack and check if it is same as x struct node *node = nodeStack.top(); if (node->data == x) return true ; nodeStack.pop(); // Push right and left children of the popped node to stack if (node->right) nodeStack.push(node->right); if (node->left) nodeStack.push(node->left); } return false ; } // Driver program int main( void ) { struct node*NewRoot=NULL; struct node *root = newNode(2); root->left = newNode(7); root->right = newNode(5); root->left->right = newNode(6); root->left->right->left=newNode(1); root->left->right->right=newNode(11); root->right->right=newNode(9); root->right->right->left=newNode(4); iterativeSearch(root, 6)? cout << "Found" : cout << "Not Found" ; iterativeSearch(root, 12)? cout << "Found" : cout << "Not Found" ; return 0; } |
JAVA
// An iterative method to search an item in Binary Tree import java.util.*; class GFG { /* A binary tree node has data, left child and right child */ static class node { int data; node left, right; }; /* Helper function that allocates a new node with the given data and null left and right pointers.*/ static node newNode( int data) { node node = new node(); node.data = data; node.left = node.right = null ; return (node); } // iterative process to search // an element x in a given binary tree static boolean iterativeSearch(node root, int x) { // Base Case if (root == null ) return false ; // Create an empty stack and push root to it Stack<node> nodeStack = new Stack<node>(); nodeStack.push(root); // Do iterative preorder traversal to search x while (nodeStack.empty() == false ) { // See the top item from stack and // check if it is same as x node node = nodeStack.peek(); if (node.data == x) return true ; nodeStack.pop(); // Push right and left children // of the popped node to stack if (node.right != null ) nodeStack.push(node.right); if (node.left != null ) nodeStack.push(node.left); } return false ; } // Driver Code public static void main(String[] args) { node NewRoot = null ; node root = newNode( 2 ); root.left = newNode( 7 ); root.right = newNode( 5 ); root.left.right = newNode( 6 ); root.left.right.left = newNode( 1 ); root.left.right.right = newNode( 11 ); root.right.right = newNode( 9 ); root.right.right.left = newNode( 4 ); if (iterativeSearch(root, 6 )) System.out.println( "Found" ); else System.out.println( "Not Found" ); if (iterativeSearch(root, 12 )) System.out.println( "Found" ); else System.out.println( "Not Found" ); } } // This code is contributed by 29AjayKumar |
Python3
# An iterative Python3 code to search # an item in Binary Tree ''' A binary tree node has data, left child and right child ''' class newNode: # Construct to create a newNode def __init__( self , key): self .data = key self .left = None self .right = None # iterative process to search an element x # in a given binary tree def iterativeSearch(root,x): # Base Case if (root = = None ): return False # Create an empty stack and # append root to it nodeStack = [] nodeStack.append(root) # Do iterative preorder traversal to search x while ( len (nodeStack)): # See the top item from stack and # check if it is same as x node = nodeStack[ 0 ] if (node.data = = x): return True nodeStack.pop( 0 ) # append right and left children # of the popped node to stack if (node.right): nodeStack.append(node.right) if (node.left): nodeStack.append(node.left) return False # Driver Code root = newNode( 2 ) root.left = newNode( 7 ) root.right = newNode( 5 ) root.left.right = newNode( 6 ) root.left.right.left = newNode( 1 ) root.left.right.right = newNode( 11 ) root.right.right = newNode( 9 ) root.right.right.left = newNode( 4 ) if iterativeSearch(root, 6 ): print ( "Found" ) else : print ( "Not Found" ) if iterativeSearch(root, 12 ): print ( "Found" ) else : print ( "Not Found" ) # This code is contributed by SHUBHAMSINGH10 |
C#
// An iterative method to search an item in Binary Tree using System; using System.Collections.Generic; class GFG { /* A binary tree node has data, left child and right child */ class node { public int data; public node left, right; }; /* Helper function that allocates a new node with the given data and null left and right pointers.*/ static node newNode( int data) { node node = new node(); node.data = data; node.left = node.right = null ; return (node); } // iterative process to search // an element x in a given binary tree static bool iterativeSearch(node root, int x) { // Base Case if (root == null ) return false ; // Create an empty stack and.Push root to it Stack<node> nodeStack = new Stack<node>(); nodeStack.Push(root); // Do iterative preorder traversal to search x while (nodeStack.Count != 0) { // See the top item from stack and // check if it is same as x node node = nodeStack.Peek(); if (node.data == x) return true ; nodeStack.Pop(); // Push right and left children // of the.Popped node to stack if (node.right != null ) nodeStack.Push(node.right); if (node.left != null ) nodeStack.Push(node.left); } return false ; } // Driver Code public static void Main(String[] args) { node root = newNode(2); root.left = newNode(7); root.right = newNode(5); root.left.right = newNode(6); root.left.right.left = newNode(1); root.left.right.right = newNode(11); root.right.right = newNode(9); root.right.right.left = newNode(4); if (iterativeSearch(root, 6)) Console.WriteLine( "Found" ); else Console.WriteLine( "Not Found" ); if (iterativeSearch(root, 12)) Console.WriteLine( "Found" ); else Console.WriteLine( "Not Found" ); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // An iterative method to search an item in Binary Tree /* A binary tree node has data, left child and right child */ class Node { constructor() { this .data = 0; this .left = null ; this .right = null ; } }; /* Helper function that allocates a new node with the given data and null left and right pointers.*/ function newNode(data) { var node = new Node(); node.data = data; node.left = node.right = null ; return (node); } // iterative process to search // an element x in a given binary tree function iterativeSearch(root, x) { // Base Case if (root == null ) return false ; // Create an empty stack and.push root to it var nodeStack = []; nodeStack.push(root); // Do iterative preorder traversal to search x while (nodeStack.length != 0) { // See the top item from stack and // check if it is same as x var node = nodeStack[nodeStack.length - 1]; if (node.data == x) return true ; nodeStack.pop(); // push right and left children // of the.Popped node to stack if (node.right != null ) nodeStack.push(node.right); if (node.left != null ) nodeStack.push(node.left); } return false ; } // Driver Code var root = newNode(2); root.left = newNode(7); root.right = newNode(5); root.left.right = newNode(6); root.left.right.left = newNode(1); root.left.right.right = newNode(11); root.right.right = newNode(9); root.right.right.left = newNode(4); if (iterativeSearch(root, 6)) document.write( "Found<br>" ); else document.write( "Not Found<br>" ); if (iterativeSearch(root, 12)) document.write( "Found<br>" ); else document.write( "Not Found<br>" ); </script> |
输出：
FoundNot Found
https://www.youtube.com/watch?v=-jREIGMJ8Tg
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
