Exercicios bst

Prévia do material em texto

cs311 Yoshii HW4 Binary Search Tree (based on week 8)
===================================================
DUE: Week 10 Tuesday at the beginning of class
TOTAL: 33 pts Your score is:
Your name: Lucas Henrique Silva	
Date turned in: oct/28/2014
---------------------------------------------------
Purpose: To learn the representation and implementation of a binary search tree.
----------------------------------------------------
Questions: [3pts] 				Your score:
Q1. Depth first traversal is the same as Pre-order traversal.
Q1. When we add a new node to an existing binary search tree, it will always become a leaf .
Q2. When we delete a node with 2 children from a binary search tree, we replace the node with 
 The biggest element of the left side or the smallest element in the right side .
PROGRAMMING: Binary Search Tree [30pts] 		Your score:
=============================================================
Your job is to complete my binstree.C according to my instructions
And test it with my hw4Client.C
Some of these files in /cs/cs311RY are in WORD (.doc) format
to show in blue exactly where changes need to be made.
Q) State of the program statement [2pts] <answer here>
Does your program compile without errors?
<No Errors>
List any bugs you are aware of, or state “No bugs”:
<No Bugs>
Submit: Stapled in this order!!!
this assignment sheet
my binstree.h	 	unchanged
binstree.C 		updated 
my Hw4Client.C	unchanged
test results (one run) which is either a script or screen dump
showing exactly what was compiled and what was executed.
End
// =========================================================
//HW4 BST
//Your name: Lucas Henrique Silva
//Complier: GCC
//File type: declaration file binstree.h
//================================================================
// CS311: BST header file for HW4 - Rika Yoshii
// tree element type is int for now
typedef int elem_t; // elem_t is hidden from the client
// definition of what a Vertex is - also hidden from the client
struct Vertex
{
 Vertex *Left;
 elem_t Elem;
 Vertex *Right;
};
class BST
{
 private:
 Vertex *Root; // data member is Root which is a pointer to the root vertex
 public:
 BST(); // constructor point the root to NULL
 ~BST(); // destructor calls dtraverse to destroy the dynamic tree
 // PURPOSE: these will show the vertices in IN order
 // TO CALL: No parameter to ShowInOrder but provide a pointer to
 // the root vertex in calling INorderTraversal
 void ShowInOrder();
 void INorderTraversal(Vertex*);
 // PURPOSE: these will show the vertices in PRE order - same as Depth First
 // TO CALL: No parameter to ShowPreOrder but provide a pointer to
 // the root vertex in calling PREorderTraversal
 void ShowPreOrder();
 //describe above
 void PREorderTraversal(Vertex*);
 // PURPOSE: This inserts a new vertex into the BST
 // TO CALL: provide the element to be inserted into the tree
 void Insertvertex(elem_t);
 // PURPOSE: This deletes a vertex with the given element - calls remove and
 // findMax (see below)
 // TO CALL: procide the element to be removed from the tree
 void DeleteVertex(elem_t);
 protected: // utility functions follow - these are not for the clients to use
 // These were created to implement the public methods
 void dtraverse(Vertex*); // traverse and delete all vertices in post order
 // PURPOSE: remove the vertex passed as a parameter
 // PARAM: the vertex that u want to delete and the parent of that vertex
 void remove(Vertex*, Vertex*); // removes the vertex knowing its parent
 // PURPOSE: find the max element of the left sub-tree and also deletes it
 // PARAM: The vertex that u want to replace
 elem_t findMax(Vertex*);
};
// =========================================================
//HW4 BST
//Your name: Lucas Henrique Silva
//Complier: GCC
//File type: implementation file binstree.cpp
//================================================================
// CS311 : This is the BST implementation file template by Rika Yoshii
// ** Look for ** comments to complete this file for HW4
// Make sure all { } match.
#include <iostream>
using namespace std;
#include "binstree.h"
// constructor initializes Root
BST::BST(){
 Root = NULL; // This is an empty tree
}
// destructor must completely destroy the tree
BST::~BST(){
 dtraverse(Root); // traverse to delete all vertices in post order
 Root = NULL;
}
// PURPOSE: Does Post Order traversal of the tree and deletes each vertex
// PARAM: pointer to the vertex to be deleted
void BST::dtraverse(Vertex *V){ // post order traversal
 if (V != NULL){
 dtraverse(V->Left); // visit left sub tree of V
 dtraverse(V->Right); // visit right sub tree of V
 delete V; // deletes V
 }
}
// PURPOSE: Show elements in IN order traversal from the Root
void BST::ShowInOrder(){
 cout << "Elements in the IN order: " << endl;
 INorderTraversal(Root); // start in-order traversal from the root
}
// PURPOSE: Does IN order traversal from V recursively
// PARAM: pointer to the vertex to visit right now
void BST::INorderTraversal(Vertex *V){
 if (V != NULL){
 // ** traverse left sub-tree of V recursively
 if(((V)->Left)!= NULL){
 INorderTraversal((V)->Left);
 }
 // ** display V's element and do endl;
 cout << (V)->Elem << "\t";
 // ** traverse right sub-tree of V recursively
 if(((V)->Right)!= NULL){
 INorderTraversal((V)->Right);
 }
 }
}
// PURPOSE: Show elements in PRE order traversal from the Root
// This is the same as Depth First Traversal
void BST::ShowPreOrder(){
 cout << "Elements in the PRE order:" << endl;
 PREorderTraversal(Root); // start pre-order traversal from the root
 cout << "\n";
}
// PURPOSE: Does PRE order traversal from V recursively
// PARAM: pointer to the vertex to be visited now
void BST::PREorderTraversal(Vertex *V){
 if (V != NULL){
 // ** display V's element and do endl;
 cout << (V)->Elem << "\t";
 // ** traverse left sub-tree of V recursively
 if(((V)->Left)!= NULL){
 PREorderTraversal((V)->Left);
 }
 // ** traverse right sub-tree of V recursively
 if(((V)->Right)!= NULL){
 PREorderTraversal((V)->Right);
 }
 }
}
// PURPOSE: Adds a vertex to the binary search tree for new element
// PARAM: the new element E
// ALGORITHM: We will do this iteratively (not recursively)
// - smaller than the current -> go to the left
// - bigger than the current -> go to the right
// - cannot go any further -> add it there
void BST::Insertvertex(elem_t E){
 Vertex *N; // N will point to the new vertex to be inserted
 N = new Vertex; // a new vertex is created
 N->Left = NULL; // make sure it does not
 N->Right = NULL; // point to anything
 N->Elem = E; // put element E in it
 cout << "Trying to insert " << E << endl;
 if (Root == NULL){ // Special case: we have a brand new empty tree
 Root = N; // the new vertex is added as the root
 cout << "...adding " << E << " as the root" << endl;
 }
 // the tree is not empty
 else{
 Vertex *V; // V will point to thecurrent vertex
 Vertex *Parent; // Parent will point to V's parent
 V = Root; // start with the root as V
 while (V != NULL){ // go down the tree until you cannot go any further
 if (N->Elem == V->Elem){// special case
 	 cout << "...error: the element already exists" << endl;
	 		 return;
 }
 else if (N->Elem < V->Elem){ // what I have is smaller than V
 cout << "...going to the left" << endl;
 // ** change Parent to be V to go down
 Parent=V;
 // ** change V to be V's Left
 V=V->Left;
	 }
 else { // what I have is bigger than V
 cout << "...going to the right" << endl;
	 	// ** change Parent to be V to go down
	 	Parent=V;
	 	// ** change V to be V's Right
	 	V=V->Right;
	 }
 }//end of while
 // reached NULL -- Must add N as the Parent's child
 if (N->Elem < Parent->Elem){
	 // ** Parent's Left should point to the same place as N
 cout << "...adding " << E << " as the left child of " << Parent->Elem << endl;	\
 Parent->Left=N;
 }
 else{
	 // ** Parent's Right should point to the same place as N
 cout << "...adding " << E << " as the right child of "<< Parent->Elem << endl;
 Parent->Right=N;
 }
 }// end of normal case
}// end of InsertVertex
// PURPOSE: Deletes a vertex that has E as its element.
// PARAM: element E to be removed
// ALGORITHM: First we must find the vertex then call Remove
void BST::DeleteVertex(elem_t E)
{
 cout << "Trying to delete " << E << endl;
 Vertex *V; // the current vertex
 Vertex *Parent = NULL; // its parent
 if ((E == Root->Elem) && (Root->Left == NULL) && (Root->Right == NULL)){
 cout << "...deleting the lonely root" << endl;
 delete Root;
 Root = NULL;
 return;
 } // only the Root was there and deleted it
// ** if V is the root with one child
 //removing left child
 if(E==Root->Elem && Root->Right == NULL){
 Vertex *Aux;
 Aux = Root;
 Root= Root->Left;
 delete Aux;
 return;
 }
 //removing right child
 else if(E==Root->Elem && Root->Left == NULL){
 ;
 Vertex *Aux;
 Aux = Root;
 Root= Root->Right;
 delete Aux;
 return;
 }
// Otherwise deleting something else
 V = Root; // start with the root to look for E
 while (V != NULL)
 {
 cout << "ELEMENTS:\n " << "looking for: " << E << " CURRENT: " << V->Elem;
 if ( E == V->Elem){ // found it
 cout << "...removing " << V->Elem << endl;
 // ** call remove here to remove V
 remove(V,Parent);
 return;
 }
	 else
 if (E < V->Elem)
 { cout << "...going to the left" << endl;
 // ** update Parent and V here to go down
 Parent=V;
 V=V->Left;
 }
 else
 { cout << "...going to the right" << endl;
 // ** update Parent and V here to go down
 Parent=V;
 V=V->Right;
 }
 }// end of while
 // reached NULL -- did not find it
 cout << "Did not find the key in the tree." << endl;
}// end of DeleteVertex
// PURPOSE: Removes vertex pointed to by V
// PARAM: V and its parent pointer P
// Case 1: it is a leaf – delete it
// Case 2: it has just one child – bypass it
// Case 3: it has two children – replace it with the max of the left //subtree
void BST::remove(Vertex *V, Vertex *P){
 // ** if V is a leaf (case 1)
 if(((V)->Left==NULL) && ((V)->Right==NULL) ){
 cout << ".. removing a leaf" << endl;
 // ** if V is a left child of P
 if((P)->Left== (V)){
 // ** delete V and also make Parent's left NULL
 delete V;
 (P)->Left=NULL;
 }
 else { // V is a right child of the Parent
 // ** delete V and also make Parent's right NULL
 delete V;
 (P)->Right=NULL;
 }
 }
 // ** else if V has just the left child (case 2)
 else if((V)->Left!=NULL && (V)->Right==NULL){
 cout << "removing a vertex with just the left child" << endl;
 // ** Make Parent’s left or right point to the left child and delete V (You need if then else to determine left or right)
 if((P)->Left== (V)){
 Vertex *Aux=V;
 P->Left=V->Left;
 delete Aux;
 }
 else {//point to the right child
 Vertex *Aux=V;
 P->Right=V->Left;
 delete Aux;
 }
 }
 // **else if V has just the right child
 else if((V)->Left==NULL && (V)->Right!=NULL){
 cout << "removing a vertex with just the right child" << endl;
 // ** Make Parent’s left or right point to the right child and delete V (need if then else to determine left or right)
 if((P)->Left== (V)){
 Vertex *Aux=V;
 P->Left=V->Right;
 delete Aux;
 }
 else {//point to the right child
 Vertex *Aux=V;
 P->Right=V->Right;
 delete Aux;
 }
 }
 else // V has two children (case 3)
 { cout << "...removing an internal vertex with children" << endl;
 cout << ".....find the MAX of its left sub-tree" << endl;
 elem_t Melem;
 Vertex *Aux=V;
 Melem = findMax(Aux); // find MAX element in the left sub-tree of V
 cout << ".....replacing " << Aux->Elem << " with " << Melem << endl;
 // ** Replace V's element with Melem here
 V->Elem=Melem;
 }
 }// end of remove
