Hi all,

My program is supposed to read data from an input file and position the read data into an AVL tree - in alphabetical order. My output at the end is supposed to show each node in this format...

i.e. (Current, Current->LeftChild (could be NULL), Current->RightChild (could be NULL), Balance (-1, 0, or 1))

Each line represents each node in my AVL tree, the first group of output (when compiled and ran) is the tree listed in Inorder method, the second group is the tree in Preorder method. I tested this program before adding rebalancing features - and was able to get correct output (as though the tree was just an unbalanced tree).

When I added rebalancing functions - LeftLeft(), RightLeft(), etc. and other code to balance the tree that's when things fell apart. I suspect something is wrong in either my rebalancing functions, or my PreorderScan().

If anyone can offer aide I would greatly appreciate it! The first block of code is my .txt file input data - each line representing one node in the AVL tree. The next is obviously my program so far. Thank you!

BTW, I'm aware it would seem my balance variables are set to be backwards - this is so because my professor wants it that way!

Kay
Jon
Tim
Tom
Amy
Ann
Eva
Guy
Jan

Program.....

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

using namespace std;

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

AVLNode* AVLCreation(ifstream &);
void InorderTraversal(AVLNode *);
void PreorderTraversal(AVLNode *);
void PreorderScan(AVLNode *, AVLNode *);
void LeftLeft(AVLNode *, AVLNode *);
void RightRight(AVLNode *, AVLNode *);
void LeftRight(AVLNode *, AVLNode *, AVLNode *);
void RightLeft(AVLNode *, AVLNode *, AVLNode *);

int main()
{
    ifstream CheckFile; //ifstream checks for file existence
    CheckFile.open("a6.txt"); //attempts to open read file, and tests for existence
    if(CheckFile.is_open())
        cout << "Input file 'a6' exists." << endl << endl;
    else
        cout << "Input file 'a6' does not exist." << endl << endl;
    
    AVLNode *head;
    head = AVLCreation(CheckFile);
    InorderTraversal(head);
    cout << endl << endl;
    PreorderTraversal(head);
    
    system("PAUSE");
    return EXIT_SUCCESS;
}

AVLNode *AVLCreation(ifstream &InFile)
{
    AVLNode *Root = NULL;
    AVLNode *Leaf, *temp, *Scan;
    while(!InFile.eof())
    {
        temp = Root;
        Leaf = new AVLNode;
        getline(InFile, Leaf->Name);
        Leaf->Balance = 0;
        Leaf->RightChild = NULL;
        Leaf->LeftChild = NULL;
        if(Root == NULL)
        {
            Root = Leaf;
            Scan = Root;
        }
        else
        {
            while(1)
            {
                if((Leaf->Name > temp->Name) && (temp->RightChild == NULL))
                {
                    temp->RightChild = Leaf;
                    temp->Balance--;
                    break;
                }
                if((Leaf->Name < temp->Name) && (temp->LeftChild == NULL))
                {
                    temp->LeftChild = Leaf;
                    temp->Balance++;
                    break;
                }
                if((Leaf->Name > temp->Name) && (temp->RightChild != NULL))
                {
                    temp->Balance--;
                    temp = temp->RightChild;
                }
                else if((Leaf->Name < temp->Name) && (temp->LeftChild != NULL))
                {
                    temp->Balance++;
                    temp = temp->LeftChild;
                }
            }
            PreorderScan(Root, Scan);
        }
    }
    return Root;
}

void PreorderScan(AVLNode *Root, AVLNode *Scan)
{
    AVLNode *temp1, *temp2;
    if(Scan != NULL)
    {
        if(Scan->Balance >= 2)
        {
            temp1 = Scan->LeftChild;
            if(temp1->Balance == 1)
                LeftLeft(Scan, temp1);
            else if(temp1->Balance == -1)
            {
                temp2 = temp1->RightChild;
                LeftRight(Scan, temp1, temp2);
            }
        }
        else if(Scan->Balance <= -2)
        {
            temp1 = Scan->RightChild;
            if(temp1->Balance == -1)
                RightRight(Scan, temp1);
            else if(temp1->Balance == 1)
            {
                temp2 = temp1->LeftChild;
                RightLeft(Scan, temp1, temp2);
            }
        }
        PreorderScan(Root, Scan->LeftChild);
        PreorderScan(Root, Scan->RightChild);
    }
    return;
}

void LeftLeft(AVLNode *Rotate, AVLNode *Pivot)
{
    Rotate->LeftChild = Pivot->RightChild;
    Pivot->RightChild = Rotate;
    Pivot->Balance = 0;
    Rotate->Balance = 0;
    return;
}
    
