Preorder to Tree?

[AutoC]

Hi,
Lets assume my preorder traversal gives me a unique tree.How do I get the tree from the preorder traversal?

Any help is appreciated

[Narue]

What do you mean by "get" the tree?

[AutoC]

draw the binary tree?..get its structure so that I can traverse it etc.?

[Alex Edwards]

It seems to me that you have a set of values returned to you from a traversal order and you would like to reconstruct the tree?

If you refer to this Tree-pedia link, you will see different methods of traversing trees and how they are mapped out with values =)

Also remember that Preorder starts with the root! I believe the algorithm for Pre-order traversal is to analyze the root, then move left then move right, though I could be a bit off on the entire definition @_@

I never understand how people seem to print the Tree's to the console with absolute ease... especially Narue and RadicalEdward... but nonetheless they do it well!

Here's a less efficient example that I managed to cook up in 2.5 hours #_# --

#include <iostream>
#include <string>
#include <exception>
#include <vector>
#include <sstream>

using std::cout;
using std::cin;
using std::endl;
using std::ostream;
using std::string;
using std::exception;
using std::vector;
using std::stringbuf;

typedef class troolean{
    short num;
        short diminish(short arg)       {return  (( (arg < 0)
                                        ? (-1) : ((arg > 0)
                                        ? (1) : (0) ) ));}
    public:
        troolean(short arg = 0)         {assign(arg);}
        short assign(short arg)         {return num = diminish(arg);}
        short assign(short arg) const   {return arg;}
        short getValue()                {return num;}
        short getValue() const          {return const_cast<troolean&>(*this).getValue();}
        short operator=(short arg)      {return assign(arg);}
        short operator=(short arg) const{return assign(arg);}
        bool operator==(short arg)      {short val = diminish(arg); return num == val;}
        bool operator==(const troolean& enemy){
            return this->getValue() == enemy.getValue();
        }
        friend ostream& operator<<(ostream& out, const troolean& tr){
            return out << tr.getValue();
        }
} trool;

class Printable{
    public:
        virtual ostream& printInfo(ostream& out = cout) = 0;
};

class Comparable{
    public:
        virtual trool compareTo(void* target) = 0;
};

typedef class Custom_Object : public Printable, public Comparable{} C_O;

class Person : public Custom_Object{
    string name;

    public:
        class InvalidPersonException : public exception{
            virtual const char* what() const throw(){
                return "Error! Invalid Person!";
            }
        } ipe;
        Person(const char* arg){string temp = arg;name = temp;}
        Person(const string& arg) : name(arg) {}
        virtual trool compareTo(void* target){
            Person *p = NULL;
            if(p = static_cast<Person*>(target)){
                return name.compare(p->name);
            }else throw ipe;
        }
        virtual ostream& printInfo(ostream& out = cout){
            return out << name << "\n";
        }
};

template<class C_O>
class Tree{
    string status;
    class Node{
        public:
            Node* left;
            Node* right;
            C_O* type;
            Node(const C_O& arg) : left(0), right(0), type(const_cast<Person*>(&arg)) {}
            virtual ostream& printInfo(const string& arg, ostream& out = cout){
                string temp;
                stringbuf sb (temp);
                ostream o (&sb);
                out << arg;
                return (type != NULL) ? type->printInfo(out): o;
            }
    };
    Node* root;

    public:
        Tree() : root(0) {}

        bool insert(const C_O& value){
            bool wasInserted = false;
            if(root == NULL){
                root = new Node(value);
            }else{
                Node* temp = root;
                Node* previous = NULL;
                bool direction = false; // 0 for left, 1 for right
                while(temp != NULL){
                    previous = temp;
                    try{
                        if( (*temp->type).compareTo(const_cast<Person*>(&value)) == 0){
                            return false; // if a value is ever the same as one already enterred
                                          // get it out of here! O_O
                        }else if( (*temp->type).compareTo(const_cast<Person*>(&value)) == -1){
                            temp = temp->right;
                            direction = true;
                        }else{
                            temp = temp->left;
                            direction = false;
                        }
                    }catch(exception&){
                        // exit, or maybe not? =P
                    }
                }

                if(direction == true){
                    previous->right = new Node(value);
                }else{
                    previous->left = new Node(value);
                }
            }
            return true;
        }

        void printInfo(ostream& out = cout){
            printTree(root, status, out);
            status.clear();
        }

        void printTree(Node* n, string arg, ostream& out = cout){
            if(n != NULL){
                string temp = arg;

                arg += "\t";
                if(n->right != NULL){
                    printTree(n->right, arg, out);
                }else out << arg << "<null>\n";

                n->printInfo(temp, out);

                if(n->left != NULL){
                    printTree(n->left, arg, out);
                }else out << arg << "<null>\n";
            }
        }
};

int main(){
    Tree<Person> myTree;

    vector<Person> vec;
    vec.push_back("Mark"); vec.push_back("Brian"); vec.push_back("Eunice");
    vec.push_back("Zeus"); vec.push_back("Will");  vec.push_back("Xantos");

    for(vector<Person>::iterator i = vec.begin(); i != vec.end(); i++){
        myTree.insert(*i);
    }
    
    myTree.printInfo();

    cout << "\n\n\n\n\n";
    Person other = "Goerge";
    myTree.insert(other);
    myTree.printInfo();

    return 0;
}

--of course I goofed off to keep myself entertained but hopefully you'll see the highlights of the code (if you look at the values inserted into the vectors and the order they're in, then look at the tree you'll see why!) =)