#define _CRT_SECURE_NO_WARNINGS
 
#define m 100
 
typedef char DataType;
typedef struct Node /*二叉链表的结构体*/
{
    DataType data;
    struct Node * LChild;
    struct Node * RChild;
}BiTNode, *BiTree;
 
#define Queue_Size 100
 
typedef BiTree QueueElement;
typedef struct //定义顺序队列的结构体
{
    QueueElement elem[Queue_Size]; //存放队列元素的一维数组
    int top; //用来存放队列元素的下标,top=-1表示空队
}SeqQueue;
 
 
BiTree CreateBiTree(void);//创建二叉链表
void InOrder(BiTree root);//中序递归遍历二叉树
void inoeder(BiTree  root); //中序非递归遍历二叉树
int LayerOrder(BiTree bt);/*层次遍历二叉树*/
int PostTreeDepth(BiTree bt); /*后序遍历二叉树求高度的递归算法*/
int leaf(BiTree root); /*后序遍历统计叶子结点的个数*/
int PreOrder(BiTree root);/*先序求二叉树中结点的个数*/
void ChangeBit(BiTree root);/*交换每个结点的左右子树*/
void EnterQueue(SeqQueue * s, QueueElement x);  //顺序入队函数
void DeleteQueue(SeqQueue * s);  //顺序出队函数
#include <stdio.h>
#include <stdlib.h>
 
int main()
{
    int choose = 0;
    do
    {
        printf("\t\t\t二叉树的简单操作\n");
        printf("\t\t1 二叉树链表的建立\n");
        printf("\t\t2 二叉树的中序递归遍历\n");
        printf("\t\t3 二叉树的中序非递归遍历\n");
        printf("\t\t4 二叉树的层次遍历\n");
        printf("\t\t5 二叉树的高度\n");
        printf("\t\t6 二叉树结点的个数\n");
        printf("\t\t7 二叉树叶子的个数\n");
        printf("\t\t8 交换二叉树的左右子树\n");
        printf("\t\t0 退出\n");
        scanf("%d", &choose);
        switch (choose)
        {
        case 1:
        {
            BiTree bt = NULL;
            getchar();//接收空格
            printf("请用先序遍历扩展输入二叉树(.表示空子树):\n");
            bt = CreateBiTree();
            break;
        }
        case 2:
        {
            BiTree bt = NULL;
            getchar();//接收空格
            printf("请用先序遍历扩展输入二叉树(.表示空子树):\n");
            bt = CreateBiTree();
            printf("中序递归遍历为:");
            InOrder(bt);
            printf("\n");
            break;
        }
        case 3:
        {
            BiTree bt = NULL;
            getchar();//接收空格
            printf("请用先序遍历扩展输入二叉树(.表示空子树):\n");
            bt = CreateBiTree();
            printf("中序非递归遍历为:");
            inoeder(bt);
            printf("\n");
            break;
        }
        case 4:
        {
            BiTree bt = NULL;
            getchar();//接收空格
            printf("请用先序遍历扩展输入二叉树(.表示空子树):\n");
            bt = CreateBiTree();
            printf("层次遍历结果为:");
            int ret = LayerOrder(bt);
            printf("\n");
            break;
        }
        case 5:
        {
            BiTree bt = NULL;
            getchar();//接收空格
            printf("请用先序遍历扩展输入二叉树(.表示空子树):\n");
            bt = CreateBiTree();
            printf("二叉树的高度为%d\n", PostTreeDepth(bt));
            break;
        }
        case 6:
        {
            BiTree bt = NULL;
            getchar();//接收空格
            printf("请用先序遍历扩展输入二叉树(.表示空子树):\n");
            bt = CreateBiTree();
            printf("结点的个数为:%d\n", PreOrder(bt));
            break;
        }
        case 7:
        {
            BiTree bt = NULL;
            getchar();//接收空格
            printf("请用先序遍历扩展输入二叉树(.表示空子树):\n");
            bt = CreateBiTree();
            printf("叶子结点的个数为:%d\n", leaf(bt));
            break;
        }
        case 8:
        {
            BiTree bt = NULL;
            getchar();//接收空格
            printf("请用先序遍历扩展输入二叉树(.表示空子树):\n");
            bt = CreateBiTree();
            ChangeBit(bt);
            printf("交换之后中序遍历的结果为:");
            InOrder(bt);
            printf("\n");
            break;
        }
        case 0:
        {
            break;
        }
        default:
        {
            break;
        }
        }
    } while (choose != 0);
    system("pause");
    return 0;
}
 