void RightRight(AVLNode *Rotate, AVLNode *Pivot)
{
    Rotate->RightChild = Pivot->LeftChild;
    Pivot->LeftChild = Rotate;
    Pivot->Balance = 0;
    Rotate->Balance = 0;
    return;
}

void LeftRight(AVLNode *RotateTop, AVLNode *Rotate, AVLNode *Pivot)
{
    Rotate->RightChild = Pivot->LeftChild;
    Pivot->LeftChild = Rotate;
    RotateTop->LeftChild = Pivot;
    RotateTop->LeftChild = Pivot->RightChild;
    Pivot->RightChild = RotateTop;
    Pivot->Balance = 0;
    Rotate->Balance = 0;
    RotateTop->Balance = 0;
    return;
}

void RightLeft(AVLNode *RotateTop, AVLNode *Rotate, AVLNode *Pivot)
{
    Rotate->LeftChild = Pivot->RightChild;
    Pivot->RightChild = Rotate;
    RotateTop->RightChild = Pivot;
    RotateTop->RightChild = Pivot->LeftChild;
    Pivot->LeftChild = RotateTop;
    Pivot->Balance = 0;
    Rotate->Balance = 0;
    RotateTop->Balance = 0;
    return;
}

void InorderTraversal(AVLNode *Root)
{
    AVLNode *temp;
    if(Root != NULL)
    {
        InorderTraversal(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 << ", ";
        }
        cout << Root->Balance << ")" << endl;
        InorderTraversal(Root->RightChild); // print right subtree
    }
    return;
}

void PreorderTraversal(AVLNode *Root)
{
    AVLNode *temp;
    if(Root != NULL)
    {
        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 << ", ";
        }
        cout << Root->Balance << ")" << endl;
        PreorderTraversal(Root->LeftChild);  // print left subtree
        PreorderTraversal(Root->RightChild); // print right subtree
    }
    return;
}

Ok I'm sorry if I'm a noobish poster, or if I'm a noobish programmer based on the software I wrote, either of those two......

Could someone please help??

Ok I get it, I'm a n00bish programmer. Can someone point me in the right direction of writing proper code for this project?

Pretty pretty please???

Here's a parital fix. I fixed a couple of problems (noted in comments), and a couple of stylistic things in your first two functions. I didn't even look at the other functions, but it works better. It seems to still be missing one name.

int main()
{
    ifstream fin ("a6.txt");
    if (!fin) {
        cout << "Input file does not exist.\n\n";
        return -1;
    }

    AVLNode* head = AVLCreation (fin);
    fin.close();

    InorderTraversal (head);
    cout << "\n\n";

    PreorderTraversal (head);

    cin.sync(); cin.get(); // Will work on more systems.
}

AVLNode *AVLCreation(ifstream &InFile)
{
    AVLNode *Root = NULL;
    AVLNode *Leaf, *temp, *Scan;

/*** Moved getline into the while condition since it is
     a getline attempt that will inform you of the EOF.
     You should add a check for blank names (or all spaces). */
    string name;
    while (getline (InFile, name))
    {
        temp = Root;
        Leaf = new AVLNode;
        Leaf->Name = name;
        Leaf->Balance = 0;
        Leaf->RightChild = NULL;
        Leaf->LeftChild = NULL;

        if (!Root)
        {
            Root = Leaf;
            Scan = Root;
        }
        else
        {
            while (1)
            {
                if (Leaf->Name > temp->Name && !temp->RightChild)
                {
                    temp->RightChild = Leaf;
                    temp->Balance--;
                    break;
                }
                else if (Leaf->Name < temp->Name && !temp->LeftChild)
                {
                    temp->LeftChild = Leaf;
                    temp->Balance++;
                    break;
                }

                if (Leaf->Name > temp->Name && temp->RightChild)
                {
/*** Switched the order of the next two lines */
                    temp = temp->RightChild;
                    temp->Balance--;
                }
                else if(Leaf->Name < temp->Name && temp->LeftChild)
                {
/*** Ditto. */
                    temp = temp->LeftChild;
                    temp->Balance++;
                }
            }
            PreorderScan(Root, Scan);
        }
    }
    return Root;
}

Thank you for your input nucleon.

