离奇的code

打印二叉树

2008年3月24日 阅读(42)

首先根据前序和中序构造一棵二叉树,然后利用中序遍历和广度优先将树按照形状打印出来。
#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;

}

You Might Also Like