void EnterQueue(SeqQueue * s, QueueElement x)  //顺序入队函数
{
    if (s->top == Queue_Size - 1)
        return;
    s->top++;
    s->elem[s->top] = x;
}
 
void DeleteQueue(SeqQueue * s)  //顺序出队函数
{
    if (s->top == -1)
        return;
    else
    {
        for (int i = 0; i < s->top; i++)
        {
            s->elem[i] = s->elem[i + 1];
        }
        s->top--;
    }
}
 
void Vist(char p)
{
    printf("%c ", p);
}
 
BiTree CreateBiTree(void)//创建二叉链表
{
    char ch;
    BiTree bt = NULL;
    scanf("%c", &ch);
    if ('.' == ch)
    {
        bt = NULL;
    }
    else
    {
        bt = (BiTree)malloc(sizeof(BiTNode));
        bt->data = ch;
        bt->LChild = CreateBiTree();
        bt->RChild = CreateBiTree();
    }
    return bt;
}
 
void InOrder(BiTree root)//中序递归遍历二叉树
{
    /*assert(root==NULL);*/
    if (root != NULL)
    {
        InOrder(root->LChild);
        Vist(root->data);
        InOrder(root->RChild);
    }
}
 
void inoeder(BiTree  root) //中序非递归遍历二叉树
{
    int top = 0;
    BiTree s[m];//栈最多存储100个元素m=100
    BiTree p = root;
    do
    {
        while (p != NULL)
        {
            if (top > m)
                return;
            top++;
            s[top] = p;
            p = p->LChild;
        }/*遍历左子树*/
        if (top != 0)
        {
            p = s[top];
            top--;
            Vist(p->data);/*访问根节点*/
            p = p->RChild;
        }/*遍历右子树*/
    } while (p != NULL || top != 0);
}
 
int LayerOrder(BiTree bt)/*层次遍历二叉树*/
{
    //assert(bt);
    SeqQueue * Q;
    Q = (SeqQueue*)malloc(sizeof(SeqQueue));
    Q->top = -1;
    BiTree p;
    if (bt == NULL)
    {
        return -1;
    }
    EnterQueue(Q, bt);
    while (Q->top > -1)
    {
        p = Q->elem[0];
        DeleteQueue(Q);
        Vist(p->data);
        if (p->LChild)
        {
            EnterQueue(Q, p->LChild);
        }
        if (p->RChild)
        {
            EnterQueue(Q, p->RChild);
        }
    }
    return 1;
}
 
int PostTreeDepth(BiTree bt) /*后序遍历二叉树求高度的递归算法*/
{
    //assert(bt);
    int hl, hr, max;
    if (NULL != bt)
    {
        hl = PostTreeDepth(bt->LChild);/*得到左子树的高度*/
        hr = PostTreeDepth(bt->RChild);/*得到右子树的高度*/
        max = hl > hr ? hl : hr;/*得到左右子树深度角度较大的*/
        return (max + 1);
    }
    else
    {
        return 0;/*如果是空树,返回0*/
    }
}
 
int leaf(BiTree root) /*后序遍历统计叶子结点的个数*/
{
    //assert(root);
    static int LeafCount = 0;
    if (NULL != root)
    {
        leaf(root->LChild);
        leaf(root->RChild);
        if ((NULL == root->LChild) && (NULL == root->RChild))
        {
            LeafCount++;
        }
    }
    return LeafCount;
}
 
int PreOrder(BiTree root)/*先序求二叉树中结点的个数*/
{
    //assert(root);
    static int BitCount = 0;
    if (NULL != root)
    {
        PreOrder(root->LChild);
        PreOrder(root->RChild);
        BitCount++;
    }
    return (BitCount);
}
 
void ChangeBit(BiTree root)/*交换每个结点的左右子树*/
{
    //assert(root);
    BiTree tmp = NULL;
    if (NULL != root)
    {
        tmp = root->LChild;
        root->LChild = root->RChild;
        root->RChild = tmp;
        ChangeBit(root->LChild);
        ChangeBit(root->RChild);
    }
}