|
1.题目：
 Problem Description
设有一棵二叉树，其节点值为字符型并假设各值互不相等，采用二叉链表存储表示。现输入其扩展二叉树的前序遍历序列，要求建立该二叉树，并对其进行层序遍历。
Input
第一行为一个整数n，表示以下有n组数据，每组数据占一行，为扩展二叉树的前序遍历序列。
Output
输出该二叉树的层序遍历序列，空二叉树则不输出任何信息。
Sample Input
Sample Output
2.代码：
#include <iostream>
using namespace std;
const int MaxSize = 100; ///定义输入字符串的最大长度
///二叉树结点的定义及声明
struct BiNode {
char data; ///数据域
BiNode* lchild, *rchild; ///指针域，左右孩子
};
class BiTree
{
private:
BiNode* root; ///定义根节点
BiNode* Creat(); ///构造函数调用
void Release(BiNode* root); ///析构函数调用
public:
BiTree(); ///构造函数，建立一颗二叉树
~BiTree(); ///析构函数，释放二叉树个结点的存储空间
BiNode* Getroot(); ///获得根节点
void levord(BiNode* root); ///广搜，然后是层序遍历
};
BiTree::BiTree()
{
root = Creat();
}
BiTree::~BiTree()
{
Release(root);
}
BiNode* BiTree::Getroot()
{
return root; ///获得根节点
}
BiNode* BiTree::Creat()
{
char ch;
cin >> ch; ///从键盘上接收前序序列
BiNode* root; ///根节点的定义
if (ch == '#')
root = NULL; ///如果跟结点为#，表示空的二叉树
else {
root = new BiNode; ///生成一个节点，
root->data = ch; ///该结点的数据域为ch
root->lchild = Creat(); ///递归建立左子树
root->rchild = Creat(); ///递归建立右子树
}
return root; ///每建立一个节点，都返回根节点
}
void BiTree::Release(BiNode* root)
{
if (root) { ///如果根节点不为空
Release(root->lchild); ///释放左子树
Release(root->rchild); ///释放右子树
delete root; ///释放根节点
}
}
void BiTree::levord(BiNode* root)
{
int front = 0, rear = 0; ///采用顺序队列，并假定不会发生上溢
BiNode* Q[MaxSize]; ///定义队列数组
BiNode* q; ///定义临时结点，作用是记录下要处理的结点
if (root == NULL) ///判断结点是否为空
return ;
else {
Q[rear++] = root; ///根节点入队
while (front != rear) { ///头指针和尾指针不相等的话，队列才不为空
q = Q[front++]; ///临时结点标记当前要处理的结点，++是指处理外后，出队
cout << q->data; ///输入当前节点的数据
if (q->lchild) ///如果q的左孩子存在的话，
Q[rear++] = q->lchild; ///左孩子入队
if (q->rchild) ///如果q的右孩子存在的话，
Q[rear++] = q->rchild; ///右孩子入队
}
}
cout << endl;
}
int main()
{
int n;
cin >> n;
while (n--) {
BiTree bt; ///按扩展前序序列创建一棵二叉树
BiNode* root = bt.Getroot(); ///x获得根节点
bt.levord(root); ///输出二叉树的层序遍历序列
}
return 0;
}
| 
转播
