#include<iostream>
#include<stack>
#include<queue>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
//二叉树结点
typedef struct BiTNode
{
    //数据
    char data;
    //左右孩子指针
    struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;
//重命名 将struct BiTNode命名为BiTNode，将struct BiTNode*命名为BiTree
//按先序序列创建二叉树
int CreateBiTree(BiTree &T)//引用
{
    char data;
    //按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树
    scanf("%c",&data);
    if(data =http://www.mamicode.com/= ‘#‘)
    {
        T = NULL;
    }
    else
    {
        T = (BiTree)malloc(sizeof(BiTNode));
        //生成根结点
        T->data =http://www.mamicode.com/ data;
        //构造左子树
        CreateBiTree(T->lchild);
        //构造右子树
        CreateBiTree(T->rchild);
    }
    return 0;
}
//输出
void Visit(BiTree T)
{
    if(T->data != ‘#‘)
    {
        printf("%c ",T->data);
    }
}
//先序遍历
void PreOrder(BiTree T)
{
    if(T != NULL)
    {
        //访问根节点
        Visit(T);
        //访问左子结点
        PreOrder(T->lchild);
        //访问右子结点
        PreOrder(T->rchild);
    }
}
//中序遍历
void InOrder(BiTree T)
{
    if(T != NULL)
    {
        //访问左子结点
        InOrder(T->lchild);
        //访问根节点
        Visit(T);
        //访问右子结点
        InOrder(T->rchild);
    }
}
//后序遍历
void PostOrder(BiTree T)
{
    if(T != NULL)
    {
        //访问左子结点
        PostOrder(T->lchild);
        //访问右子结点
        PostOrder(T->rchild);
        //访问根节点
        Visit(T);
    }
}
//层次遍历
void LevelOrder(BiTree T)
{
    BiTree p = T;
    //队列
    queue<BiTree> queue;
    //根节点入队
    queue.push(p);
    //队列不空循环
    while(!queue.empty())
    {
        //对头元素出队
        p = queue.front();
        //访问p指向的结点
        printf("%c ",p->data);
        //退出队列
        queue.pop();
        //左子树不空，将左子树入队
        if(p->lchild != NULL)
        {
            queue.push(p->lchild);
        }
        //右子树不空，将右子树入队
        if(p->rchild != NULL)
        {
            queue.push(p->rchild);
        }
    }
}
//叶子节点个数
int TreeCount(BiTree T)
{
    if(T == NULL)
    {
        return 0;
    }
    else if ((T->lchild==NULL) && (T->rchild==NULL))
    {
        return 1;//如果此节点是叶子节点，返回1 即它本身是一个节点。
    }
    else
    {
        return TreeCount(T->lchild)+TreeCount(T->rchild);//如果左右孩子不空，返回左孩子+右孩子节点数。
    }
}
//求深度
int TreeDepth(BiTree T)
{
    int rightdep=0;
    int leftdep=0;
　　//如果是空树，返回-1
    if(T==NULL)
        return -1;
　　//如果左孩子不空，继续递归，如果为空，返回-1
    if(T->lchild!=NULL)
        leftdep=TreeDepth(T->lchild);
    else
        leftdep=-1;
   //如果右孩子不空，继续递归，如果为空，返回-1
    if(T->rchild!=NULL)
        rightdep=TreeDepth(T->rchild);
    else
        rightdep=-1;
　　//左右孩子都递归完，返回左右孩子中较大的值
    return (rightdep>leftdep) ? rightdep+1 : leftdep+1;
}
//交换左右孩子
void TreeExchange(BiTree T)
{
    if(T!=NULL)
    {
        BiTree temp;
        if(T->lchild||T->rchild)
        {
            temp=T->lchild;
            T->lchild=T->rchild;
            T->rchild=temp;
            TreeExchange(T->lchild);
            TreeExchange(T->rchild);
        }
    }
}
int main()
{
    BiTree T;
    CreateBiTree(T);
    printf("先序遍历：\n");
    PreOrder(T);
    printf("\n\n");

    printf("中序遍历：\n");
    InOrder(T);
    printf("\n\n");

    printf("后序遍历：\n");
    PostOrder(T);
    printf("\n\n");

    printf("层次遍历：\n");
    LevelOrder(T);
    printf("\n\n");

    int deep=TreeDepth(T);
    printf("树的深度：%d\n\n",deep+1);

    int number=TreeCount(T);
    printf("叶子节点个数：%d\n\n",number);

    printf("交换左右孩子成功\n\n");
    TreeExchange(T);

    printf("层次遍历：\n");
    LevelOrder(T);
    printf("\n");
    printf("\n");
    return 0;
}