Search through a binary search tree given the pointer to the first node with an

Question

Search through a binary search tree given the pointer to the first node with an orgainzation of:

leftChild

rightChild   

int x

Another pointer

The above elements are in consecutive memory locations beginning at the pointer. You are trying to find an int x value that matches R0 before the tree null-terminates. If it does, store the other pointer in some register RX.

Explanation / Answer

#include "stdafx.h" #include using namespace std; struct node { int key_value; struct node* left; struct node* right; }; class btree { public: btree(); void insert(int key); bool search(int key); private: void insert(int key, node *leaf); bool search(int key, node *root); node *root; }; btree::btree() { root=NULL; } void btree::insert(int key, node *leaf) { if(keykey_value) { if(leaf->left!=NULL) insert(key, leaf->left); else { leaf->left=new node; leaf->left->key_value=key; leaf->left->left=NULL; //Sets the left child of the child node to null leaf->left->right=NULL; //Sets the right child of the child node to null } } else if(key>=leaf->key_value) { if(leaf->right!=NULL) insert(key, leaf->right); else { leaf->right=new node; leaf->right->key_value=key; leaf->right->left=NULL; //Sets the left child of the child node to null leaf->right->right=NULL; //Sets the right child of the child node to null } } } void btree::insert(int key) { if(root!=NULL) insert(key, root); else { root=new node; root->key_value=key; root->left=NULL; root->right=NULL; } } bool search( int key_value, node *root ) { // Return true if item is one of the items in the binary // sort tree to which root points. Return false if not. if ( root == NULL ) { // Tree is empty, so it certainly doesn't contain item. return false; } else if ( key_value == root->key_value ) { // Yes, the item has been found in the root node. return true; } else if ( key_value key_value ) { // If the item occurs, it must be in the left subtree. return search( key_value, root->left ); } else { // If the item occurs, it must be in the right subtree. return search( key_value, root->right ); } } // end treeContains() bool btree::search(int key) { return search(key, root); } int main() { btree b; int tmp; int s; int x = 1; while (x!=0) { couttmp; b.insert(tmp); couts; b.search(s); if (s == NULL) { cout

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.