binary tree sorting.

[avansc]

i dont know if anyone would want/need this. its by no means the best solution. but it works and is more academical than anything else.
please feel free to ask any questions may the arise.

ps: just a little node. NO this does not do any fancy checking for alphabetic order. it does not check for caps. so just use all lower or all uppercase. if you are really interested you can twiddle with it. but like i said, its more academical.

edit: i also just want to add that there is no advanced techniques like tree balancing to make the tree more efficient. but there are things like that, so feel free to study up on them.

main.cpp

Code: Select all

#include <stdio.h>
#include <stdlib.h>

#include "node.h"
#include "tree.h"

int main()
{
    printf("Start of program.\n");

    tree *sort = new tree();

    sort->addNode("zach");
    sort->addNode("stephanie");
    sort->addNode("andre");
    sort->addNode("bob");
    sort->addNode("dannie");
    sort->addNode("kurk");

    sort->printList(sort->head);

    return 0;
}

node.h

Code: Select all

#ifndef NODE_H_INCLUDED
#define NODE_H_INCLUDED

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct node
{
    char *name;
    node *left;
    node *right;
};

node *newNode(char *name);

#endif // NODE_H_INCLUDED

node.cpp

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "node.h"

node *newNode(char *name)
{
    node *temp = (node*)malloc(sizeof(node));
    temp->name = (char*)malloc(sizeof(char)*strlen(name));
    for(int a = 0;a < strlen(name);a++)
    {
        temp->name[a] = name[a];
    }

    temp->name[strlen(name)] = '\0';
    temp->left = NULL;
    temp->right = NULL;

    return temp;
}

tree.h

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "node.h"

#ifndef TREE_H_INCLUDED
#define TREE_H_INCLUDED

class tree
{
public:
    tree();
    void addNode(char *name);
    bool sort(char *a, char *b); // returns true if a comes before b
    void printList(const node * const temp);
//private:
    node *head;
};

#endif // TREE_H_INCLUDED

tree.cpp

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "node.h"
#include "tree.h"

tree::tree()
{
    this->head = NULL;
}

void tree::addNode(char *name)
{
    if(!this->head)
    {
        this->head = newNode(name);
        return;
    }

    node *temp = (node*)malloc(sizeof(node));
    temp = this->head;

    while(temp)
    {
        if(this->sort(name, temp->name))
        {
            if(temp->left)
            {
                temp = temp->left;
            }else{
                temp->left = newNode(name);
                return;
            }

        }else{
            if(temp->right)
            {
                temp = temp->right;
            }else{
                temp->right = newNode(name);
                return;
            }
        }
    }
}

bool tree::sort(char *a, char *b)
{
    int p = 0;
    while(p < strlen(a) || p < strlen(b))
    {
        if(a[p] > b[p])
        {
            return false;
        }
        if(a[p] < b[p])
        {
            return true;
        }
        p++;
    }
    return false;
}

void tree::printList(const node * const temp)
{
    if(!temp) return;
    this->printList(temp->left);
    printf("name : %s\n", temp->name);
    this->printList(temp->right);
}

[PixelP]

cool stuff! that might come in handy.
thanks for sharing your knowledge.