1.(6.51)輸出以二叉樹表示的算術(shù)表達(dá)式湃交，結(jié)果含有括號(hào)。
注意藤巢，對(duì)于左子樹搞莺，如果運(yùn)算符優(yōu)先級(jí)比根小，要加括號(hào)掂咒，但是相等不用才沧，因?yàn)楸緛砭拖人阕筮叄粚?duì)于右子樹俏扩，如果運(yùn)算優(yōu)先級(jí)小于等于根糜工，要加括號(hào)弊添。

#include<bits/stdc++.h>
using namespace std;
struct Tree{
    char data;
    Tree *lchild;
    Tree *rchild;
};
map<char,bool> prior;
void CreatTree(Tree* root){
    char data;
    cin>>data;
    root->data=data;
    if(isalnum(data)){
        root->lchild=root->rchild=NULL;
        return;
    }
    root->lchild=new Tree;
    CreatTree(root->lchild);
    root->rchild=new Tree;
    CreatTree(root->rchild);
}
void MidTreval(Tree *root){
    if(!root) return;
    bool flag=0;
    if(!isalnum(root->data)&&!isalnum(root->lchild->data)){
        if(prior[root->data]>prior[root->lchild->data]) flag=1;
    }
    if(flag) cout<<'(';
    MidTreval(root->lchild);
    if(flag) cout<<')';
    cout<<root->data;
    flag=0;
    if(!isalnum(root->data)&&!isalnum(root->rchild->data)){
        if(prior[root->data]>=prior[root->rchild->data]) flag=1;
    }
    if(flag) cout<<'(';
    MidTreval(root->rchild);
    if(flag) cout<<')';
}
int main(){
    prior['+']=prior['-']=0;
    prior['*']=prior['/']=1;
    Tree* root=new Tree;
    CreatTree(root);
    MidTreval(root);
    return 0;
}

2.(6.65)已知前序遍歷和中序遍歷录淡，求樹。

#include<bits/stdc++.h>
using namespace std;
char pre[100];
char mid[100];
int n,p;
struct Tree{
    char data;
    Tree* lchild;
    Tree* rchild;
};
Tree* CreatTree(){
    p++;
    if(p>n) return NULL;
    Tree *root=new Tree;
    root->data=pre[p];
    bool flag=0;
    for(int i=1;i<=n;i++){
        if(mid[i]=='\0') continue;
        if(pre[p]==mid[i]){
            mid[i]='\0';
            if(!flag){
                root->lchild=root->rchild=NULL;
                return root;
            }
        }
        flag=1;
    }
    root->lchild=CreatTree();
    root->rchild=CreatTree();
    return root;
}
void PostTreval(Tree *root){
    if(!root) return;
    PostTreval(root->lchild);
    PostTreval(root->rchild);
    cout<<root->data<<' ';
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>pre[i];
    for(int i=1;i<=n;i++) cin>>mid[i];
    Tree* root=CreatTree();
    PostTreval(root);
    return 0;
}

3.(6.71)按凹入表方式打印一棵用孩子-兄弟表示法儲(chǔ)存的多叉樹油坝。

#include<bits/stdc++.h>
using namespace std;
struct Tree{
    char data;
    Tree *firstchild,*nextsibling;
};
Tree* CreatTree(){//前序輸入
    Tree* root=new Tree;
    char data;
    cin>>data;
    if(data=='#') return NULL;
    root->data=data;
    root->firstchild=CreatTree();
    root->nextsibling=CreatTree();
    return root;
}
void print(Tree* root,int depth){
    if(!root) return;
    for(int i=1;i<=depth;i++) cout<<"     ";
    cout<<root->data<<endl;
    print(root->firstchild,depth+1);
    print(root->nextsibling,depth);
}
int main(){
    Tree* root=CreatTree();
    print(root,0);
    return 0;
}