# 二元樹插入&樹的遍歷

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

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

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


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


void insert(NodePointer root, int key) 
{ 
  if(root->data==key)
  	return ;
  /*情況2.如果這個值小於樹根*/
  if(key<root->data){
    /*同時左節點為空*/
    if(root->left==NULL){
      /*插入節點*/
      root->left=new Node(key);
      return ;
    }else{
      insert(root->left, key);
    }
  }
  /*情況3.如果這個值大於樹根*/
  if(key>root->data){
    /*同時左節點為空*/
    if(root->right==NULL){
      /*插入節點*/
      root->right=new Node(key);
      return ;
    }else{
      insert(root->right, key);
    }
  }
} 
void printPostorder(struct Node* node) 
{ 
    if (node == NULL) 
        return; 
    printPostorder(node->left); 
    printPostorder(node->right); 
    cout << node->data << " "; 
} 

void printInorder(struct Node* node) 
{ 
    if (node == NULL) 
    	return;
    printInorder(node->left); 
    cout << node->data << " "; 
    printInorder(node->right); 
} 
  
void printPreorder(struct Node* node) 
{ 
    if (node == NULL) 
        return; 
    cout << node->data << " "; 
    printPreorder(node->left);  
    printPreorder(node->right); 
}  

void del(struct Node* node)
{
	del(node->left);
	del(node->right);
	free(node);
}

int main() 
{ 
	int array[] = {4, 3, 7, 1, 2, 9, 8, 5};
	NodePointer root=NULL;
	/*
	//第4題 
	for(int i=0;i<sizeof(array)/4;i++)
		Insert(root, array[i]);
	*/
	
	//第3題
	//General case  insert(root->left,key)\insert(root->right, key)
	root=new Node(34); 
	Insert(root,82)
	Insert(root,77);
	Insert(root,40);
	Insert(root,10);
	Insert(root,19);
	Insert(root,92);
	Insert(root,83);
	
	/*前序*/
	//printPreorder(root);
	/*中序*/
	//printInorder(root);
	/*後序*/
	//printPostorder(root); 
	del(root);
	
	return 0; 
}