CMP 507 Homework #9		 

1. 	Given the following key values: 7, 16, 49, 82, 5, 31, 6, 2, 44, 
generate the heap.

		

		

	














































2. 	Write a function to display the tree by inorder traversal.P365

	void TraverseInOrder(TreeNode *T)
	{
	  if (T != NULL)
	  {
		TraversInOrder(T->LLink);
		Visit(T);
		TraverseInOrder(T->RLink);
	  }
       	}

3. 	Write a function to display the tree by preorder traversal.

	void TraversePreOrder(TreeNode *T)
	{
	  if (T != NULL)
	  {
		Visit(T);
		TraversePreOrder(T->LLink);
		TraversePreOrder(T->RLink);
	  }
       	}


4.	Write a function to display the tree by postorder traversal.


	void TraversePostOrder(TreeNode *T)
	{
	  if (T != NULL)
	  {
		TraversePostOrder(T->LLink);
		TraversePostOrder(T->RLink);
		Visit(T);
	  }
       	}

5.	Write a function to display the tree by level order traversal.
	#include<stdio.h>
	#include"QueueInterface.h>

	void LevelORderTraversal(TreeNode *T)
	{
	  Queue Q; TreeNode *Nl

	  initializeQueue(&Q);
	  insert(T,&Q);
	  while(!Empty(&Q)){
		Remove(&Q,&N);
		if(N != NULL){
		  printf(%c:,N->Symbol);
		  insert(N->LLink,&Q);
		  insert(N->RLink,&Q);
		}
	   }
}

6. Write a non-recursive function for fibonacci sequence.

int Fibonacci (int n)
	{
		int I, first, second, fibonacci;
		if  ( n < 2 )  return 1;
		first = 1;
		second = 1;
		for ( I = 3 ; I <= n ; I + + )
			{ 
fibonacci = first + second ;
first = second ;
second = fibonacci ;
			}
		return (fibonacci) ;
	}

7. Show the list after each exchange of elements by quick sort. 

List 1:	34, 23, 5, 7, 9, 45, 38, 4, 2.
List 2:	23, 5, 7, 9, 4, 2, 34, 45, 38.
List 3:	5, 7, 9, 4, 2, 23, 34, 38, 45.
List 4:	4, 2, 5, 7, 9, 23, 34, 38, 45.
List 5:	2, 4, 5, 7, 9, 23, 34, 38, 45.

8. Given a number sequence:26, 5, 37, 1, 61, 11, 59, 15, 48, 19. Show 
the number of sequence after each iteration of insertion sort.

List 1:	26, 5, 37, 1, 61, 11, 59, 15, 48, 19.
List 2:	5, 26, 37, 1, 61, 11, 59, 15, 48, 19.
List 3:	5, 26, 37, 1, 61, 11, 59, 15, 48, 19.
List 4:	5, 26, 37, 1, 61, 11, 59, 15, 48, 19.
List 5:	1, 5, 26, 37, 61, 11, 59, 15, 48, 19.
List 6:	1, 5, 26, 37, 61, 11, 59, 15, 48, 19.
List 7:	1, 5, 26, 37, 61, 11, 59, 15, 48, 19.
List 8:	1, 5, 11, 26, 37, 61, 59, 15, 48, 19.
List 9:	1, 5, 11, 26, 37, 59, 61, 15, 48, 19.
List 10:	1, 5, 11, 15, 26, 37, 59, 61, 48, 19.
List 11:	1, 5, 11, 15, 26, 37, 48, 59, 61, 19.
List 12:	1, 5, 11, 15, 19, 26, 37, 59, 61, 48.

9. Given the input sequence: 77, 61, 59, 48, 19, 11, 26, 15, 1, 5. 
Construct the heap tree and heap tree at each stage of heap sort.










































































10. Describe the algorithm of radix sort.

The following procedure assume that each element in the n-element 
array A has d digits, where digits 1 is the lowest-order digits d is the 
highest-order digits.

Radix-Sort (A,d)
For i=1 to d
Do use any stable sort to sort array A on digits i.

<END>

4

1