登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

银河里的星星

落在人间

 
 
 

日志

 
 

打印二叉树  

2008-03-24 11:07:29|  分类: 算法与acm |  标签: |举报 |字号 订阅

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

}
  评论这张
 
阅读(2570)| 评论(0)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018