Bài giảng Data Structures & Algorithms - Chương 7: Trees

Click to edit Master title style Click to edit Master text styles Second level Third level Fourth level Fifth level 05/05/2014 ‹#› Click to edit Master title style Click to edit Master text styles Second level Third level Fourth level Fifth level ‹#› Data Structures & Algorithms Trees 1. THE CONCEPT OF TREES 2. BINARY TREE AND REPRESENTATION 3. BINARY TREE TRAVERSAL 4. BINARY SEARCH TREE 1. THE CONCEPT OF TREES A tree is a set of one or more nodes T: there is a specially designated node called a root The remaining nodes are partitioned into n disjointed set of nodes T1, T2,…,Tn, each of which is a tree. 1. THE CONCEPT OF TREES Example 1. THE CONCEPT OF TREES It’s not a tree Tree 1. THE CONCEPT OF TREES: Some terminology Root Child (left,right) Parent Leaf node Subtree Ancestor of a node Descendant of a node 1. THE CONCEPT OF TREES Degree of a Node of a Tree The degree of a node of a tree is the number of subtrees having this node as a root. Degree of a Tree The degree of a tree is defined as the maximum of degree of the nodes of the tree Level of a Node level of the root node as 1, and incrementing it by 1 as we move from the root towards the subtrees. 2. BINARY TREE AND REPRESENTATION BINARY TREE no node can have a degree of more than 2. The maximum number of nodes at level i will be 2i−1 If k is the depth of the tree then the maximum number of nodes that the tree can have is 2k − 1 = 2k−1 + 2k−2 + … + 20 2. BINARY TREE AND REPRESENTATION BINARY TREE A full binary tree is a binary of depth k having 2k − 1 nodes. If it has key(v) } 	return TreeSearch(k, T.right(v)) 6 9 2 4 1 8 = Insertion To perform operation inser(k, o), we search for key k (using TreeSearch) Assume k is not already in the tree, and let let w be the leaf reached by the search We insert k at node w and expand w into an internal node Example: insert 5 6 9 2 4 1 8 6 9 2 4 1 8 5 > w w 4. BINARY SEARCH TREE Insert new node 4. BINARY SEARCH TREE Insert new node void InsertNode(node* &root,node *newnode) { 	if (root==NULL) 	root=newnode; 	else 	if (root->data>newnode->data) 	InsertNode(root->l,newnode); 	else 	if (root->datadata)	 	InsertNode(root->r,newnode); } Insert node Insert node Insert Order 4. BINARY SEARCH TREE traverse node void preorder(node* r) { if (r!=NULL) 	{	coutdatal); 	inorder(r->r); 	} } 4. BINARY SEARCH TREE traverse node 4. BINARY SEARCH TREE traverse node Exercise 1 1. Build Binary Search Tree from list 10 4 7 12 16 20 30 5 2 26 15 24 12 89 4 32 50 10 6 36 79 5 9 11 Exercise 2 1. Order of: inoder, postorder, preorder of Exercise 3 1. Order of: inoder, postorder, preorder of Search node Count Even/Odd Leaf Sum Even/Odd Height Delete node 1. SEACRCHING NODE node* search(node* &r, int data) { 	if (r==NULL) 	return NULL; 	else 	if (r->data==data) 	return r; 	else 	if (datadata) 	return search (r->l,data);	 	else 	if (data>r->data) 	 return seach(r->r,data);	 } 1. SEACRCHING NODE node* search(node* &r, int data) { 	if ( (r==NULL) || (r->data==data) ) 	return r; 	else 	if (datadata) 	return search (r->l,data);	 	else 	if (data>r->data) 	 return seach(r->r,data);	 } 100 H20 H40 80 NULL NULL H3 H20 120 NULL NULL H40 Node* S=search(r,80) What does S stand for? 2. COUNTING THE NUMBER OF NODES int count(struct tnode *p) { if( p == NULL) 	return(0); else 	 if( p->lchild == NULL && p->rchild == NULL) return(1); else return(1 + (count(p->lchild) + count(p->rchild))); } With Recursion Without Recursion 2. COUNTING THE NUMBER OF NODES int count(struct tnode *p) { if( p == NULL) 	return(0); else return(1 + (count(p->lchild) + count(p->rchild))); } 3. Sum of all nodes int sum(node *p) { if( p == NULL) 	return(0); else return( p->data+sum(p->l)+sum(p->r) ); } 4. COUNTING THE NUMBER OF EVEN (ODD) NODES int counteven(node* r) { 	if (r!=NULL) 	if (r->data%2==0) 	return 	1+ counteven(r->l)+counteven(r->r); 	else 	return 	counteven(r->l)+counteven(r->r); 	else 	return 0; 	 } 5. SUM OF EVEN (ODD) NODES int counteven(node* r) { 	if (r!=NULL) 	if (r->data%2==0) 	???????????????????? 	else 	???????????????????? 	else 	return 0; 	 } 6. Count number of leaf nodes Exercise Count number of leaf nodes 6. Count number of leaf nodes int countleaf(node* r) { 	if (r!=NULL) 	if (r->l==NULL && r->r==NULL) 	return 	1; 	else 	return 	countleaf(r->l)+countleaf(r->r); 	else 	return 0; 	 } 6. Count number of node had 1 child int countleaf(node* r) { 	if (r!=NULL) 	if (????????????????????????????) 	return 	1; 	else 	return 	countleaf(r->l)+countleaf(r->r); 	else 	return 0; 	 } 6. Count number of node had 2 children int countleaf(node* r) { 	if (r!=NULL) 	if (????????????????????????) 	return 	1; 	else 	return 	countleaf(r->l)+countleaf(r->r); 	else 	return 0; 	 } 7. Find height of tree int Height (node* n){if(n==NULL) return 0;else return 1+max(Height (n->l)), Height (n->r));} 8. Delete node Divide into 3 cases Deletion of a Node with No Child Deletion of a Node with one Child Deletion of a Node with two Children 8. Delete node Deletion of a Node with No Child Set the left of y to NULL Dispose of the node pointed to by x 8. Delete node Deletion of a Node with One Child Make the y->left=x->right dispose of the node pointed to by x 8. Delete node Deletion of a Node with two Children 8. Delete node rightmost child of the subtree of the left leftmost child of the subtree of the right But WHY??? Deletion (cont.) We consider the case where the key k to be removed is stored at a node v whose children are both internal we find the internal node w that follows v in an inorder traversal we copy key(w) into node v we remove node w and its left child z (which must be a leaf) by means of operation removeExternal(z) Example: remove 3 3 1 8 6 9 5 v w z 2 5 1 8 6 9 v 2 Deletion (cont.): exercise1: remove 16 Deletion (cont.): exercise1: remove 16 Deletion (cont.): exercise2: remove 16 Deletion (cont.): exercise2: remove 16 Exercise: Write program to delete node END