avl tree implementation..

[arc45]

"write a program that reads a list of names and telephone numbers from a text file and inserts them into an AVL tree showing in order and pre order traversal..once the tree has been built,present the user with a menu that allows huim or her to search the list for a specified name,insert a new name,delete an exixting name or prInt the entire phone list.At the end of the job write the data in the list back to the file.Test your program with atleast 10 names."

this is a college project i've been working on..i have managed to work on the 1st half of the program ,where in a text file acts as an input to create an AVL tree.The code for this is attached.The problem is with building the menu for the user.I am really finding it very difficult to perform any update (delete,search etc) on the file content.(i know veryyyy little about file handling in c++ :( )
PLEASE if any one could help me with the rest of the code i'll be so thankful!!

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>

using namespace std;

struct AVLNode
{
    string Name;
    int Balance;
    AVLNode *LeftChild;
    AVLNode *RightChild;
};

AVLNode *InputData(ifstream &);
AVLNode *InsertData(AVLNode *, AVLNode *);
int FindBalance(AVLNode *);
void Traversal(AVLNode *);
AVLNode *LeftLeft(AVLNode *);
AVLNode *RightRight(AVLNode *);
AVLNode *LeftRight(AVLNode *);
AVLNode *RightLeft(AVLNode *);

int main()
{
    ifstream CheckFile; //ifstream checks for file existence
    char inputFileName[]="file.txt";
    CheckFile.open(inputFileName); //attempts to open read file, and tests for existence
    if(!CheckFile)
        cout << "Input file does not exist." << endl << endl;
    else
        cout <<"file opend"<<endl;
    AVLNode *head = InputData(CheckFile);
    cout << "taversal:\n\n";
   Traversal(head);
    //cout << endl;

    system("PAUSE");
    return EXIT_SUCCESS;
}

AVLNode *InputData(ifstream &InFile)
{
    AVLNode *Root = NULL;
    AVLNode *Leaf;
    while(!InFile.eof())
    {
        Leaf = new AVLNode;
        getline(InFile, Leaf->Name);
        Leaf->Balance = 0;
        Leaf->RightChild = Leaf->LeftChild = NULL;
        if(Root == NULL)
            Root = Leaf;
        Root = InsertData(Leaf, Root);
    }
    return Root;
}

AVLNode *InsertData(AVLNode *Leaf, AVLNode *Root)
{
    if(Root == NULL)
        return Leaf;
    else if(Leaf->Name < Root->Name)
    {
        Root->LeftChild = InsertData(Leaf, Root->LeftChild);
        if(FindBalance(Root->LeftChild) - FindBalance(Root->RightChild) == 2)
        {
            if(Leaf->Name < Root->LeftChild->Name)
                Root = LeftLeft(Root);
            else
                Root = LeftRight(Root);
        }
    }
    else if(Leaf->Name > Root->Name)
    {
        Root->RightChild = InsertData(Leaf, Root->RightChild);
        if(FindBalance(Root->RightChild) - FindBalance(Root->LeftChild) == 2)
        {
            if(Leaf->Name > Root->RightChild->Name)
                Root = RightRight(Root);
            else
                Root = RightLeft(Root);
        }
    }
    Root->Balance = max(FindBalance(Root->LeftChild), FindBalance(Root->RightChild)) + 1;
    return Root;
}

int FindBalance(AVLNode *Root)
{
    if(Root == NULL)
        return -1;
    else
        return Root->Balance;
}

AVLNode *LeftLeft(AVLNode *Rotate)
{
    AVLNode *Pivot = Rotate->LeftChild;
    Rotate->LeftChild = Pivot->RightChild;
    Pivot->RightChild = Rotate;
    Rotate->Balance = max(FindBalance(Rotate->LeftChild), FindBalance(Rotate->RightChild)) + 1;
    Pivot->Balance = max(FindBalance(Pivot->LeftChild), FindBalance(Rotate->RightChild)) + 1;
    return Pivot;
}

AVLNode *RightRight(AVLNode *Rotate)
{
    AVLNode *Pivot = Rotate->RightChild;
    Rotate->RightChild = Pivot->LeftChild;
    Pivot->LeftChild = Rotate;
    Rotate->Balance = max(FindBalance(Rotate->LeftChild), FindBalance(Rotate->RightChild)) + 1;
    Pivot->Balance = max(FindBalance(Pivot->RightChild), FindBalance(Rotate->LeftChild)) + 1;
    return Pivot;
}

AVLNode *LeftRight(AVLNode *RotateTop)
{
    RotateTop->LeftChild = RightRight(RotateTop->LeftChild);
    return LeftLeft(RotateTop);
}

AVLNode *RightLeft(AVLNode *RotateTop)
{
    RotateTop->RightChild = LeftLeft(RotateTop->RightChild);
    return RightRight(RotateTop);
}

void Traversal(AVLNode *Root)
{
    AVLNode *temp;
    if(Root != NULL)
    {
        Traversal(Root->LeftChild);  // print left subtree
        cout << "(" << Root->Name << ", "; // print this node
        if(Root->LeftChild == NULL)
            cout << "NULL, ";
        else
        {
            temp = Root->LeftChild;
            cout << temp->Name << ", ";
        }
        if(Root->RightChild == NULL)
            cout << "NULL, ";
        else
        {
            temp = Root->RightChild;
            cout << temp->Name << ", ";
        }
        int temp1 = (FindBalance(Root->RightChild) - FindBalance(Root->LeftChild));
        cout << temp1 << ")" << endl;
       Traversal(Root->RightChild); // print right subtree
    }
    return;
}

[mrnutty]

Your user interaction logic would look something like this :

string userInput;
const std::string DONE = "done";
do{
  cout << "Enter a command to call[ add, print, delete, done ] ";
  cin >> userInput;
  if( userInput == "add"){
    /* ask user what to add then add it to the tree */
   }
  else if( userInput == "print") { /* print tree */ }
  else if( userInput == "delete"){ /* ask what to delete, then try to delete it */ }
  else if( userInput == "done"){
     /* save the tree into a file, you can do so by saving each element in the tree into the file */
  }
}while(userInput != DONE );

[abhimanipal]

What part of file handling is confusing ?

There are 4 basic operations
1. Read --> Read the contents of a file . Use fread for this
2. Write --> Write to a file . Open the file is write mode and then use fwrite for this.
3. Append --> Append to end of file. Open the file in append mode and then use fwrite
4. seek --> When you use fopen to open a file the file pointer usually points to the start of the file. But if you want to update the contents of a file you have to move the file pointer away from the start. Use fseek for this

Try googling for these functions . You should find lots of sample code / tutorials

[shinnoon]

Do you find the answer?because i have the same project and i used this code but i couldn't add and delete and also search...

[Narue]

i couldn't add and delete and also search...

I suspect you didn't look very hard, or looked for something complete that you could use without any thinking. But if it's the deletion for AVL trees you're having trouble finding, that's understandable. Most resources leave it as an exercise for the reader even though it's the most complex operation. :icon_rolleyes:

Fortunately for you, I scratched that particular itch with my AVL tutorial. You're welcome.

[shinnoon]

Unfortunately i'm new in c++.I dont want a complete package to just run,thanks for the tutorial anyway