Trouble traversing Btree

[UberJoker]

Any ideas on how would I be able to traverse this BTree in asceding order? right now I am sorting the data and giving it to my retreival() function to look for the keys. But naturally it visits and prints the data in ascending order because I give it sorted data in the first place. But i dont think thats correct. I sort of need ideas of how to do inorder traversal on this one. As always, any suggestions would be quite appreciated :)

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <string.h>
#include <string>

using namespace std;
const int KeyFieldMax = 20;
const int KeyFieldMaxplus = KeyFieldMax+1;
const int DataFieldMax = 25;
const int DataFieldMaxplus = DataFieldMax+1;

typedef char KeyFieldType[KeyFieldMaxplus];
typedef char DataFieldType[DataFieldMaxplus];

typedef struct
	      {
		KeyFieldType KeyField;
		DataFieldType DataField;
	      }ItemType;


class TableBaseClass
   		    {
  			 public:
   				   virtual bool Empty(void) = 0;
   				   virtual bool Retrieve(KeyFieldType SearchKey, ItemType & Item) = 0;
   			 public:
				   fstream DataFile;   
      				   long NumItems;      
			           char OpenMode;     
   		    };


const int MaxKeys = 4;   

const int MaxKeysPlusOne = MaxKeys + 1;

const int MinKeys = 2;    

const long NilPtr = -1L;   


typedef struct
   	      {
		 int Count;              
		 ItemType Key[MaxKeys];   
		 long Branch[MaxKeysPlusOne];   
   	      } NodeType;



class BTTableClass: public TableBaseClass
  		  {
   		      public:
     				 BTTableClass(char Mode, char * FileName);
   	           	         bool Empty(void);
      				 bool Insert(const ItemType & Item);
      				 bool Retrieve(KeyFieldType SearchKey, ItemType & Item);
    
  		     private:
      				
     				 bool SearchNode(const KeyFieldType Target, int & location) const;
    			         void AddItem(const ItemType & NewItem, long NewRight,NodeType & Node, int Location);
     				 void Split(const ItemType & CurrentItem, long CurrentRight,long CurrentRoot, int Location, ItemType & NewItem,long & NewRight);
     				 void PushDown(const ItemType & CurrentItem, long CurrentRoot,bool & MoveUp, ItemType & NewItem, long & NewRight);
     				 long Root;       
     				 long NumNodes;  
     				 int NodeSize;   
     				 NodeType CurrentNode;   
                  };

















BTTableClass::BTTableClass(char Mode, char * FileName)
   							{
  
   								OpenMode = Mode;
   								NodeSize = sizeof(NodeType);

  								 if (Mode == 'r')
      									{
     									  DataFile.open(FileName, ios::in | ios::binary);
     										 if (DataFile.fail())
          										cout<<"cannot open"<<endl;	

     										 DataFile.read(reinterpret_cast <char *> (&CurrentNode), NodeSize);
     										 if (DataFile.fail())
        									    {  
         										NumItems = 0;
         										NumNodes = 0;
        										Root = NilPtr;
        									    }
      										else   
         									    {
        										NumItems = CurrentNode.Branch[0];
         										NumNodes = CurrentNode.Branch[1];
         										Root = CurrentNode.Branch[2];
         									    }
     
       
   
     									 }
  								else if (Mode == 'w')
      									 {
     									   DataFile.open(FileName, ios::in | ios::out | ios:: trunc | ios::binary);
     										 if (DataFile.fail())
        										 cout<<"cannot open"<<endl;

     											 Root = NilPtr;
     											 NumItems = 0;
     											 NumNodes = 0;   
     											 CurrentNode.Branch[0] = NumItems;
     											 CurrentNode.Branch[1] = NumNodes;
     											 CurrentNode.Branch[2] = Root;
    											 DataFile.seekp(0, ios::beg);
     											 DataFile.write(reinterpret_cast <char *> (&CurrentNode), NodeSize);
     
  
      									 }
  								    else
      									 cout<<"improper mode"<<endl;
   							}





bool BTTableClass::Empty(void)
   			    {   
   				return (Root == NilPtr);
  			    }



bool BTTableClass::SearchNode(const KeyFieldType Target,int & Location) const
   				{
   					bool Found;

  					Found = false;
   					if (strcmp(Target, CurrentNode.Key[0].KeyField) < 0)
      						Location = -1;
  					else
      					   { 
      						Location = CurrentNode.Count - 1;
						while ((strcmp(Target, CurrentNode.Key[Location].KeyField) < 0)&& (Location > 0))
        					      Location--;
												
      							if (strcmp(Target, CurrentNode.Key[Location].KeyField) == 0)
	  						    Found = true;
      					   }

   								return Found;
   				}



