MOOC 03_02 List Leaves
队列直接使用的是讲义中的。
本题采用结构数组存放树节点相关信息。
可参考
读取相关的数据进入节点,最后根据队列层序遍历即可从上到下,从左到右得到叶节点的输出。
关键是通过队列这一数据结构实现,根节点入队,,出队时其左右儿子入队。
#include <iostream>
using namespace std;
const int MAXSIZE = 10;
const int QUEUE_INIT_SIZE = 100;
const int ERROR = 0;
const int OK = 1;
const int EMPTY = 1;
typedef int Status;
template <class T>
class SqQueue
{
public:
SqQueue();
~SqQueue();
Status EnQueue(T e);
Status DeQueue(T &e);
Status IsEmpty();
private:
T * base; //内存空间首地址
T *front; //头指针
T *rear; //尾指针
int queueSize; //队列的长度
};
//初始化顺序队列
template <class T>
SqQueue<T>::SqQueue()
{
base = new T[QUEUE_INIT_SIZE];
if (!base)
{
cerr << "存储分配失败!" << endl;
}
front = rear = base; //注意此处的赋值顺序,将base赋值给front和rear
queueSize = QUEUE_INIT_SIZE;
}
template <class T>
SqQueue<T>::~SqQueue()
{
T *p = front;
while (p != rear)
{
p++;
delete front;
front = p;
}
}
//顺序入队
template <class T>
Status SqQueue<T>::EnQueue(T e)
{
if (rear - base >= queueSize)
{
return ERROR;
}
*rear++ = e; //先赋值,再加指针
return OK;
}
//顺序队列出队
template <class T>
Status SqQueue<T>::DeQueue(T &e)
{
if (rear == front)
{
return ERROR;
}
e = *front++; //先减指针,再取值
return OK;
}
template <class T>
Status SqQueue<T>::IsEmpty()
{
if (front == rear)
{
return EMPTY;
}
else
{
return !EMPTY;
}
}
struct TreeNode
{
int data;
int left;
int right;
};
struct TreeNode T[MAXSIZE];
//建树,返回根节点的值
int BuildTree(struct TreeNode T[])
{
char cl, cr;
int check[MAXSIZE];
int Root = -1;
int i = 0;
int N;
cin >> N;
if (N)
{
for (i = 0; i<N; i++)
{
check[i] = 0; //寻找根节点,此时为0,有指向其的节点则改为1
}
for (i = 0; i<N; i++)
{
T[i].data = i;
cin >> cl >> cr;
if (cl != '-')
{
T[i].left = cl - '0'; //字符转数字
check[T[i].left] = 1;
}
else
{
T[i].left = -1;
}
if (cr != '-')
{
T[i].right = cr - '0';
check[T[i].right] = 1;
}
else
{
T[i].right = -1; //置为-1,表示空
}
}
for (i = 0; i<N; i++)
{
if (check[i] == 0)
{
break;
}
}
Root = i;
return Root;
}
}
int main()
{
int R1 = BuildTree(T); //根节点
SqQueue<TreeNode> Q;
Q.EnQueue(T[R1]); //根节点进队
bool flag = true;
while (!Q.IsEmpty())
{
TreeNode temp;
Q.DeQueue(temp);
if (temp.left != -1)
{
Q.EnQueue(T[temp.left]);
}
if (temp.right != -1)
{
Q.EnQueue(T[temp.right]);
}
if (temp.left == -1 && temp.right == -1 && flag)
{
cout << temp.data;
flag = false;
}
else if (temp.left == -1 && temp.right == -1)
{
cout << " " << temp.data;
}
}
return 0;
}