// PURPOSE: Finds the Maximum element in the left sub-tree of V
elem_t BST::findMax(Vertex *V)
{
 Vertex *Parent = V;
 V = V->Left; // start with the left child of V
 // ** while the right child of V is still available
 while(V->Right!=NULL){
 // ** update Parent and V to go to the right
 Parent=V;
 V=V->Right;
 }
 // reached NULL Right -- V now has the MAX element
 elem_t X = V->Elem;
 cout << ".....Max is " << X << endl;
 remove(V, Parent); // remove the MAX vertex
 return X; // return the MAX element
}// end of FindMax
// CS311 This client tests the BST class - (by Rika Yoshii)
#include <iostream>
using namespace std;
#include "binstree.h"
int main()
{
 BST MyTree; // my first binary search tree
 for(int i = 1; i <=9 ; i=i+2) // inserting 1,3,5,7,9 into the tree
 MyTree.Insertvertex(i);
 for(int i = 10; i >=2 ; i=i-2) // inserting 10,8,6,4,2 into the tree
 MyTree.Insertvertex(i);
 MyTree.ShowInOrder(); // should show in the sorted order
 
 MyTree.ShowPreOrder(); // should show the parent before children//********************************************************
 cout << "=== Starting a new tree with 3 nodes ===="<< endl;
 BST Nums1; // Nums1 is the second binary search tree
 Nums1.Insertvertex(1);
 Nums1.Insertvertex(2);
 Nums1.Insertvertex(3);
 Nums1.DeleteVertex(1); // delete the root
 Nums1.ShowInOrder();
 //********************************************************
 cout << "=== Starting a new tree with 3 nodes ===="<< endl;
 BST Nums2; // Nums2 is another binary search tree
 Nums2.Insertvertex(10);
 Nums2.Insertvertex(9);
 Nums2.Insertvertex(8);
 Nums2.DeleteVertex(10); // delete the root
 Nums2.ShowInOrder();
 //**********************************************************
 cout << "=== Starting a new tree with 7 nodes ===="<< endl;
 BST Nums; // Nums is the last binary search tree
 // creates a shallowest 7 node tree (draw this)
 Nums.Insertvertex(3); // root
 Nums.Insertvertex(1); // level 1 L
 Nums.Insertvertex(2); // level 2 R
 Nums.Insertvertex(0); // level 2 L
 Nums.Insertvertex(5); // level 1 R
 Nums.Insertvertex(6); // level 2 R
 Nums.Insertvertex(4); // level 2 L
 Nums.Insertvertex(4); // should be an error
 //and show the nodes in sorted order
 Nums.ShowInOrder();
 //and then delete some nodes 
 
 // - level 2 right most leaf
 Nums.DeleteVertex(6);
 
 // - level 1 right mode node with one left child
 Nums.DeleteVertex(5);
 
 // - level 0 root with two children
 Nums.DeleteVertex(3);
 
 // - deleting a non-existing one
 Nums.DeleteVertex(7);
 
 //and then show the remaining nodes in sorted order
 Nums.ShowInOrder();
 
 
}
Script started on Tue 28 Oct 2014 09:26:29 AM PDT
�]0;henri011@empress:~/CS311/HW_8/HW_8
[henri011@empress HW_8]$ ls
�[00m�[00;32ma.out�[00m �[00mbinstree.cpp�[00m �[00mhw4Client.C�[00m �[00mHW_8.depend�[00m �[00;34mobj�[00m
�[00;34mbin�[00m �[00mbinstree.h�[00m �[00mHW_8.cbp�[00m �[00mHW_8.layout�[00m �[00mresults.txt�[00m
�[m�]0;henri011@empress:~/CS311/HW_8/HW_8
[henri011@empress HW_8]$ ./a.ot
Trying to insert 1
...adding 1 as the root
Trying to insert 3
...going to the right
...adding 3 as the right child of 1
Trying to insert 5
...going to the right
...going to the right
...adding 5 as the right child of 3
Trying to insert 7
...going to the right
...going to the right
...going to the right
...adding 7 as the right child of 5
Trying to insert 9
...going to the right
...going to the right
...going to the right
...going to the right
...adding 9 as the right child of 7
Trying to insert 10
...going to the right
...going to the right
...going to the right
...going to the right
...going to the right
...adding 10 as the right child of 9
Trying to insert 8
...going to the right
...going to the right
...going to the right
...going to the right
...going to the left
...adding 8 as the left child of 9
Trying to insert 6
...going to the right
...going to the right
...going to the right
...going to the left
...adding 6 as the left child of 7
Trying to insert 4
...going to the right
...going to the right
...going to the left
...adding 4 as the left child of 5
Trying to insert 2
...going to the right
...going to the left
...adding 2 as the left child of 3
Elements in the IN order: 
1	2	3	4	5	6	7	8	9	10	Elements in the PRE order:
1	3	2	5	4	7	6	9	8	10	
=== Starting a new tree with 3 nodes ====
Trying to insert 1
...adding 1 as the root
Trying to insert 2
...going to the right
...adding 2 as the right child of 1
Trying to insert 3
...going to the right
...going to the right
...adding 3 as the right child of 2
Trying to delete 1
Elements in the IN order: 
2	3	=== Starting a new tree with 3 nodes ====
Trying to insert 10
...adding 10 as the root
Trying to insert 9
...going to the left
...adding 9 as the left child of 10
Trying to insert 8
...going to the left
...going to the left
...adding 8 as the left child of 9
Trying to delete 10
Elements in the IN order: 
8	9	=== Starting a new tree with 7 nodes ====
Trying to insert 3
...adding 3 as the root
Trying to insert 1
...going to the left
...adding 1 as the left child of 3
Trying to insert 2
...going to the left
...going to the right
...adding 2 as the right child of 1
Trying to insert 0
...going to the left
...going to the left
...adding 0 as the left child of 1
Trying to insert 5
...going to the right
...adding 5 as the right child of 3
Trying to insert 6
...going to the right
...going to the right
...adding 6 as the right child of 5
Trying to insert 4
...going to the right
...going to the left
...adding 4 as the left child of 5
Trying to insert 4
...going to the right
...going to the left
...error: the element already exists
Elements in the IN order: 
0	1	2	3	4	5	6	Trying to delete 6
ELEMENTS:
 looking for: 6 CURRENT: 3...going to the right
ELEMENTS:
 looking for: 6 CURRENT: 5...going to the right
ELEMENTS:
 looking for: 6 CURRENT: 6...removing 6
.. removing a leaf
Trying to delete 5
ELEMENTS:
 looking for: 5 CURRENT: 3...going to the right
ELEMENTS:
 looking for: 5 CURRENT: 5...removing 5
removing a vertex with just the left child
Elements in the IN order: 
Trying to delete 3
ELEMENTS:
 looking for: 3 CURRENT: 3...removing 3
...removing an internal vertex with children
.....find the MAX of its left sub-tree
.....Max is 2
.. removing a leaf
.....replacing 3 with 2
Trying to delete 7
ELEMENTS:
 looking for: 7 CURRENT: 2...going to the right
ELEMENTS:
 looking for: 7 CURRENT: 4...going to the right
Did not find the key in the tree.
Elements in the IN order: 
0	1	2	4	�]0;henri011@empress:~/CS311/HW_8/HW_8
[henri011@empress HW_8]$ exit
exit
Script done on Tue 28 Oct 2014 09:27:13 AM PDT