1.输入一个二叉树带虚结点的层次遍历，构建一棵不带虚结点的二叉树，并将其后序线索化，输出前序，中序，后序遍历。
注意：层次遍历相当于BFS。不能通过p=NULL设置空指针，因为这样改变不了原来的指针，更不要试图用引用指针（试过了，不行）！必须在进入下一层递归之前就判断是不是空结点。

#include<bits/stdc++.h>
using namespace std;
struct Tree{
    char data;
    Tree *lchild,*rchild,*next;
    bool LTag,RTag;//1表示有儿子，0表示没有儿子
};
Tree* CreatTree(){
    Tree *root=new Tree;
    queue<Tree*> q;
    cin>>root->data;
    q.push(root);
    while(!q.empty()){
        Tree *p=q.front();
        char data;
        cin>>data;
        if(data=='#') p->lchild=NULL,p->LTag=0;
        else{
            p->LTag=1;
            p->lchild=new Tree;
            p->lchild->data=data;
            q.push(p->lchild);
        }
        cin>>data;
        if(data=='#') p->rchild=NULL,p->RTag=0;
        else{
            p->RTag=1;
            p->rchild=new Tree;
            p->rchild->data=data;
            q.push(p->rchild);
        }
        q.pop();
    }
    return root;
}
Tree* GetFirst(Tree* root){  //返回后序遍历的第一个结点
    if(!root) return NULL;
    Tree *lc=GetFirst(root->lchild);
    if(lc&&lc->LTag==0&&lc->RTag==0) return lc;
    Tree *rc=GetFirst(root->rchild);
    if(rc&&rc->LTag==0&&rc->RTag==0) return rc;
    return root;
}
Tree* GetNext(Tree *pre,Tree *root){  //返回后继
    if(!pre) return NULL;
    if(root==pre->rchild||!pre->rchild) return pre;
    return GetFirst(pre->rchild); 
}
void PostThread(Tree *pre,Tree *root){  //后序线索化
    if(!root) return;
    PostThread(root,root->lchild);
    PostThread(root,root->rchild);
    root->next=GetNext(pre,root);
}
void PostTreval(Tree *root){  //后序遍历
     Tree* cur=GetFirst(root);
     while(cur){
         cout<<cur->data;
         cur=cur->next;
     }
}
void PreTreval(Tree* root){  //前序遍历
    if(!root) return;
    cout<<root->data;
    PreTreval(root->lchild);
    PreTreval(root->rchild);
}
void MidTreval(Tree *root){  //中序遍历
    if(!root) return;
    MidTreval(root->lchild);
    cout<<root->data;
    MidTreval(root->rchild);
}
int main(){
    Tree *root=CreatTree();
    PostThread(NULL,root);
    PreTreval(root);
    cout<<endl;
    MidTreval(root);
    cout<<endl;
    PostTreval(root);
    return 0;
}

2.输入波兰表达式，输出带括号的中缀表达式，后缀表达式和表达式的值。

#include<bits/stdc++.h>
using namespace std;
struct Tree{
    bool tag; //0表示数字，1表示运算符
    union{
        double num;
        char op;
    };
    Tree *lchild;
    Tree *rchild;
};
map<char,bool> prior;
Tree* CreatTree(){
    Tree *root=new Tree;
    char tmp=cin.peek();
    if(isalnum(tmp)){
        cin>>root->num;
        cin.get();
        root->tag=0;
        root->lchild=root->rchild=NULL;
        return root;
    }
    else{
        cin>>root->op;
        cin.get();
        root->tag=1;
    }
    root->lchild=CreatTree();
    root->rchild=CreatTree();
    return root;
}
void MidTreval(Tree *root){
    if(!root) return;
    bool flag=0;
    if(root->tag&&root->lchild->tag){
        if(prior[root->op]>prior[root->lchild->op]) flag=1;
    }
    if(flag) cout<<'(';
    MidTreval(root->lchild);
    if(flag) cout<<')';
    if(root->tag) cout<<root->op;
    else cout<<root->num;
    flag=0;
    if(root->tag&&root->rchild->tag){
        if(prior[root->op]>=prior[root->rchild->op]) flag=1;
    }
    if(flag) cout<<'(';
    MidTreval(root->rchild);
    if(flag) cout<<')';
}
void PostTreval(Tree *root){
    if(!root) return;
    PostTreval(root->lchild);
    PostTreval(root->rchild);
    if(root->tag) cout<<root->op<<' ';
    else cout<<root->num<<' ';
}
double GetValue(Tree *root){
    if(!root->tag) return root->num;
    double lnum=GetValue(root->lchild);
    double rnum=GetValue(root->rchild);
    switch(root->op){
        case '+':return lnum+rnum;
        case '-':return lnum-rnum;
        case '*':return lnum*rnum;
        case '/':return lnum/rnum;
        default: return -1;
    }
    
}
int main(){
    prior['+']=prior['-']=0;
    prior['*']=prior['/']=1;
    Tree* root=CreatTree();
    MidTreval(root);
    cout<<endl;
    PostTreval(root);
    cout<<endl;
    cout<<double(GetValue(root));
    return 0;
}