树

建树与输出

#include<iostream>  
using namespace std;  
  
typedef struct node{
    node *le;
    node *re;
    char data;
}BiTreeNode,*BiTree;  
  
void createBiTree(BiTree &T){
    char c;
    cin>>c;
    if(c=='#')
        T=NULL;
    else{
        T=new BiTreeNode;
        T->data=c;
        createBiTree(T->le);
        createBiTree(T->re);
    }
}  
void printTree(BiTree &T){
    if(T){
        
        printTree(T->le);
        printf("%c ",T->data);
        printTree(T->re);
    }
}
  
int main()  
{  
    BiTree T;  
    createBiTree(T);  
    printTree(T);
    return 0;  
}

树的遍历

已知后序遍历和中序遍历求层序遍历

#include <cstdio>  
#include <cstdlib>  
#include <queue>  
  
using namespace std;  
  
const int maxx = 32;  
  
typedef struct Tree{  
    Tree *le;  
    Tree *ri;  
    int data;  
}Tree;  
  
Tree *root;  
  
int pos[maxx],in[maxx];  

void printLevelOrder(Tree *root){  
    queue<Tree *> que;  
    Tree *tr = NULL;  
    que.push(root);  
    bool flg = true;  
    while(!que.empty()){  
        tr = (Tree *)que.front();  
        que.pop();  
        if(tr==NULL)continue;  
        if(flg){  
            printf("%d",tr->data);  
            flg = false;  
        }else{  
            printf(" %d",tr->data);  
        }  
        que.push(tr->le);  
        que.push(tr->ri);  
    }  
    printf("\n");  
}  
Tree *buildTree(int pl,int pr,int il,int ir){  
    if(pl>pr)return NULL;  
    int p = il;  
    while(in[p]!=pos[pr])++p;  
  
    Tree *tree = (Tree *)malloc(sizeof(Tree));  
    tree->data = pos[pr];  
    tree->le = buildTree(pl,pr-ir+p-1,il,p-1);  
    tree->ri = buildTree(pr-ir+p,pr-1,p+1,ir);  
      
    return tree;  
}  
  
int main(){  
    int n,i;  
    Tree *root;  
  
    scanf("%d",&n);  
    for(i=0;i<n;++i){  
        scanf("%d",&pos[i]);  
    }  
    for(i=0;i<n;++i){  
        scanf("%d",&in[i]);  
    }  
    root=buildTree(0,n-1,0,n-1);  
    printLevelOrder(root);  
    return 0;  
}