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