二叉樹的遍歷

下面的程序分別實現了二叉樹的前序中序後序和層次遍歷！

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
struct LNode{
    char data;
    LNode *lchild;
    LNode *rchild;
};
#define N 1000
void inorder(LNode *root){
    if(root){
        inorder(root->lchild);
        cout<<root->data<<" ";
        inorder(root->rchild);
    }
}
void preorder(LNode *root){
    if(root){
        cout<<root->data<<" ";
        preorder(root->lchild);
        preorder(root->rchild);
    }
}
void postorder(LNode *root){
    if(root){
        postorder(root->lchild);
        postorder(root->rchild);
        cout<<root->data<<" ";
    }
}
void leverorder(LNode *root){
    queue<LNode *> my_queue;
    my_queue.push(root);
    while(!my_queue.empty()){
        LNode *p=my_queue.front();
        my_queue.pop();
        cout<<p->data<<" ";
        if(p->lchild!=NULL)
            my_queue.push(p->lchild);
        if(p->rchild!=NULL)
            my_queue.push(p->rchild);
    }
}
int main(){
    char ldate[N];
    cin>>ldate;
    char flag[N];
    int i;
    flag[0]='0';
    char ch='A';
    for(i=1;i<strlen(ldate);i+=2){
        flag[i]=flag[i+1]=ch;
        ++ch;
    }
    flag[i-1]='\0';
    i=0;
    LNode *tree[N];
    while(i<strlen(flag)){
        tree[i]=new LNode();
        tree[i]->data=ldate[i];
        tree[i]->lchild=NULL;
        tree[i]->rchild=NULL;
        i++;
    }
      
    LNode *root=new LNode;
    for(i=0;i<strlen(flag);++i){
        if(flag[i]=='0'){
            root=tree[i];
            continue;
        }
          
        int j;
        for(j=0;j<strlen(ldate);++j){
            if(tree[j]->data==flag[i]){
                if(tree[j]->lchild==NULL)
                    tree[j]->lchild=tree[i];
                else
                    if(tree[j]->rchild==NULL)
                        tree[j]->rchild=tree[i];
            }
        }
    }
    LNode *p=root;
    inorder(p);
    cout<<endl;
    p=root;
    preorder(p);
    cout<<endl;
    p=root;
    postorder(p);
    cout<<endl;
    p=root;
    leverorder(p);
    cout<<endl;
    return 0;
}

本文出自 “菜鳥的進階之路” 博客，請務必保留此出處http://beyond316.blog.51cto.com/7367775/1266347