ÒøºÓÀïµÄÐÇÐÇ

Ê×Ïȸù¾ÝÇ°ÐòºÍÖÐÐò¹¹ÔìÒ»¿Ã¶þ²æÊ÷£¬È»ºóÀûÓÃÖÐÐò±éÀúºÍ¹ã¶ÈÓÅÏȽ«Ê÷°´ÕÕÐÎ×´´òÓ¡³öÀ´¡£
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX 1000
/*
print the tree
first:using the preorder and inoder,create a tree
then print it using bst and preorder
*/
int i=1; //±ê¼ÇÖÐÐòÖеÄ˳Ðò
//¶ÓÁеļòµ¥ÊµÏÖ
struct node * queue[MAX];//¶ÓÁÐ ,δ¿¼ÂÇÒç³ö
int head = 0;
int tail = 0;
struct node * dequeue(){
    struct node * temp = queue[head];
    head++;
    head %= MAX;
    return temp;

}
void enqueue(struct node * n){
    queue[tail] = n;
    tail++;
    tail %= MAX;
}
int isempty(){
    return (head == tail);
}

//Ê÷µÄʵÏÖ
struct node {
    int key;
    int level; //±íʾ¸Ã½Úµã´òÓ¡³öÀ´ºó¾àÀë×î×ó²àµÄ¾àÀë
    struct node * left;
    struct node * right;
}*root;
struct node * newNode(){
    struct node * temp= (struct node *)malloc(sizeof(struct node));
    memset(temp,0,sizeof(*temp));
    return temp;
}
//¸ù¾ÝÇ°Ðò¼°ÖÐÐòÐòÁУ¬¹¹ÔìÊ÷£¬size±íʾÊ÷ÖÐ×ܽڵãÊý
struct node * creatTree(char * inorder,char * preorder,int size){
    char * pos = inorder;
    struct node * root = newNode();
    int leftsize;
    if(size < 1){
        return NULL;
    }
    root -> key = *preorder;
    while(*pos != '\0' && *pos != *preorder)
        pos++;
    leftsize = pos - inorder;
    root -> left = creatTree(inorder,preorder+1,leftsize);
    root -> right = creatTree(pos+1,preorder+leftsize+1,size-1-leftsize);
    return root;
}
//ÖÐÐò±éÀú£¬²¢½«½Úµãlevel¼ÆËã
void inOrder(struct node * root){
    if(root == NULL)
        return ;
    inOrder(root -> left);
    root -> level = i;
    i++;
    printf("%d ",root -> level);
    inOrder(root -> right);

}
//bfs
void bfs(struct node * root){
    struct node * last;
    struct node * curr;
    struct node * prev;
    int distance = 0;//ÉÏÒ»¸ö½Úµã¾àÀë×î×ó²àµÄ¾àÀë
    last = root;
    enqueue(root);
    while(!isempty()){
        curr = dequeue();
        printf("%*c",curr->level - distance,curr -> key);
        distance = curr -> level;
        if(curr -> left != NULL){
            prev = curr -> left;
            enqueue(prev);
        }
        if(curr -> right != NULL){
            prev = curr -> right;
            enqueue(prev);
        }
        if(curr == last){
            printf("\n");
            last = prev;
            distance = 0;
        }

    }
}

int main(){
    char * inorder="123456";
    char * preorder="321456";
    root = creatTree(inorder,preorder,6);
    printf("inOrder:\n");
    inOrder(root);
    printf("\nBFS:\n");
    bfs(root);
    return 0;

}