#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
typedef struct node{
    int data;
    struct node* right;
    struct node* left;
}Node;

typedef struct{
    Node *root;
}Tree;

//二叉树的创建
void insert(Tree *tree,int value)
{
    Node *node=(Node *)malloc(sizeof(Node));
    node->data=value;
    node->left=NULL;
    node->right=NULL;
    
    if(tree->root==NULL)
        tree->root=node;
    else
    {
        Node *temp=tree->root;
        while(temp!=NULL)
        {
            if(value<temp->data)
            {
                if(temp->left==NULL)
                {
                    temp->left=node;
                    break;                    
                }
                else
                    temp=temp->left;
            }
            else
            {
                if(value>temp->data)
                {
                    if(temp->right==NULL)
                    {
                        temp->right=node;
                        break;                        
                    }
                    else
                        temp=temp->right;                    
                }
            }
        }
    }
}

//递归前序遍历法 
void Preorder(Node *node)
{
    if(node!=NULL)
    {
        printf("%d\t",node->data);
        Preorder(node->left);
        Preorder(node->right);
    }
}
//递归的中序遍历 
void Inorder(Node *node)
{
    if(node!=NULL)
    {
        Inorder(node->left);
        printf("%d\t",node->data);
        Inorder(node->right);
    }
}
//递归后序遍历法 
void Postorder(Node *node)
{
    if(node!=NULL)
    {
        Postorder(node->left);
        Postorder(node->right);
        printf("%d\t",node->data);
    }
}

//非递归前序遍历方法 
void PreorderNonrecurion(Node *node)
{
    if(node!=NULL)
    {
        Node *stack[MAXSIZE];
        int top=-1;
        Node *p=NULL;
        stack[++top]=node;
        while(top!=-1)
        {
            p=stack[top--];
            printf("%d\t",p->data);
            if(p->right!=NULL)
                stack[++top]=p->right;
            if(p->left!=NULL)
                stack[++top]=p->left;
        }        
    }
}

//非递归中序遍历方法 
void InorderNonrecurion(Node *node)
{
    if(node!=NULL)
    {
        Node *stack[MAXSIZE];int top=-1;
        Node *p=node;
        while(top!=-1||p!=NULL)
        {
            while(p!=NULL)
            {
                stack[++top]=p;
                p=p->left;
            }
            if(top!=-1)
            {
                p=stack[top--];
                printf("%d\t",p->data);
                p=p->right;
            }
        }
    }
} 

//非递归后序遍历法
void PostorderNonrecurion(Node *node)
{
    if(node!=NULL)
    {
        Node *stack1[MAXSIZE];int top1=-1;
        Node *stack2[MAXSIZE];int top2=-1;
        stack1[++top1]=node;
        Node *p=NULL;
        
        while(top1!=-1)
        {
            p=stack1[top1--];
            stack2[++top2]=p;
            if(p->left!=NULL)
                stack1[++top1]=p->left;
            if(p->right!=NULL)
                stack1[++top1]=p->right;
        }
        
        Node *q=NULL;
        while(top2!=-1)
        {
            q=stack2[top2--];
            printf("%d\t",q->data);
        }        
    }
} 

//层次遍历
void Levelorder(Node *node)
{
    if(node!=NULL)
    {
        Node *que[MAXSIZE];int front=0,rear=0;
        Node *p=NULL;
        
        rear=(rear+1)%MAXSIZE;
        que[rear]=node;
        while(front!=rear)
        {
            front=(front+1)%MAXSIZE;
            p=que[front];
            printf("%d\t",p->data);
            if(p->left!=NULL)
            {
                rear=(rear+1)%MAXSIZE;
                que[rear]=p->left;
            }
            if(p->right!=NULL)
            {
                rear=(rear+1)%MAXSIZE;
                que[rear]=p->right;
            }
        }
    }
} 
int main(){
    int arr[7]={6,3,4,2,5,1,7};
    Tree tree;
    tree.root=NULL;
    for(int i=0;i<7;i++)
        insert(&tree,arr[i]);
        
    printf("递归前序遍历结果为\t"); 
    Preorder(tree.root);
    printf("\n\n");
    
    printf("递归中序遍历结果为\t"); 
    Inorder(tree.root);
    printf("\n\n");    
    
    printf("递归后序遍历结果为\t"); 
    Postorder(tree.root);
    printf("\n\n");
        
    printf("非递归前序遍历结果为\t"); 
    PreorderNonrecurion(tree.root);
    printf("\n\n");

    printf("非递归中序遍历结果为\t"); 
    InorderNonrecurion(tree.root);
    printf("\n\n");
    
    printf("非递归后序遍历结果为\t"); 
    PostorderNonrecurion(tree.root);
    printf("\n\n");    
    
    printf("层次遍历结果为\t\t"); 
    Levelorder(tree.root);
    printf("\n\n");    
}