二叉树的排序

先序遍历
先序遍历比较容易理解，首先将根节点入栈。从栈中取出栈顶节点，打印该点，接着先将右孩子入栈，再将左孩子入栈（因为栈的特点是先进后出，要先遍历左孩子就得后入栈）。不断重复该步骤直至栈为空。

中序遍历
令cur等于head
步骤1：先把cur入栈，然后不停让cur=cur->left，重复此步骤。即把cur下的所有左孩子节点入栈。直到cur为空。
步骤2：从栈中弹出栈顶给cur，打印该节点，然后令cur=cur->right，回到步骤2。
步骤3：当栈为空时且cur为空时，过程结束。
入栈的顺序可参考下图：

后序遍历

方法一：

申请两个栈s1、s2，先将头节点入栈s1。从s1中弹出栈顶节点记为cur，然后依次将cur的左孩子和右孩子压入s1。在这过程中每一个从s1中弹出的节点均压入s2。当s1为空后，从s2中依次弹出的节点便是后序遍历的次序。
主要就是利用两个栈来进行“倒腾“，压入s2的顺序为中、右、左，弹出的顺序就变成了左、右、中。

方法二：
申请一个栈，将头节点压入栈。
现在我们思考一下：当遍历到一个节点时，如何判断这次遍历是打印该点，还是先处理它的孩子呢？
有以下几种情况：

该节点的左右孩子皆为空，即该节点为叶子节点，那么这次遍历就是打印该点。
如果上一次打印的节点为该节点的右孩子，说明该节点的子树处理完毕，这次遍历就是打印该点。
如果上一次打印的节点为该节点的左孩子，且该节点的右孩子为空，说明该节点的子树处理完毕，这次遍历就是打印该点。
否则说明子树没有被访问过，按照右孩子、左孩子的顺序入栈。

#include <stdio.h>
#include<stdlib.h>

//二叉树结点
typedef struct treeNode{
    int value;
    struct treeNode *left;
    struct treeNode *right;
}Node;

//栈结点
typedef struct stackNode{
    Node* value;
    struct stackNode *next;
}sNode;

//队列结点
typedef struct queueNode{
    Node *node;
    struct queueNode *next;
}qNode;

//队列类型定义
typedef struct linkQueue{
    qNode *front;
    qNode *rear;
}Queue;

//初始化队列
void initQueue(Queue **queue)
{
    *queue = (Queue *)malloc(sizeof(Queue));
    (*queue)->front = NULL;
    (*queue)->rear = (*queue)->front;
}

//判断队列是否为空
int isEmptyQ(Queue *queue)
{
    if(queue->front!=NULL)
        return 0;
    return 1;
}

//获取队列列首保存的元素
Node *getQueueFront(Queue* queue)
{
    if(isEmptyQ(queue))
    {
        return NULL;
    }
    return queue->front->node;
}

//出队操作
void dequeue(Queue *queue)
{
    if(isEmptyQ(queue))
    {
        return;
    }
    
    Node* node = queue->front->node;
    
    if (queue->front==queue->rear) {
        queue->front = NULL;
        queue->rear = queue->front;
    }
    else
    {
        queue->front = queue->front->next;
    }
    
    
    free(node);
}

//入队操作
void inQueue(Queue *queue,Node* node)
{
    qNode *newNode = (qNode *)malloc(sizeof(qNode));
    newNode -> node = node;
    newNode -> next = NULL;
    
    if(isEmptyQ(queue))
    {
        queue->front = newNode;
        queue->rear = queue->front;
    }
    else
    {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}

//创建栈
sNode* createStack(){
    sNode *head = (sNode *)malloc(sizeof(sNode));
    
    if(!head)
        return NULL;
    
    return head;
}

//入栈
void push(sNode **head, Node *node){
    
    sNode *newNode = (sNode *)malloc(sizeof(sNode));
    newNode -> value = node;
    newNode -> next = *head;
    
    (*head) = newNode;
}

//判断栈是否为空
int isEmpty(sNode *head)
{
    if(head->value != NULL)
        return 0;
    return 1;
}

//获取栈顶结点
Node* getTopNode(sNode* head)
{
    if(isEmpty(head))
        return NULL;
    return head->value;
}

//弹出栈顶结点
void popTopNode(sNode **head)
{
    if(isEmpty(*head))
        return;
    sNode *p = *head;
    (*head) = (*head)->next;
    free(p);
}

//先序遍历
void preOrder(Node *tree)
{
    sNode *stack = createStack();
    push(&stack,tree);
    
    while(!isEmpty(stack))
    {
        Node *node = getTopNode(stack);
        printf("%d",node->value);
        popTopNode(&stack);
        
        if(node->right)
            push(&stack,node->right);
        if(node->left)
            push(&stack,node->left);
    }
}

//后序遍历
void postOrder(Node *tree)
{
    sNode *stack1 = createStack();
    push(&stack1,tree);
    
    sNode *stack2 = createStack();
    
    while (!isEmpty(stack1)) {
        Node *node = getTopNode(stack1);
        popTopNode(&stack1);
        push(&stack2,node);
        if(node->left)
            push(&stack1,node->left);
        if(node->right)
            push(&stack1,node->right);
    }
    
    while (!isEmpty(stack2))
    {
        Node *node = getTopNode(stack2);
        printf("%d",node->value);
        popTopNode(&stack2);
    }
}

//中序遍历
void inOrder(Node *tree)
{
    sNode *stack = createStack();

    Node *cur = tree;
    
    while(!isEmpty(stack)||cur!=NULL)
    {
        if(cur)
        {
            push(&stack,cur);
            cur = cur->left;
        }
        else
        {
            Node *node = getTopNode(stack);
            printf("%d",node->value);
            popTopNode(&stack);
            cur = node->right;
        }
    }
    
}

//二叉树添加结点
void addTreeNode(Node **rootNode,int value)
{
    if(*rootNode == NULL)
    {
        *rootNode = (Node *)malloc(sizeof(Node));
        if(*rootNode == NULL){
            return;
        }
        (*rootNode)->value = value;
        (*rootNode)->left = NULL;
        (*rootNode)->right = NULL;
        return;
    }
    
    if((*rootNode)->value > value)
    {
        addTreeNode(&((*rootNode)->left),value);
    }
    else
    {
        addTreeNode(&((*rootNode)->right),value);
    }
}

int main()
{
    Node* tree = NULL;
    
    int n;
    scant("%d",&n);
    while(n>=0)
    {
         addTreeNode(&tree, n);
         scant("%d",&n);
    }
    
    inOrder(tree);
    preOrder(tree);
    postOrder(tree);

    return 0;
}