hw5.cpp

#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <cmath>

using namespace std;

typedef struct _node* pnode;
typedef struct _node{
    string *name;
    pnode left;
    pnode right;
} node;

void createNode(pnode *root, string top, string left, string right);
pnode findNode(pnode root, string name);
void printPreOrder(pnode root);
void printInOrder(pnode root);
void printPostOrder(pnode root);
int hight(pnode root);
int max(int , int);

int main(int argc, char* argv[])
{
    // detect arguments have filename ?
    if(argc != 2){
        cout << "usage:" << endl << "HW5 filename" << endl;
        return -1;
    }
    // define pointer of tree
    pnode BinaryTree = 0;
    // read file
    ifstream ifs;
    char buffer[256];
    string root , left , right;
    ifs.open(argv[1]);

    if(ifs.is_open()){
        // read lines
        while(ifs.getline(buffer, 255)){
            // clean string
            root = "";
            left = "";
            right = "";
            // read 3 propetity
            istringstream iss(buffer);
            iss >> root;
            iss >> left;
            iss >> right;
            createNode(&BinaryTree, root, left, right);
        }
    }else{
        cout << "file not found!" << endl;
    }

    cout << "Preorder: ";
    printPreOrder(BinaryTree);
    cout << endl;
    cout << "Inorder: ";
    printInOrder(BinaryTree);
    cout << endl;
    cout << "Postorder: ";
    printPostOrder(BinaryTree);
    cout << endl;

    int lh , rh;
    lh = hight(BinaryTree->left);
    rh = hight(BinaryTree->right);

    cout << "The balance factor is: " << " " << abs(lh-rh) << endl;


    return 0;
}

void createNode(pnode *root, string top, string left, string right){
    string *tmp1 , *tmp2;
    tmp1 = new string(left);
    tmp2 = new string(right);
    int lr;
    (*tmp1) = tmp1->substr(tmp1->find("n")+1);
    (*tmp2) = tmp2->substr(tmp2->find("n")+1);
    istringstream *iss;
    iss = new istringstream((*tmp1));
    (*iss) >> lr;
    if(lr != 0 && lr % 2 == 0){
        string tmp = left;
        left = right;
        right = tmp;
    }

    pnode nleft , nright;
    pnode ntop = 0;

    nleft = new node;
    nright = new node;

    nleft->left = 0;
    nleft->right = 0;
    nright->left = 0;
    nright->right = 0;

    nleft->name = new string(left);
    nright->name = new string(right);
    if(top == "r"){
        pnode r = new node;
        r->left = 0;
        r->right = 0;
        r->name = new string(top);
        (*root) = r;
        ntop = r;
    }else{
        ntop = findNode((*root), top);
        if(ntop == 0){
            cout << "Error: to find" << top << endl;
        }
    }

    if(left!= ""){
        ntop->left = nleft;
    }
    if(right!=""){
        ntop->right = nright;
    }

}

void printPreOrder(pnode root){
    if(root == 0) return ;
    cout << (*root->name) << " ";
    printPreOrder(root->left);
    printPreOrder(root->right);
}

void printInOrder(pnode root){
    if(root == 0) return ;
    printInOrder(root->left);
    cout << (*root->name) << " ";
    printInOrder(root->right);
}

void printPostOrder(pnode root){
    if(root == 0) return ;
    printPostOrder(root->left);
    printPostOrder(root->right);
    cout << (*root->name) << " ";
}

pnode findNode(pnode root, string name){
    if(root == 0 ) return 0 ;
    pnode find = 0;
    if((*root->name) == name){
        return root;
    }
    find = findNode(root->left, name);
    if(find != 0 ) return find;
    find = findNode(root->right, name);
    if(find != 0 ) return find;
    return 0;
}

int hight(pnode root){
    if(root == 0){
        return 1;
    }
    return max(hight(root->left) , hight(root->right))+1;
}

int max(int a, int b){
    if(a>b) return a;
    return b;
}