CSc 352: Lecture-15

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".)