void BTTableClass::AddItem(const ItemType & NewItem, long NewRight,NodeType & Node, int Location)
   									{
  										 int j;

  										 for (j = Node.Count; j > Location; j--)
      										     {
     											 Node.Key[j] = Node.Key[j - 1];
     											 Node.Branch[j + 1] = Node.Branch[j];
    										     }

   										 Node.Key[Location] = NewItem;
  										 Node.Branch[Location + 1] = NewRight;
   										 Node.Count++;
   									}



void BTTableClass::Split(const ItemType & CurrentItem, long CurrentRight,long CurrentRoot, int Location, ItemType & NewItem, long & NewRight)
   					{
  						int j, Median;
 						NodeType RightNode;
										
  						cout << "<--- Splitting Node at this point"<<endl;
	
     


   						if (Location < MinKeys)
      						    Median = MinKeys;
  						else
     						    Median = MinKeys + 1;

  						    DataFile.seekg(CurrentRoot * NodeSize, ios::beg);
  						    DataFile.read(reinterpret_cast <char *> (&CurrentNode), NodeSize);
 


 						    for (j = Median; j < MaxKeys; j++)
     							{ 
    							  RightNode.Key[j - Median] = CurrentNode.Key[j];
    							  RightNode.Branch[j - Median + 1] = CurrentNode.Branch[j + 1];
     							}

  							  RightNode.Count = MaxKeys - Median;
  							  CurrentNode.Count = Median;  

   
  							  if (Location < MinKeys)
     							      AddItem(CurrentItem, CurrentRight, CurrentNode, Location + 1);
  							  else
   							      AddItem(CurrentItem, CurrentRight, RightNode,Location - Median + 1);

  							      NewItem = CurrentNode.Key[CurrentNode.Count - 1];
 							      RightNode.Branch[0] = CurrentNode.Branch[CurrentNode.Count];
  							      CurrentNode.Count--;

  							      DataFile.seekp(CurrentRoot * NodeSize, ios::beg);
 							      DataFile.write(reinterpret_cast <char *> (&CurrentNode), NodeSize);
 
     							      NumNodes++;
  							      NewRight = NumNodes;
  							      DataFile.seekp(NewRight * NodeSize, ios::beg);
  							      DataFile.write(reinterpret_cast <char *> (&RightNode), NodeSize);
 
   
   				          }



void BTTableClass::PushDown(const ItemType & CurrentItem, long CurrentRoot,bool & MoveUp, ItemType & NewItem, long & NewRight)
   				  {
  					 int Location;
  
						if (CurrentRoot == NilPtr)   
     						   {  
     							MoveUp = true;
    							NewItem = CurrentItem;
      							NewRight = NilPtr;
      						   }
  						else   
      						   {
    							 DataFile.seekg(CurrentRoot * NodeSize, ios::beg);
     							 DataFile.read(reinterpret_cast <char *> (&CurrentNode), NodeSize);
      
  							 if (SearchNode(CurrentItem.KeyField, Location))
  								 cout<<"Duplicates not allowed..will not insert: "<<CurrentItem.KeyField<<endl;
	

								 PushDown(CurrentItem, CurrentNode.Branch[Location + 1], MoveUp,NewItem, NewRight);
									 if (MoveUp)
								  	     {
										 DataFile.seekg(CurrentRoot * NodeSize, ios::beg);
										 DataFile.read(reinterpret_cast <char *> (&CurrentNode), NodeSize);
     
										 if (CurrentNode.Count < MaxKeys)
           									    {
          										MoveUp = false;
          										AddItem(NewItem, NewRight, CurrentNode, Location + 1);
           										DataFile.seekp(CurrentRoot * NodeSize, ios::beg);
          										DataFile.write(reinterpret_cast <char *> (&CurrentNode),NodeSize);
               
       									    	    }
        									else
          									   {
          										MoveUp = true;
         										Split(NewItem, NewRight, CurrentRoot, Location,
              										NewItem, NewRight);
           									   }
        								     }
     					           }
   		                    }					



bool BTTableClass::Insert(const ItemType & Item)
  		         {
 			  bool MoveUp;
  			  long NewRight;
  			  ItemType NewItem;
    			  PushDown(Item, Root, MoveUp, NewItem, NewRight);

  				 if (MoveUp)   
    				    {
      					CurrentNode.Count = 1;
    					CurrentNode.Key[0] = NewItem;
     					CurrentNode.Branch[0] = Root;
    					CurrentNode.Branch[1] = NewRight;
      					NumNodes++;
      					Root = NumNodes;
     				        DataFile.seekp(NumNodes * NodeSize, ios::beg);
      					DataFile.write(reinterpret_cast <char *> (&CurrentNode), NodeSize);
     
      
     				    }
	
  					 NumItems++;   
   				return true;   
   			   }



