#include <myhead.h>
 
// 定义二叉树节点结构体
struct tree 
{
    char value;  //二叉树的值
    struct tree* left;  //左子树
    struct tree* right;  //右子树
};
 
// 创建节点
struct tree* create_node(int value) 
{
    //申请空间
    struct tree* new = (struct tree*)malloc(sizeof(struct tree));
 
    //节点初始化
    new->value = value;
    new->left = NULL;
    new->right = NULL;
    return new;
}
 
// 创建二叉树
struct tree* create_tree() 
{
    //创建根节点
    struct tree* root = create_node('a');
 
    //创建根节点的左孩子节点
    root->left = create_node('b');
    //创建根节点的右孩子节点
    root->right = create_node('c');
 
    //创建根节点的左孩子节点的左孩子节点
    root->left->left = create_node('d');
    //创建根节点的左孩子节点的右孩子节点
    root->left->right = create_node('e');
	//创建根节点右孩子节点的左孩子节点
	root->right->left = create_node('f');
	//创建根节点右孩子节点的右孩子节点
	root->right->right = create_node('g');
    return root;
}
 
// 前序遍历  依次遍历根节点、左子树、右子树，直到所有节点都被遍历完毕
void front(struct tree* node) 
{
    //当节点不为空时
    if (node != NULL) 
    {
        printf("%c ", node->value);
        front(node->left);
        front(node->right);
    }
}
 
// 中序遍历  依次遍历左子树、根节点、右子树，直到所有节点都被遍历完毕
void middle(struct tree* node) 
{
    //当节点不为空时
    if (node != NULL)
    {
        middle(node->left);
        printf("%c ", node->value);
        middle(node->right);
    }
}
 
// 后序遍历  依次遍历左子树、右子树、根节点，直到所有节点都被遍历完毕
void last(struct tree* node) 
{
    //当节点不为空时
    if (node != NULL)
    {
        last(node->left);
        last(node->right);
        printf("%c ", node->value);
    }
}
 
// 销毁二叉树  采用后序的方式进行二叉树的销毁，这样可以完全销毁二叉树
void destroy_tree(struct tree* node) 
{
    //当节点不为空时
    if (node != NULL) 
    {
        destroy_tree(node->left);
        destroy_tree(node->right);
        free(node);
    }
}
 
//主函数
int main(int argc,const char * argv[]) 
{
    //定义二叉树的根节点，并同时创建一个二叉树
    struct tree* root = create_tree();
    //前序遍历二叉树
    printf("前序遍历: ");
    front(root);
 
    //中序遍历二叉树
    printf("\n中序遍历: ");
    middle(root);
 
    //后序遍历二叉树
    printf("\n后序遍历: ");
    last(root);
 
	printf("\n");
 
    //销毁二叉树
    destroy_tree(root);
    return 0;
}