怎样从顶部开始逐层打印二叉树结点数据？(使用队列)

环境:g++ (队列类使用 c++ 更方便)

 

queue.h

 

#ifndef _H_QUEUE_
#define _H_QUEUE_
 
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
 
struct student {
        int value;
        struct student *lchild;
        struct student *rchild;
};
 
class Queue {
public:
        Queue(int size = 10):size_(size){
                head_ = new (struct student*)[size_];
                num_ = 0;
        }
        ~Queue() {
                delete[] head_;
        }
        bool empty() {
                return num_>0?false:true;
        }
        struct student* dequeue() {
                if(num_ > 0) {
                        struct student *p = head_[0];
                        for(int i=0; i<num_-1; i++) {
                                head_[i] = head_[i+1];
                        }
                        num_--;
                        return p;
                } else {
                        return NULL;
                }
        }
        void enqueue(struct student* p) {
                if(num_ >= size_) {
                        size_ *= 2;
                        struct student **new_head = new (struct student*)[size_];
                        memcpy(*new_head, *head_, 4*num_);
                        delete[] head_;
                        head_ = new_head;
                        printf("space auto extends from %d to %d\n", size_/2, size_);
                }
                head_[num_] = p;
                num_++;
        }
private:
        struct student **head_;
        int num_;
        int size_;
};
 
 
#endif

 

layerordertree.c

 

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
 
#include "queue.h"
 
 
void arraytotree(int *a, int len, struct student **p) {
        if(len) {
                *p = (struct student*)malloc(sizeof(struct student));
                (*p)->value = a[len/2];
                arraytotree(a, len/2, &((*p)->lchild));
                arraytotree(a+len/2+1, len-len/2-1, &((*p)->rchild));
        } else {
                *p = NULL;
        }
}
 
void display_tree(struct student *head) {
        if(head->lchild)display_tree(head->lchild);
        printf("%d\t", head->value);
        if(head->rchild)display_tree(head->rchild);
}
 
 
void display_tree_layer(struct student *head) {
        Queue *queue = new Queue;
        printf("%d\t", head->value);
        if(head->lchild)queue->enqueue(head->lchild);
        if(head->rchild)queue->enqueue(head->rchild);
        while(!queue->empty()) {
                struct student *p = queue->dequeue();
                printf("%d\t", p->value);
                if(p->lchild)queue->enqueue(p->lchild);
                if(p->rchild)queue->enqueue(p->rchild);
        }
}
 
 
int main() {
 
        int a[] = {1,2,3,4,5,6,7,8,9,10};
        struct student *tree;
        arraytotree(a, sizeof(a)/sizeof(a[0]), &tree);
        printf("After convert:\n");
        display_tree(tree);
        printf("\nlay order :\n");
        display_tree_layer(tree);
        printf("\n");
        return 0;
 
}