Binary Trees
Note: All the programs mentioned in this lecture are in:/home/cs352/SUMMER02/lecture15progs/
- Binary Trees - A tree is a finite set of elements called nodes, and a finite set of edges that connect them.(It is a connected graph with no cycles.) - It has a unique node called root. - A leaf node is one that doesn't have any children (i.e. degree-1) - A binary tree is a tree where each node(except the leaves) has two children. - Adv: Usually Its elements can be reached in a logarithmic number of link traversals. See tree.h, traversal.c, createtree.c - Binary Search Trees: Have the special property that the values in any left subtree are less than the value in its parent node, and the values in any right subtree are greater than or equal to the value in its parent node. - Creating a BST: How to insert? - Let "bst" be the pointer with type btree(as defined in tree.h) - If bst is NULL create a new node(allocate space) initialize values, and make bst point to the new node. - ow if the data to be inserted is less than the data stored in bst, call insert with the leftpointer ow call it with the right pointer. How to delete? - Let "item" be the item to be deleted and "parent" be the item that has a pointer to "item". - If "item" is a leaf node, delete the item and set the appr. pointer of "parent" to NULL. - If "item" is a node with one child, set the appr. pointer of "parent" to point at the child of "item" and delete "item". - If "item" is a node with two children, - Find the node "replacement"(the rightmost node in the leftsubtree pointed to by"item") - Replace "item" with "replacement"(making all the necessary pointer changes that will reflect the replacement) (Note 2 cases, if "replacement" has no children, and if "replacement" has a left child are slightly different, in the second case additionaly make the parent of "replacement" to point at the left child of "replacement".)