CSU层次遍历实验报告.doc

姓名: 学号: 班级:
题目描述: 。
为上面的树建立二叉链表,然后层次遍历,显示结果,要求用到循环队列。
思路: 建立二叉链表,用循环队列存储数据,遵顿循环队列的先进先出的特点,设置长度为n-1=4空队,将根节点v0入队,此时队列不空,打印v0;把v0的左儿子v3入队,然后v0的右儿子v1入队,此时,v3为队列头,v1为队尾,列队列不空,v3出队;v3的左儿子v4入队,然后v3的左儿子v2入队,此时队列头是v1,队列尾是v2,队列不空,v1出队;v1是叶子结点,没有新元素入队,v4为队列头,v2为队列尾,队列不空,v4出队,以此类推,完成储存与遍历。
详细演示层次遍历过程:找到根V0,打印V0;找到V0的左儿子v3,打印v3;找到v0,找到v0的右儿子v1,打印v1:找到v0,找到V0的左儿子v3,找到v3的左儿子v4,打印v4;找到v3,找到v3的右儿子v2,打印v2。
程序代码如下:
#include <iostream>
using namespace std;
const int INITSIZE = 4; //这个数是总节点数减一
class Node{
public:
char* data;
Node* left;
Node* right;
Node(char* data){
this->data = data;
left = NULL;
right = NULL;
}
};
Node* constructTree(){
Node* root = new Node("V0");
root->left = new Node("V3");
root->right = new Node("V1");
root->left->left = new Node("V4");
root->left->right = new Node("V2");
return root;
}
Node* q[1000];
Node* p;
int level(Node* T){
int f,r;
f=0; r=0; /*置空队*/
q[r]=T; r++; /*根结点进队*/
while(f != r%INIT