#include <stdio.h>
#include <stdlib.h>
#define MAX 50

//二叉树链表存储结构
typedef struct btnode
{
    int data;        //结点数据内容
    struct btnode *Llink;   //左子树指针
    struct btnode *Rlink;   //右子树指针
}btnode, *btreetype;

/****---------------------------------------------****/
//函数名:  OutputTree(btreetype &root)
//参数:    (传入)btreetype &root 二叉树指针
//功能:    输出二叉树
/****---------------------------------------------****/
void OutputTree(btreetype &root)
{
    btreetype p;
    //打印左子树
    p = root->Llink;
    printf("建立的二叉树的左子树:");
    while(p != NULL)
    {
        printf("%d ",p->data);
        p = p->Llink;
    }
    //打印右子树
    p = root->Rlink;
    printf("\n建立的二叉树的右子树为:");
    while(p != NULL)
    {
        printf("%d ", p->data);
        p = p->Rlink;
    }
}

/****--------------------------------------------****/
//函数名: PreOrder(btreetype &root)
//参数:   (传入)btreetype &root二叉树指针
//功能:   先序遍历二叉树
/****--------------------------------------------****/
void PreOrder(btreetype &root)
{
    btreetype p;
    p = root;
    if(p != NULL)
    {
        printf("%d ",p->data);
        PreOrder(p->Llink);    //递归处理左子树
        PreOrder(p->Rlink);    //递归处理右子树
    }
}

/****--------------------------------------------****/
//函数名: InOrder(btreetype &root)
//参数:   (传入)btreetype &root二叉树指针
//功能:   中序遍历二叉树(递归方式)
/****--------------------------------------------****/
void InOrder(btreetype &root)
{
    btreetype p;
    p = root;
    if(p != NULL)
    {
        InOrder(p->Llink);   //递归处理左子树
        printf("%d ", p->data);
        InOrder(p->Rlink);   //递归处理右子树
    }
}

/****-------------------------------------------****/
//函数名: InOrder(btreetype &root)
//参数:   (传入)btreetype &root二叉树指针
//功能:   中序遍历二叉树(非递归方式)
/****--------------------------------------------****/
void InOrder_Norecursion(btreetype &root)
{
    btreetype stack[MAX];
    btreetype p;
    int top = 0;
    p = root;
    do
    {
        while(p != NULL)  //扫描左结点
        {
            top++;
            stack[top] = p;
            p = p->Llink;
        }
        if(top > 0)
        {
            p = stack[top];   //p所指结点为无左子树或其左子树已遍历过
            top--;
            printf("%d ", p->data);
            p = p->Rlink;  //扫描右结点
        }
    }while(p != NULL || top != 0);
}

/****--------------------------------------------****/
//函数名:  PostOrder(btreetype &root)
//参数:    (传入)btreetype &root 二叉树指针
//功能:    后序遍历二叉树
/****--------------------------------------------****/
void PostOrder(btreetype &root)
{
    btreetype p;
    p = root;
    if(p != NULL)
    {
        PreOrder(p->Llink);   //递归处理左子树
        PreOrder(p->Rlink);   //递归处理右子树
        printf("%d ", p->data);
    }
}

/****--------------------------------------------****/
//函数名: CreateTree(int n)
//参数:   (传入)int n数据数量
//返回值: 返回二叉树(根结点)指针
//功能:   建立二叉树
/****--------------------------------------------****/
btreetype CreateTree(int n)
{
    int i;
    btreetype root = NULL;
    for(i = 0; i < n; i++)
    {
        btreetype newNode;
        btreetype currentNode;
        btreetype parentNode;

        //建立新结点
        newNode = (btreetype)malloc(sizeof(btnode));
        scanf("%d", &newNode->data); /*新结点赋值*/
        newNode->Llink = NULL;
        newNode->Rlink = NULL;

        currentNode = root;  //存储当前结点指针
        if(currentNode == NULL) root = newNode;  //以新结点作为二叉树根结点
        else
        {
            while(currentNode != NULL)
            {
                parentNode = currentNode; //存储当前结点的父结点
                if(newNode->data < currentNode->data) //比较结点数值大小
                    currentNode = currentNode->Llink;  //左子树
                else
                    currentNode = currentNode->Rlink;  //右子树
            }
            //根据数值大小连接父结点和子结点
            if(newNode->data < parentNode->data)
                parentNode->Llink = newNode;
            else
                parentNode->Rlink = newNode;
        }//else
    }//for
    return root;
}
/****------------测试主程序------------------****/
int main()
{
    btreetype btree;
    int count;
    printf("input the number of elements:\n");
    scanf("%d", &count);
    printf("input data(num = %d):\n", count);
    btree = CreateTree(count);

    //二叉树的各种遍历
    printf("\n先序遍历建立的二叉树:");
    PreOrder(btree);
    printf("\n中序遍历建立的二叉树(递归方式):");
    InOrder(btree);
    printf("\n中序遍历建立的二叉树(非递归方式):");
    InOrder_Norecursion(btree);
    printf("\n后序遍历建立的二叉树:");
    PostOrder(btree);
    return 0;
}