#include <stdio.h>
#include <stdlib.h>
#define num 100

typedef struct node
{
    char data;
    struct node *lchild,*rchild;
}binTnode;
typedef binTnode * binTree;

int found;
binTnode *p;


binTree createBinTree(binTree bt)     //二叉树建立函数
{
    binTnode * q[num];
    binTnode *s;
    int front,rear;
    char ch;
    ch = getchar();
    bt = NULL;
    front = 1;
    rear = 0;      //初始化队列
    while(ch != '#')
    {
        s = NULL;
        if(ch != '@')
        {
            s = (binTnode *)malloc(sizeof(binTnode));
            s -> data = ch;
            s -> lchild = s ->rchild = NULL;    //新节点赋值
        }
        rear ++;
        q[rear] = s;
        if(rear == 1)
        bt = s;
        else
        {
            if(s != NULL && q[front] != NULL)    //当前结点及其双亲结点都不是虚结点
            
            if(rear % 2 == 0)                // rear为偶数，新节点应作为左孩子
            q[front] ->lchild = s;
            else
            q[front] ->rchild = s;           //rear 为奇数，新结点应作为右孩子
            
            if(rear % 2 != 0)
            front ++;    //rear为奇数，说明两个孩子已经处理完毕，front指向下一个双亲
        }
        ch = getchar();    //读取下一个节点的值
    }
    return bt;
}


void nodePath(binTree bt,binTnode *ch)  //求二叉树根结点到指定结点*p的路径函数
{
    typedef enum {FALSE,TRUE} boolean;
    binTnode *stack[num];      //定义栈
    int tag[num];             //标志数组
    int top,i;
    boolean find;
    binTnode *s;
    find = FALSE;
    top = 0;
    s = bt;
    do
    {
        while(s != NULL)
        {//扫描左子树
            top ++;
            stack[top] = s;
            tag[top] = 0;
            s = s ->lchild;
        }
        if(top > 0)
        {
            s = stack[top];
            if(tag[top] == 1)
            {
                if(s == ch)
                {//找到ch，则显示从根结点到ch之间的路径
                    for(i = 1;i <= top;i ++)
                    printf("->%c",stack[i] ->data);
                    find = TRUE;
                }
                else
                top --;
                s = stack[top];
            }
            if(top > 0 && !find)
            {
                if(tag[top] != 1)
                {
                    s = s ->rchild;
                    tag[top] = 1;
                }
                else s = NULL;
            }
        }
    } while(!find && top != 0);
}

void preorder(binTree bt)
{//非递归前序遍历二叉树
    binTnode * stack[num];
    int top = 0;
    binTnode *s;
    stack[top] = bt;
    while(top >= 0)
    {
        s = stack[top];
        top --;
        if(s != NULL)
        {
            printf("%c",s ->data);
            top ++;
            stack[top] = s ->rchild;
            top ++;
            stack[top] = s ->lchild;
        }
    }
}

void inorder(binTree bt)
{//非递归中序遍历算法
    binTnode * stack[num];
    int top = 0;
    stack[top] = bt;
    do
    {
        while(stack[top] != NULL)
        {
            top = top + 1;
            stack[top] = stack[top - 1] ->lchild;
        }
        top = top - 1;
        if(top >= 0)
        {
            printf("%c",stack[top] ->data);
            stack[top] = stack[top] ->rchild;
        }
    }while(top >= 0);
}

void postorder(binTree bt)
{//非递归后序遍历算法
    binTnode *stack[num];
    int tag[num];
    int top;
    binTnode *s;
    top = 0;
    s = bt;
    do
    {
        while(s != NULL)
        {
            top ++;
            stack[top] = s;
            tag[top] = 0;
            s = s ->lchild;
        }
        
        if(top > 0)
        {
            s = stack[top];
            if(tag[top] == 1)
            {
                printf("%c",stack[top] ->data);
                top --;
                s = stack[top];
            }
            if(top > 0)
            {
                if(tag[top] != 1)
                {
                    s = s ->rchild;
                    tag[top] = 1;
                }
                else
                s = NULL;
            }
        }
    }while(top != 0);
}

void findbt(binTree bt,char x)
{
    if((bt != NULL) && !found)
    {
        if(bt ->data == x)
        {
            p = bt;
            found = 1;
        }
        else
            {
            findbt(bt ->lchild,x);
            findbt(bt ->rchild,x);
            }
    }
}
binTnode *findx(binTree bt,char x)
{
    found = 0;    //用来标志是否找到
    p = NULL;
    findbt(bt,x);
    return (p);
}


void main()
{
    binTree bt;
    int xz = 1;
    char ch1;
    while(xz)
    {
        printf(" 二叉树的遍历以及求结点路径   \n");
        printf("==============================\n");
        printf("       1.建立二叉树存储结构   \n");
        printf("       2.求二叉树的前序遍历   \n");
        printf("       3.求二叉树的中序遍历   \n");
        printf("       4.求二叉树的后序遍历   \n");
        printf("       5.求指定结点的路径     \n");
        printf("       0.退 出 系 统          \n");
        printf("==============================\n");
        printf("请 选 择: 0---5\n");
        scanf("%d",&xz);
        switch(xz)
        {
            case 1:
            printf("请输入二叉树的按层结点值(按照完全二叉树)：\n");
            getchar();
            bt = createBinTree(bt);
            printf("二叉树的链式存储结构构建完毕!\n");
            printf("\n");
            break;
            
            case 2:
            printf("该二叉树的前序遍历为: ");
            preorder(bt);
            printf("\n");
            printf("\n");
            break;
            
            case 3:
            printf("该二叉树的中序遍历为: ");
            inorder(bt);
            printf("\n");
            printf("\n");
            break;
            
            case 4:
            printf("该二叉树的后序遍历为: ");
            postorder(bt);
            printf("\n");
            printf("\n");
            break;
            
            case 5:
            printf("输入要求路径的结点值: ");
            ch1 = getchar();
            ch1 = getchar();
            p = findx(bt,ch1);
            if(p != NULL)
            {
            nodePath(bt,p);
            printf("\n");    
            }            
            else
            {
            printf("没有要求的结点,请检查!\n");
            printf("\n");    
            }
            break;
        }
    }
}