#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <assert.h>
#define MaxSize 100
#define true 1
#define false 0
typedef char Elemtype;

typedef struct BiTNode {
    Elemtype data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

// 先序序列建树；
void PreCreateTree(BiTNode **t) {
    Elemtype item;  scanf("%c", &item);
    if (item == '#') (*t) = NULL;
    else {
        (*t) = (BiTNode *)malloc(sizeof(BiTNode));
        assert((*t) != NULL);    // 若这个语句为false，则会触发警告；
        (*t)->data = item;
        PreCreateTree(&((*t)->lchild));     // 传入指向左孩子或右孩子指针的地址；
        PreCreateTree(&((*t)->rchild));
    }
}

void visit(BiTNode *t) { printf("%c", t->data); }

// 递归版先序遍历；
void PreOrder(BiTree T) {
    if (T != NULL) {
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

// 非递归版层次遍历，需构建循环队列的基本函数，其中队列的元素是树节点的指针；
typedef struct {
    BiTNode *data[MaxSize];
    int front, rear;
} SqQueue;
void InitQueue(SqQueue *q) { q->front = q->rear = 0; }
int QueueEmpty(SqQueue *q) { return q->front == q->rear ? true : false; }
int EnQueue(SqQueue *q, BiTNode **x) { 
    if ((q->rear + 1) % MaxSize == q->front) return false;
    q->data[q->rear] = (*x);
    q->rear = (q->rear + 1) % MaxSize;
    return true;
}
int DeQueue(SqQueue *q, BiTNode **x) {
    if (q->front == q->rear) return false;
    (*x) = q->data[q->front];
    q->front = (q->front + 1) % MaxSize;
    return true;
}

void LevelOrder(BiTree T) {
    SqQueue q;  InitQueue(&q);
    BiTNode *p;
    EnQueue(&q, &T);
    while (!QueueEmpty(&q)) {
        DeQueue(&q, &p);    visit(p);
        if (p->lchild) EnQueue(&q, &(p->lchild));
        if (p->rchild) EnQueue(&q, &(p->rchild));
    }
}

// 非递归中序遍历，需构建栈的基本函数，其中栈的元素也是树节点的指针；
typedef struct {
    BiTNode *data[MaxSize];
    int top;
} SqStack;
void InitStack(SqStack *s) { s->top = -1; }
int StackEmpty(SqStack *s) { return s->top == -1 ? true : false; }
int push(SqStack *s, BiTNode **x) { 
    if (s->top == MaxSize - 1) return false;
    s->data[++ s->top] = (*x);
    return true;
}
int pop(SqStack *s, BiTNode **x) {
    if (s->top == -1) return false;
    (*x) = s->data[s->top --];
    return true;
}
int GetTop(SqStack *s, BiTNode **x) {
    if (s->top == -1) return false;
    (*x) = s->data[s->top];
    return true;
}

void InOrder(BiTree T) {
    SqStack s;  InitStack(&s);
    BiTNode *p = T;
    while (p != NULL || !StackEmpty(&s)) {
        if (p) {
            push(&s, &p);
            p = p->lchild;
        }
        else {
            pop(&s, &p);    visit(p);
            p = p->rchild;
        }
    }
}

// 非递归后序遍历，若按照中序非递归来做 由于直接赋值p=p->rchild 但不存在右节点 此时p=NULL 一直GetStack() + p赋值循环 此时一直无节点弹出 死循环
// 因此加入判断条件 右节点是否存在 不存在则pop更新 通过p=NULL回溯，设置r辅助节点记录从而防止从已遍历的右节点回溯时 由GetTop的P的右节点存在导致的反复循环遍历右子树的情况；
void PostOrder(BiTree T) {
    SqStack s;  InitStack(&s);
    BiTNode *p = T, *r = NULL;
    while (p != NULL || !StackEmpty(&s)) {
        if (p) {
            push(&s, &p);
            p = p->lchild;
        }
        else {
            GetTop(&s, &p);
            if (p->rchild && p->rchild != r) p = p->rchild;
            else {
                pop(&s, &p);
                visit(p);
                r = p;
                p = NULL;
            }
        }
    }
}

// WD T4 (层次遍历 队列 + 栈);
void InvertLevel(BiTree T) {
    SqStack s;  SqQueue q;  InitStack(&s);  InitQueue(&q);
    BiTNode *p;     EnQueue(&q, &T);
    while (!QueueEmpty(&q)) {
        DeQueue(&q, &p);
        push(&s, &p);
        if (p->lchild) EnQueue(&q, &(p->lchild));
        if (p->rchild) EnQueue(&q, &(p->rchild));
    }
    while (!StackEmpty(&s)) {
        pop(&s, &p);
        visit(p);
    }
}

// WD T5 (树高度 递归与非递归)
int max(int a, int b) { return a > b ? a : b; }
int BTDepth(BiTree T) { return T != NULL ? 1 + max(BTDepth(T->lchild), BTDepth(T->rchild)) : 0; }
int BTDepth2(BiTree T) {
    if (T == NULL) return 0;    // 若树为空，此时while中队列非空 此时访问p->lchild导致SE；
    BiTNode **q = (BiTNode **)malloc(MaxSize * sizeof(BiTNode *)), *p;     // q此时是指向BiTNode *的数组；
    int front = -1, rear = -1, last = 0, level = 0;
    memset(q, 0, MaxSize * sizeof(BiTNode));
    q[++ rear] = T;
    while (front != rear) {
        p = q[++ front];
        if (p->lchild) q[++ rear] = p->lchild;
        if (p->rchild) q[++ rear] = p->rchild;
        // 当前层最后一个节点被填坑时，代表下一层的最后一个节点即当前队列中的rear；
        if (front == last) {
            level ++;
            last = rear;
        }
    }
    return level;
}

// 中序线索二叉树的创建以及遍历；
typedef struct ThreadNode {
    Elemtype data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;     // 0->左∨右孩子，1->前驱∨后继；
} ThreadNode, *ThreadTree;
void PreCreateTree2(ThreadNode **t) {
    Elemtype item;  scanf("%c", &item);
    if (item == '#') (*t) = NULL;
    else {
        (*t) = (ThreadNode *)malloc(sizeof(ThreadNode));
        assert((*t) != NULL);    // 若这个语句为false，则会触发警告；
        (*t)->data = item, (*t)->ltag = (*t)->rtag = 0;
        PreCreateTree2(&((*t)->lchild));     // 传入指向左孩子或右孩子指针的地址；
        PreCreateTree2(&((*t)->rchild));
    }
}
void InThread(ThreadNode **p, ThreadNode **pre) {
    if ((*p) != NULL) {
        InThread(&((*p)->lchild), &(*pre));
        // bug：左孩子指针为空时才线索化链接，指向前驱或后继；
        if ((*p)->lchild == NULL) (*p)->lchild = (*pre), (*p)->ltag = 1;
        if ((*pre) != NULL && (*pre)->rchild == NULL) (*pre)->rchild = (*p), (*pre)->rtag = 1;
        (*pre) = (*p);
        InThread(&((*p)->rchild), &(*pre));
    }
}
void CreateInThread(ThreadTree *T) {
    if ((*T) != NULL) {
        ThreadNode *pre = NULL;
        InThread(&(*T), &pre);
        pre->rchild = NULL;
        pre->rtag = 1;
    }
}
void visit2(ThreadNode *p) { printf("%c", p->data); }
ThreadNode *LeftMostNode(ThreadNode *p) {   // 获得线索二叉树中当前节点的最左下节点（线索化之间最左下节点lchild=NULL，线索化后ltag=1，且为第一次出现ltag非0的情况）；
    while (p->ltag == 0) p = p->lchild;
    return p;
}
ThreadNode *NextNode(ThreadNode *p) {
    if (p->rtag == 0) return LeftMostNode(p->rchild);
    else return p->rchild;
}
void ThreadInOrder(ThreadTree T) { for (ThreadNode *p = LeftMostNode(T); p != NULL; p = NextNode(p)) visit2(p); }

// WD T6 (判断是否为完全二叉树，思路：层次加入节点，包括空节点，当遍历到空节点时，判断后续是否还有实际节点存在)
int IsComplete(BiTree T) {
    SqQueue q;  InitQueue(&q);
    EnQueue(&q, &T);
    BiTNode *p;
    while (!QueueEmpty(&q)) {
        DeQueue(&q, &p);
        if (p) {
            EnQueue(&q, &(p->lchild));
            EnQueue(&q, &(p->rchild));
        }
        else {
            while (!QueueEmpty(&q)) {
                DeQueue(&q, &p);
                if (p) return false;
            }
        }
    }
    return true;
}

// WD T7 (双分支节点个数)
int DsonNode(BiTree T) {
    SqQueue q;  InitQueue(&q);
    BiTNode *p;     int num = 0;
    EnQueue(&q, &T);
    while (!QueueEmpty(&q)) {
        DeQueue(&q, &p);
        if (p->lchild && p->rchild) num ++;
        if (p->lchild) EnQueue(&q, &(p->lchild));
        if (p->rchild) EnQueue(&q, &(p->rchild));
    }
    return num;
}

// WD T8 (交换所有节点的左右子树)
void SwapLR(BiTree *T) {
    SqQueue q;  InitQueue(&q);
    BiTNode *p, *t;
    EnQueue(&q, &(*T));
    while (!QueueEmpty(&q)) {
        DeQueue(&q, &p);
        if (p->lchild) EnQueue(&q, &(p->lchild));
        if (p->rchild) EnQueue(&q, &(p->rchild));
        t = p->lchild;
        p->lchild = p->rchild;
        p->rchild = t;
    }
}

// WD T9 (前序第k个节点数据)
Elemtype FindKData(BiTree T, int k) {
    SqStack s;  InitStack(&s);
    BiTNode *p = T;     int i = 0;
    while (p != NULL || !StackEmpty(&s)) {
        if (p) {
            push(&s, &p);   i ++;
            if (i == k) return p->data;
            p = p->lchild;
        }
        else {
            pop(&s, &p);    p = p->rchild;
        }
    }
}

// WD T10 (删除所有以x为元素的子树)
void DelX(BiTree *T, Elemtype x) {
    if ((*T) == NULL) return;
    BiTNode *p;
    if ((*T)->data == x) { p = (*T); (*T) = NULL; free(p); return; }
    SqQueue q;  InitQueue(&q);
    EnQueue(&q, &(*T));
    while (!QueueEmpty(&q)) {
        DeQueue(&q, &p);
        if (p->lchild) {
            if (p->lchild->data == x) {
                free(p->lchild);
                p->lchild = NULL;
            }
            else EnQueue(&q, &(p->lchild));
        }
        if (p->rchild) {
            if (p->rchild->data == x) {
                free(p->rchild);
                p->rchild = NULL;
            }
            else EnQueue(&q, &(p->rchild));
        }
    }
}

// WD T11 妙 -->  后序变量，若访问到目标节点(题目中目标节点只有一个)时，栈中的节点全部为其祖先，因为后序的左右中遍历顺序，此时左兄弟与左右孩子节点都已经遍历完了；
// 若处于左子树中，根节点由于左子树未处理完，此时栈中不存在右子树的节点，刚好栈中只有祖先节点；若处于右子树中，此时左子树已经处理完，同样栈中也只有祖先节点；
void XAllAncestor(BiTree T, Elemtype x) {
    SqStack s;  InitStack(&s);
    BiTNode *p = T, *r = NULL;
    while (p != NULL || !StackEmpty(&s)) {
        if (p) {
            push(&s, &p);
            p = p->lchild;
        }
        else {
            GetTop(&s, &p);
            if (p->rchild && p->rchild != r) p = p->rchild;
            else {
                pop(&s, &p);
                if (p->data == x) break;
                r = p;
                p = NULL;
            }
        }
    }
    while (!StackEmpty(&s)) {
        pop(&s, &p);
        visit(p);
    }
}

// WD T12 (最近公共祖先 important)
BiTNode *MRecentAncestor(BiTree T, BiTNode *p, BiTNode *q) {
    SqStack s1, s2;  InitStack(&s1);
    BiTNode *t = T, *r = NULL;
    int tag = 0;
    while (t != NULL || !StackEmpty(&s1)) {
        if (t) {
            push(&s1, &t);
            t = t->lchild;
        }
        else {
            GetTop(&s1, &t);
            if (t->rchild && t->rchild != r) t = t->rchild;
            else {
                pop(&s1, &t);
                if (tag == 0 && (t == p || t == q)) {
                    tag = (t == p) ? 1 : 2;
                    // s2作为辅助栈保存；继续后序遍历，直到找到另一个目标节点才break；
                    s2 = s1;
                }
                if (tag == 1 && t == q) break;
                if (tag == 2 && t == p) break;
                r = t;
                t = NULL;
            }
        }
    }
    // 栈的元素从下标0开始，直到top；
    for (int i = s1.top; i >= 0; i --)
        for (int j = s2.top; j >= 0; j --)
            if (s2.data[j] == s1.data[i])
                return s2.data[i];
    return NULL;
}

// WD T13 (树的宽度)
int BTWidth(BiTree T) {
    if (T == NULL) return 0;
    BiTNode **q = (BiTNode **)malloc(MaxSize * sizeof(BiTNode *));
    int front = -1, rear = -1, last = 0, width = 1;
    memset(q, 0, MaxSize * sizeof(BiTNode *));
    BiTNode *p;     q[++ rear] = T;
    // 此时从根节点向下的第二层开始计算宽度，最后一次的width计算为zero；
    while (front != rear) {
        p = q[++ front];
        if (p->lchild) q[++ rear] = p->lchild;
        if (p->rchild) q[++ rear] = p->rchild;
        if (last == front) {    // 此时遍历到了该层的最右侧节点，此时下一层的宽度即rear - front，此时更新last指针；
            width = (rear - front) > width ? (rear - front) : width;
            last = rear;
        }
    }
    return width;
}

// WD T14 (满二叉树前序转后序)
void PreToPost(Elemtype pre[], int l1, int h1, Elemtype post[], int l2, int h2) {
    int half;
    if (l1 <= h1) {  // 一个元素时，从pre获得唯一元素填坑至post，然后向下递归 此时half为0 由于l1 + 1 > l1 + half 且 l1 + half + 1 > h1，递归结束；
        post[h2] = pre[l1];
        half = (h1 - l1) >> 1;
        PreToPost(pre, l1 + 1, l1 + half, post, l2, l2 + half - 1);
        PreToPost(pre, l1 + half + 1, h1, post, l2 + half, h2 - 1);
    }
}

// WD T15 (叶节点从左向右链接成单链表，思路：先序或者中序遍历，pre记录上次遍历到的叶节点，当再次遍历到右节点时，建立其指向，其中以rchild作为next指针)
BiTNode *TreeNodeToList(BiTree *T) {
    SqStack s;  InitStack(&s);
    BiTNode *p = (*T), *pre = NULL, *head;
    while (p != NULL || !StackEmpty(&s)) {
        if (p) {
            push(&s, &p);
            p = p->lchild;
        }
        else {
            pop(&s, &p);
            if (p->lchild == NULL && p->rchild == NULL) {
                if (pre != NULL) pre->rchild = p, pre = p;
                else head = p, pre = p;
            }
            p = p->rchild;
        }
    }
    pre->rchild = NULL;
    return head;
}

// WD T16 (树相似，即结构相同；与T14一致，本质上也是递归解决问题，确定递归终止条件 以及 递归函数)
int Similar(BiTree T1, BiTree T2) {
    if (T1 == NULL && T2 == NULL) return true;
    else if (T1 == NULL || T2 == NULL) return false;
    else {
        int LeftT = Similar(T1->lchild, T2->lchild);
        int RightT = Similar(T1->rchild, T2->rchild);
        return LeftT & RightT;
    }
}

// WD T17 (带权路径长度，起始的data本质上即节点的weight权值，层次遍历)
int WL(BiTree T) {
    if (T == NULL) return 0;
    // 手动构建非循环队列，front与rear的灵活运用；
    BiTNode **q = (BiTNode **)malloc(MaxSize * sizeof(BiTNode *));
    memset(q, 0, MaxSize * sizeof(BiTNode *));
    int front = -1, rear = -1, last = 0, level = 0, WL = 0;     BiTNode *p;
    q[++ rear] = T;
    while (front != rear) {
        p = q[++ front];
        // 并非判断是否为完全二叉树，对于子节点为空节点的情况不加入队列，否则出现SE；
        if (p->lchild) q[++ rear] = p->lchild;
        if (p->rchild) q[++ rear] = p->rchild;
        WL += (p->data - 'A') * (level + 1);
        if (front == last) {
            level ++;
            last = rear;
        }
    }
    return WL;
}

// WD T18 (中缀表达式输出，递归)
void BiTreeToExp(BiTNode *t, int deep) {
    // 根节点与叶子节点不加括号，因此加入deep参数与if判断；
    if (t == NULL) return;
    else if (t->lchild == NULL && t->rchild == NULL) printf("%c", t->data);
    else {
        if (deep > 1) printf("(");
        BiTreeToExp(t->lchild, deep + 1);
        printf("%c", t->data);
        BiTreeToExp(t->rchild, deep + 1);
        if (deep > 1) printf(")");
    }
}

// 延伸的知识（中缀表达式 转 后缀表达式，核心思路：建立存储运算符的栈，根据优先级判断是否弹出，*/ > +- > ()，规则是若栈空/优先级高于栈顶操作符，则入栈，一旦低于或等于栈顶优先级 以及 栈空，则出栈，对于左括号直接入栈，对于右括号出栈直到匹配到左括号，应当在中缀字符串遍历时就对负号进行处理，若该负号代表负数而不是运算符，则中缀表达式中前面会搭配一个括号，假如是 运算符，则前面是一个数字）
// 对于带负号的后缀表达式的计算，可以通过表达式之间的空格来判断；
int Priority(char op) {
    switch (op) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        default:
            return 0;
    }
}
int _isdigit(char c) { return c >= '0' && c <= '9'; }
// 建立在WD T18下的中缀表达式，即根节点不带括号，叶节点不带括号，对于负数，用括号包含；
char *InfixToPostfix(char *infix) {
    char *postfix = (char *)malloc(MaxSize * sizeof(char));
    char *s = (char *)malloc(MaxSize * sizeof(char));
    int top = -1, i = 0, j = 0;
    while (infix[i] != '\0') {
        if (_isdigit(infix[i])) {
            while (_isdigit(infix[i]))
                postfix[j ++] = infix[i ++];
            postfix[j ++] = ' ';
        }
        else if (infix[i] == '-' && infix[i - 1] == '(') postfix[j ++] = infix[i ++];
        else if (infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/') {
            if (top == -1 || Priority(infix[i]) > Priority(s[top])) s[++ top] = infix[i ++];
            else postfix[j ++] = s[top --], postfix[j ++] = ' ';
        }
        else if (infix[i] == '(') s[++ top] = infix[i ++];
        else if (infix[i] == ')') {
            while (s[top] != '(') postfix[j ++] = s[top --], postfix[j ++] = ' ';
            top --, i ++;
        }
    }
    while (top != -1) postfix[j ++] = s[top --], postfix[j ++] = ' ';
    postfix[j] = '\0';
    return postfix;
}
int CalPostfix(char *postfix) {
    int *s = (int *)malloc(MaxSize * sizeof(int));
    int top = -1, i = 0;
    while (postfix[i] != '\0') {
        if (postfix[i] == ' ') i ++;
        else if (_isdigit(postfix[i]) || (postfix[i] == '-' && (i == 0 || _isdigit(postfix[i + 1])))) {
            int num = 0, sign = 1;
            if (postfix[i] == '-') sign = -1, i ++;
            while (_isdigit(postfix[i]))
                num = num * 10 + postfix[i ++] - '0';
            s[++ top] = sign * num;
        }
        else {
            char op = postfix[i ++];
            int a = s[top --], b = s[top --];
            switch (op) {
                case '+': s[++ top] = b + a; break;
                case '-': s[++ top] = b - a; break;
                case '*': s[++ top] = b * a; break;
                case '/': s[++ top] = b / a; break;
            }
        }
    }
    return s[top --];
}

// WD T19 (顺序存储的二叉搜索树) 定义：非空左子树的所有键值小于其根结点的键值；非空右子树的所有键值大于其根结点的键值；左、右子树都是二叉搜索树；
typedef struct {
    int SqBiTNode[MaxSize];
    int ElemNum;
} SqBiTree;
typedef int bool;
bool IsSearchBiTree(SqBiTree T) {
    // 节点个数为奇数时，此时最后一个节点为右节点；偶数时，最后一个节点为左节点；
    int end = (T.ElemNum % 2 == 1) ? (T.ElemNum - 1) / 2 : (T.ElemNum - 2) / 2;
    //遍历到最后一个节点的父节点的下标为止；
    for (int i = 0; i < end; i ++) {
        if (T.SqBiTNode[i] != -1) {
            if (T.SqBiTNode[2 * i + 1] != -1 && T.SqBiTNode[2 * i + 1] >= T.SqBiTNode[i]) return false;
            if (T.SqBiTNode[2 * i + 2] != -1 && T.SqBiTNode[2 * i + 2] <= T.SqBiTNode[i]) return false;
        }
    }
    if (T.ElemNum % 2 == 1) return T.SqBiTNode[2 * end + 1] < T.SqBiTNode[end];
    else return (T.SqBiTNode[2 * end + 1] < T.SqBiTNode[end]) && (T.SqBiTNode[2 * end + 2] > T.SqBiTNode[end]);
}

int main() {
    BiTree root;    // 此时只是声明了指向结构体的指针，并没有为其指向的结构体元素分配内存空间，需要malloc动态分配；
    PreCreateTree(&root);
    // begin；
    // 函数调用test；
    // end；
    return 0;
}