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

//定义树结构
typedef struct tree_node_tag...{
    int value;
    struct tree_node_tag *left;
    struct tree_node_tag *right;
} TreeNode;

//通过父节点插入建立二叉树
void insert_node(TreeNode *parent, TreeNode *node)
...{
    if (!parent)    //插入时必须确保父节点不为空
    ...{
        cout << "parent not null" << endl;
        return;
    }
    if (node->value < parent->value) ...{    //比父节点小则插入左子树
        if (parent->left != NULL) ...{        //如果左子树还有节点，则继续
            insert_node(parent->left, node);
        }
        else
        ...{                                //否则直接插入
            parent->left = node;
            return;
        }
    }
    else...{
        if (parent->right != NULL) ...{
            insert_node(parent->right, node);
        }
        else
        ...{
            parent->right = node;
            return;
        }
    }
}
//分配节点空间
int  new_node(TreeNode **node)
...{
    *node=(TreeNode*)malloc(sizeof(TreeNode));
    if (*node == NULL) ...{
        return -1;
    }
    (*node)->left=(*node)->right = NULL;
    (*node)->value = 0;
    return 0;
}
//创建二叉树
void create_tree(TreeNode **head)
...{
    TreeNode *p=NULL;
    int value;
    int ret;
    TreeNode *node= NULL;
    
    ret = new_node(&node);
    if ( ret == -1) ...{
        cout << "new_node error" << endl;
        return;
    }
    //指向头节点
    p=node;
    *head=p;
    cin >> value;
    node->value = value;
    //插入其它节点,以-1为结束标志
    while (1) 
    ...{
        cin >> value;
        if (value == -1)    break;
        ret = new_node(&node);
        if ( ret == -1) ...{
            cout << "new_node error" << endl;
            return;
        }
        node->value = value;
        insert_node(p,node);
    }
}

//输出节点
void print(TreeNode *t)
...{
    cout << t->value << " ";
}

void del_node(TreeNode *current)
...{
    free(current);
    current = NULL;
}

void preorder(TreeNode *t, void (*pred)(TreeNode *))
...{
    if (t) ...{
        pred(t);
        preorder(t->left, pred);
        preorder(t->right, pred);
    }
}

void inorder(TreeNode *t, void (*pred)(TreeNode *))
...{
    if (t) ...{
        inorder(t->left, pred);
        pred(t);
        inorder(t->right, pred);
    }
}

void postorder(TreeNode *t, void (*pred)(TreeNode *))
...{
    if (t) ...{
        postorder(t->left, pred);
        postorder(t->right, pred);
        pred(t);
    }
}
void hierarchy(TreeNode *t, void (*pred)(TreeNode *))
...{
    queue<TreeNode *> que;
    TreeNode *pTmp = NULL;
    que.push(t);

    while (!que.empty()) ...{
        pTmp = que.front();
        if (pTmp->left != NULL) ...{
            que.push(pTmp->left);
        }
        if (pTmp->right != NULL) ...{
            que.push(pTmp->right);
        }
        pred(pTmp);
        que.pop();        
    }
}

void visit(TreeNode *t, void (*pred1)(TreeNode *), void(*pred)(TreeNode *, void (*)(TreeNode *)))
...{
    if (t) ...{
        pred(t, pred1);
    }
}
void clear(TreeNode **head)
...{
    //后序遍历清空
    visit(*head, del_node, postorder);
    *head = NULL;
}
void main(void)
...{
    TreeNode *head=NULL;
    //空头节点
    cout << "建立二叉树，节点数据为整型，以-1为输入结束" <<endl;
    create_tree(&head);
    
    //前序遍历
    cout << "前序遍历" << endl;
    visit(head, print, preorder);
    cout << endl;

    cout << "中序遍历" << endl;
    visit(head, print, inorder);
    cout << endl;

    cout << "后序遍历" << endl;
    visit(head, print, postorder);
    cout << endl;

    cout << "层次遍历" << endl;
    visit(head, print,hierarchy);
    cout << endl;

    cout << "清空二叉树" << endl;
    clear(&head);
    visit(head, print, inorder);
    cout << endl;
    
    getchar();
}