bool BTTableClass::Retrieve(KeyFieldType SearchKey, ItemType & Item)
   		  {
  			 long CurrentRoot;
 			 int Location;
   			 bool Found;

  			 Found = false;
   			 CurrentRoot = Root;

   			  while ((CurrentRoot != NilPtr) && (! Found))
      				{
      					DataFile.seekg(CurrentRoot * NodeSize, ios::beg);
     					DataFile.read(reinterpret_cast <char *> (&CurrentNode), NodeSize);
         

    					  if (SearchNode(SearchKey, Location))
         				     {
         					Found = true;
						Item = CurrentNode.Key[Location];
         				     }
     					 else
        				        CurrentRoot = CurrentNode.Branch[Location + 1];
     			       }

   					return Found;
  		  }




const int LineMax = KeyFieldMax + DataFieldMaxplus;


typedef char StringType[LineMax];



int MyGetLine(istream & InStream, char * String, int StringMax)
  	     {
  		 char Ch;
  		 int Count, Last;

  		 Count = 0;
  		 Last = StringMax - 1;
  		 Ch = InStream.get();

  		 while ((Ch != '\n') && (! InStream.fail()))
     		       {
      				if (Count < Last)
         			String[Count++] = Ch;
      				Ch = InStream.get();
      		       }

  		 String[Count] = NULL;
 					  return Count;
  	      }



void ReadLine(fstream & InputFile, KeyFieldType Word,DataFieldType Definition)
   	     {
   			char Line[LineMax];
  			int k, ch;

  			MyGetLine(InputFile, Line, LineMax);   

   			for (k = 0; k < KeyFieldMax; k++)
      				Word[k] = Line[k];
   				Word[KeyFieldMax] = NULL;

   			for (k = 0; k < DataFieldMax; k++)
      			    {
      				ch = Line[KeyFieldMax + k];
      					if (ch == '\n')
         					break;
     				Definition[k] = ch;
     			    }
  			 Definition[k] = NULL;
  	     }



void Load(fstream & InputFile, BTTableClass & Table)
   	 {
   		ItemType Item;
  		int Count;

  		Count = 0;
   		ReadLine(InputFile, Item.KeyField, Item.DataField);

   			while (! InputFile.fail())
      			      {
      
       				  Count++;
       				  cout << endl << "inserting: " << Item.KeyField << " ";
				  Table.Insert(Item);
       				  ReadLine(InputFile, Item.KeyField, Item.DataField);
	
     			      }
	
         }



int main()
   	{
  		 fstream Source;
		 ifstream DataFile("btree.txt");
   		 char data;
		 int counter = 0;
		 char array[100];
		
		 while(DataFile >> data)
		      {
			array[counter] = data;
			counter++;					
		      }
		 array[counter];
		 
   		 BTTableClass BTTable('w', "btree.dat");
   
   		 Source.open("btree.txt", ios::in);
   			if (Source.fail())
     			   {
      				 exit(1);
     			   }
	
  		 Load(Source, BTTable);
 		 Source.close();
		
		 

		 ItemType Item;
		 KeyFieldType SearchKey;
		  KeyFieldType dat;	 
		 
		 sort(array,array+counter);
		 int i=0;
		 memset(SearchKey,0,4);
		 cout<<"Traversing Ascending Order"<<endl;
		 while(i<counter)
		      {
			
			
			memcpy(SearchKey,&array[i],1);
					
			if (BTTable.Retrieve(SearchKey, Item))
         			cout << " Item "<<SearchKey<<" Found  " << endl;
			else
         			cout << " Item "<<SearchKey<<" Not Found  " << endl;
					
			i++;
		      }
		


  			 return 0;
        }

[wmsigler]

You can do prefix/infix/postfix tree traversal really easily using recursion.

Basically it goes along the lines of passing the root node to the function. The function itself goes something like this (for infix):
IF left child exists THEN PASS left child to the function
PRINT value of current node
IF right child exists THEN PASS right child to the function

All the nodes will be passed to the function, and because of the way the recursion works, it will print out the node values in the order you want (move PRINT first for prefix, PRINT to middle for infix, PRINT to end for postfix).

This should work as long as your tree structure is made correctly.