CMPSC 24 Lecture 11: Lecture 11 - Binary Search Tree, Search, Insert, and In Order Traversal
Document Summary
Treenode *n = root; while(n!=0 && n->item != key){ if(key < n->item){ n = n -> left; else{ n = n-> right; return n; Inserting a node if(info < current node) insert to left; else if (info > current node) insert to right; else. One child: swap child and parent and delete the new child. Two children: find min in right subtree and swap with target node, then delete swapped node. In order void inordertraversal(treenode *n){ if(n != 0){ inordertraversal(n - > left); //a visit(n); //b inordertraverse(n->right); //c. Pre-order: b a c; post-order a c b. Treenode* root; void insertprivate(int info, treenode *ptr); void inorderprivate(treenode* ptr); Bst::bst(){ root = null; void bst::insert(int info){ if(root == null){ Treenode *n = new treenode; n -> info = info; n->left = null; n -> right = null; root = n; insertprivate(info, root); else{ void bst::insertprivate(int info, treenode* ptr){ if( info < ptr -> info){ if(ptr->left == null){