Since a lot of time elapsed before anyone replied I had already tore apart my initial design and started building another one. The new code I have will be posted hopefully by this evening (my code is at home, and I'm at work).

The new code has one very elusive bug in it that I just cannot find, but it is overall much, much better than what I posted originally. 'Just reposting for now in case you're interested. 'Like I said, I'll repost the new code later this evening.

I appreciate the aid very much and thanks again nucleon.

I saw that no one had responded. The reason I had not responded was because I was "sick of trees". That can happen, you know. Maybe everyone else was sick of trees too. And it was a fair amount of code. And it was the weekend.

I'll take a look at the new stuff when you post it.

Here is the new design I made, that almost works. The positioning of each node is correct, after comparing with my own hand-drawn model.

The balance integer I'm using to hold balances in each node appears slightly bugged. In some of the nodes the balance is correct, however in others it is not, it's obvious when noticing a balance greater than abs(1 or -1).

I'll probly be able to find this bug soon but I'm posting here anyways. I'm also posting my .exe results after compiling the program. Also the polarity of the balances is 'proper' now, meaning a greater weight on the LeftChild of a node yields a negative integer, and vice versa for the RightChild.

The code will compile and run if copied from here.

#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 InorderTraversal(AVLNode *);
void PreorderTraversal(AVLNode *);
AVLNode *LeftLeft(AVLNode *);
AVLNode *RightRight(AVLNode *);
AVLNode *LeftRight(AVLNode *);
AVLNode *RightLeft(AVLNode *);

int main()
{
    ifstream CheckFile; //ifstream checks for file existence
    CheckFile.open("a6.txt"); //attempts to open read file, and tests for existence
    if(CheckFile.is_open())
        cout << "Input file 'a6' exists." << endl << endl;
    else
        cout << "Input file 'a6' does not exist." << endl << endl;

    AVLNode *head;
    head = InputData(CheckFile);
    InorderTraversal(head);
    cout << endl;
    PreorderTraversal(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)
        {
            AVLNode *temp;
            temp = Root->LeftChild;
            if(Leaf->Name < temp->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)
        {
            AVLNode *temp;
            temp = Root->RightChild;
            if(Leaf->Name > temp->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 InorderTraversal(AVLNode *Root)
{
    AVLNode *temp;
    if(Root != NULL)
    {
        InorderTraversal(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 << ", ";
        }
        cout << Root->Balance << ")" << endl;
        InorderTraversal(Root->RightChild); // print right subtree
    }
    return;
}

void PreorderTraversal(AVLNode *Root)
{
    AVLNode *temp;
    if(Root != NULL)
    {
        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 << ", ";
        }
        cout << Root->Balance << ")" << endl;
        PreorderTraversal(Root->LeftChild);  // print left subtree
        PreorderTraversal(Root->RightChild); // print right subtree
    }
    return;
}
Attachments c++.jpg 36.11 KB

LOL never mind. The bug has been found and squashed, I'm posting the completed code now. I was just missing a critical calculation in my output functions (InorderTraversal() and PreorderTraversal()). And am also marking this thread as solved.

I don't mean to ignore the tips you included nucleon, but this program is due tomorrow, and I'm a college student.

Thanks again!

#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 InorderTraversal(AVLNode *);
void PreorderTraversal(AVLNode *);
AVLNode *LeftLeft(AVLNode *);
AVLNode *RightRight(AVLNode *);
AVLNode *LeftRight(AVLNode *);
AVLNode *RightLeft(AVLNode *);

int main()
{
    ifstream CheckFile; //ifstream checks for file existence
    CheckFile.open("a6.txt"); //attempts to open read file, and tests for existence
    if(CheckFile.is_open())
        cout << "Input file 'a6' exists." << endl << endl;
    else
        cout << "Input file 'a6' does not exist." << endl << endl;

    AVLNode *head = InputData(CheckFile);
    cout << "Inorder:\n\n";
    InorderTraversal(head);
    cout << "\n\nPreorder:\n\n";
    PreorderTraversal(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 InorderTraversal(AVLNode *Root)
{
    AVLNode *temp;
    if(Root != NULL)
    {
        InorderTraversal(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;
        InorderTraversal(Root->RightChild); // print right subtree
    }
    return;
}

void PreorderTraversal(AVLNode *Root)
{
    AVLNode *temp;
    if(Root != NULL)
    {
        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;
        PreorderTraversal(Root->LeftChild);  // print left subtree
        PreorderTraversal(Root->RightChild); // print right subtree
    }
    return;
}

You should still make these changes, it could save you marks!

In main, no need to say the file exists, and it should exit the program if the file does not exist (after reporting so).

In InputData(), do the following. Otherwise it adds a final blank entry into your tree (unless there's no newline on the last line, which is not something to be counted on). This will also skip blank lines without adding a blank entry to the tree.

string name;
    while(getline(InFile, name))
    {
        // Skip if no non-blanks.
        if (name.find_first_not_of(" \t") == string::npos)
            continue;

        Leaf = new AVLNode;
        Leaf->Name = name;
This question has already been answered. Start a new discussion instead.