Going from left to right build a Binary Search Tree. 10,5,20,13,6,54,5,66,89,2,4

Question

Going from left to right build a Binary Search Tree.

10,5,20,13,6,54,5,66,89,2,4,1,7,99,75,60

Explanation / Answer

//Binary Search Tree Program #include #include using namespace std; class BinarySearchTree { private: struct tree_node { tree_node* left; tree_node* right; int data; }; tree_node* root; public: BinarySearchTree() { root = NULL; } bool isEmpty() const { return root==NULL; } void print_inorder(); void inorder(tree_node*); void print_preorder(); void preorder(tree_node*); void print_postorder(); void postorder(tree_node*); void insert(int); void remove(int); }; // Smaller elements go left // larger elements go right void BinarySearchTree::insert(int d) { tree_node* t = new tree_node; tree_node* parent; t->data = d; t->left = NULL; t->right = NULL; parent = NULL; // is this a new tree? if(isEmpty()) root = t; else { //Note: ALL insertions are as leaf nodes tree_node* curr; curr = root; // Find the Node's parent while(curr) { parent = curr; if(t->data > curr->data) curr = curr->right; else curr = curr->left; } if(t->data data) parent->left = t; else parent->right = t; } } void BinarySearchTree::remove(int d) { //Locate the element bool found = false; if(isEmpty()) { coutright; else curr = curr->left; } } if(!found) { coutleft == NULL && curr->right == NULL) { if(parent->left == curr) parent->left = NULL; else parent->right = NULL; delete curr; return; } //Node with 2 children // replace node with smallest value in right subtree if (curr->left != NULL && curr->right != NULL) { tree_node* chkr; chkr = curr->right; if((chkr->left == NULL) && (chkr->right == NULL)) { curr = chkr; delete chkr; curr->right = NULL; } else // right child has children { //if the node's right child has a left child // Move all the way down left to locate smallest element if((curr->right)->left != NULL) { tree_node* lcurr; tree_node* lcurrp; lcurrp = curr->right; lcurr = (curr->right)->left; while(lcurr->left != NULL) { lcurrp = lcurr; lcurr = lcurr->left; } curr->data = lcurr->data; delete lcurr; lcurrp->left = NULL; } else { tree_node* tmp; tmp = curr->right; curr->data = tmp->data; curr->right = tmp->right; delete tmp; } } return; } } void BinarySearchTree::print_inorder() { inorder(root); } void BinarySearchTree::inorder(tree_node* p) { if(p != NULL) { if(p->left) inorder(p->left); coutright); cout

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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