CMPSC 24 Lecture Notes - Lecture 15: Binary Tree
Document Summary
Info in left subtree of is less than info in. Info in right subtree of is greater than info in. When trees are not complete, the array representation wastes space. Array is less flexible than linked node representation. Treenode *n = root; // start at root node while (n != 0 && n->item != key) // iterate until no more branches or item is. // found if (key < n->item) // search left subtree n = n->left; else // search right subtree n = n->right; return n; // either null, or node with key info. Insert to a bst if (info < current node) insert to left; else if (info > current node) insert to right; else - duplicate info - abort insert. Also need a way to signal unsuccessful insert too. Next steps depend on how many children it has. Replace the node with either largest value in its left subtree or smallest in right subtree.
