一道关于二叉树的题目解决方案

一道关于二叉树的题目
Description
在二叉树类BinaryTree中增加一个功能：实现层次遍历。

Input(levelOrder.in)
第一行一个正整数n(1<=n<=100000),表示树上结点的个数。
第二行到第n+1行每行3个正整数l,r,value,第i行表示第i-1个结点的左儿子是l号结点(0表示没有左儿子)，右儿子是r号结点（0表示没有右儿子），第i-1号结点的值是value(0<=value<=100000).

Output(levelOrder.out)
输出仅一行，表示这个二叉树的层次遍历。

Sample Input

Example 1：
7
2 3 1
4 5 3
0 6 7
0 0 5
0 0 9
7 0 6
0 0 10

Example 2：
6
0 2 1
0 3 9
0 4 100
5 0 4
6 0 2
0 0 9

Sample Output

Example 1：
1 3 7 5 9 6 10

Example 2:
1 9 100 4 2 9


[解决办法]
从第二行开始，只看前2位数字，第一个2，则输出2+1行的value，第二个是3输出第4行的value，然后是4输出第5行的value，遇到0则不输出
[解决办法]
用队列的数据结构就可以了，我几天前写过，发了另一贴上。现在我挖出来给你贴贴，我用C写的，自己看按层次遍历那个函数应该可以明白的。

C/C++ code

//第16题：题目：输入一颗二元查找树，把它按层次遍历//这道题我是很有感触的，记得一个月前我去面试莱科，就出过这道题，当时硬是不会//一个月过去了，现在我可以一下就ko它，进步蛮快的（代码真的是要多写才行）//算法思想：从队头中取结点，遍历该结点，如果它的孩子非空，把孩子加到队尾//如此重复，直到队头等于队尾#include<stdio.h>#include<malloc.h>//定义二叉树结点结构struct node{    int data;    struct node *left;    struct node *right;};typedef struct node treenode;    //二叉树结点，作辅助暂存typedef struct node * ptreenode;    //二叉树//往root为根的二叉树加入新的结点ptreenode addtreenode(ptreenode root,int e){    int flag;    ptreenode current,newnode,frontcurrent;    newnode=(ptreenode)malloc(sizeof(treenode));    if(newnode==NULL)        return NULL;    else    {        newnode->data=e;        newnode->left=newnode->right=NULL;    }    current=root;    if(current==NULL)        return newnode;    else    {        while(current!=NULL)        {            frontcurrent=current;            if(newnode->data>=current->data)            {    current=current->right;                flag=1;            }            else            {    flag=0;                current=current->left;            }        }        if(flag==1)            frontcurrent->right=newnode;        else            frontcurrent->left=newnode;    }    return root;}//树的广度优先搜索void bfstree(ptreenode root){    ptreenode p[10];//开一数组并且在逻辑上认为是队列    int f,r;    //维护两个指针，一个指向其队头，一个指向其队尾    f=r=0;    //队列空时，两指针相等    if(root==NULL)        return;    p[r++]=root;//把第一个根结点入队    while(f<r)//队列非空时表明遍历没结束    {        printf("%d ",p[f]->data);    //遍历该结点        if(p[f]->left!=NULL)    //如果存在孩子就把它入队            p[r++]=p[f]->left;        if(p[f]->right!=NULL)            p[r++]=p[f]->right;        f++;    }}void main(){    while(1){    ptreenode treeroot=NULL;    int k;    do{        scanf("%d",&k);        treeroot=addtreenode(treeroot,k);//把新输入的结点加到原来树中，结点0时结束    }while(k!=0);    bfstree(treeroot);    }}
[解决办法]
C/C++ code
#include <iostream>using namespace std;const int MAXN = 1001;int main(){    int left[MAXN], right[MAXN], value[MAXN], qu[MAXN];    int n, l, r, v;    int qu_b, qu_e;    int i, k;        while (cin >> n && n != 0)     {        for (i = 1; i <= n; i++)        {            cin >> l >> r >> v;            left[i] = l;            right[i] = r;            value[i] = v;        }                qu_b = 0;        qu_e = 0;        qu[qu_e] = 1;        qu_e++;        while (qu_b != qu_e)        {            k = qu[qu_b++];            cout << value[k] << " ";            if (left[k])                qu[qu_e++] = left[k];            if (right[k])                qu[qu_e++] = right[k];        }        cout << endl;    }        return 0;}
[解决办法] 
 
一个特点就是树的节点就位于存储后的坐标处。
[解决办法]

探讨

C/C++ code

#include <iostream>

using namespace std;

const int MAXN = 1001;

int main()
{
    int left[MAXN], right[MAXN], value[MAXN], qu[MAXN];
    int n, l, r, v;
    int qu_b, qu_e;
……

[解决办法]
想了想，可以用parent数组，
读入时这样，
  
C/C++ code
for (i = 1; i <= n; i++)        {            cin >> l >> r >> v;            left[i] = l;            right[i] = r;            value[i] = v;            parent[l]=parent[r]=i            parent[i]=-1;        }