# 樹的應用

#include <stdlib.h>
#include <queue>
#include <stdio.h>
#include <iostream>
#include <cstring>
using namespace std;

typedef struct Student {
    int id;
    string name;
} Student;

Student arr[] = {
    { 4, "jack" },
    { 3, "jason" },
    { 7, "jason" },
    { 1, "alex" },
    { 2, "alice" },
    { 9, "hacker" },
    { 8, "cracker" },
    { 5, "jobs" }
};

struct Node {
    int id;
    string name;
    struct Node* left, *right;
    /*節點建構函式*/
    Node(int id, string name)
    {
        this->id = id;
        this->name = name;
        left = right = NULL;
    }
};

/*定義節點指標*/
typedef struct Node* NodePointer;


#define Insert(r,id,name){\
  if((r)==NULL){\
    (r)=new Node(id,name);\
  }else{\
    insert((r),(id),(name));\
  }\
}

#define Insert2(r,id,name){\
  if((r)==NULL){\
    (r)=new Node(id,name);\
  }else{\
    insert2((r),(id),(name));\
  }\
}
void insert(NodePointer root, int in, string na)
{
    if(root->id == in)
        return ;
    /*情況2.如果這個值小於樹根*/
    if(in < root->id) {
        /*同時左節點為空*/
        if(root->left == NULL) {
            /*插入節點*/
            root->left = new Node(in, na);
            return ;
        } else {
            insert(root->left, in, na);
        }
    }
    /*情況3.如果這個值大於樹根*/
    if(in > root->id) {
        /*同時左節點為空*/
        if(root->right == NULL) {
            /*插入節點*/
            root->right = new Node(in, na);
            return ;
        } else {
            insert(root->right, in, na);
        }
    }
}

void insert2(NodePointer root, int in, string na)
{
    int a;
    a = na.compare(root->name);
    if(a == 0)
        return ;
    /*情況2.如果這個值小於樹根*/
    if(a < 0) {
        /*同時左節點為空*/
        if(root->left == NULL) {
            /*插入節點*/
            root->left = new Node(in, na);
            return ;
        } else {
            insert(root->left, in, na);
        }
    }
    /*情況3.如果這個值大於樹根*/
    if(a > 0) {
        /*同時左節點為空*/
        if(root->right == NULL) {
            /*插入節點*/
            root->right = new Node(in, na);
            return ;
        } else {
            insert(root->right, in, na);
        }
    }
}
void printInorder(struct Node* node)
{
    if (node == NULL)
        return;
    printInorder(node->left);
    cout << node->id << " " << node->name << endl;
    printInorder(node->right);
}

int main()
{
    NodePointer root = NULL;
    NodePointer root2 = NULL;

    root = new Node(arr[0].id, arr[0].name);
    for(int i = 1; i < 8; i++)
        Insert(root, arr[i].id, arr[i].name);

    /*中序*/
    printInorder(root);
    cout << endl;

    root = new Node(arr[0].id, arr[0].name);
    for(int i = 1; i < 8; i++)
        Insert2(root, arr[i].id, arr[i].name);

    /*中序*/
    printInorder(root);
    return 0;
}