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

一道关于二叉树的题目
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;
}

------解决方案--------------------

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

相关推荐