Question
In C++, create a Binary Search Tree. Make sure it follows the details and runs in order to recieve points.
Create a node class/struct
-Data field
-2 self referential pointers
Create a BST class/struct
-Node field
Methods:
Add (data)
-Adds the data to the tree in sorted order.
Print()
-Prints all the nodes using inorder traversal
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