题目

问题 C: DS二叉树的先序遍历及应用

时间限制: 1 Sec  内存限制: 128 MB
提交: 74  解决: 32
[提交][状态][讨论版]
题目描述

按先序遍历给出一棵二叉树，每个结点都有一个水平位置：左子结点在它左边一个单位，右子结点在右边1个单位。从左向右输出每个水平位置的所有节点的权值之和。

例如：以下二叉树有三个水平位置，从左至右的输出是7,11,3。

输入

测试数据有多组，每组测试数据输入按先序遍历输入一棵二叉树，其中-1代表空节点（一棵树的节点数量不超过 103）

当输入的二叉树是一棵空树时，结束输入。

输出

对于每组测试数据，首先输出一行"Case x:"，其中x代表这是第x个测试数据的输出，然后从左到右输出每个水平位置所有节点的权值之和

样例输入

5 7 -1 6 -1 -1 3 -1 -1
8 2 9 -1 -1 6 5 -1 -1 12 -1
-1 3 7 -1 -1 -1
-1
样例输出

Case 1:
7 11 3

Case 2:
9 7 21 15

代码块

#include <iostream>
using namespace std;

class BiTNode
{
    int data;
    BiTNode *lchild, *rchild;
    friend class BiTree;
};

class BiTree
{
    BiTNode *root;
    int *count;
    int max, min;
    void PreOrderTraverse(BiTNode *&p);
    void InOrderTraverse(BiTNode *p, int num);
public:
    BiTree();
    ~BiTree();
    int PreOrder();
    void InOrder();
    void Clear();
};

BiTree::BiTree()
{
    max = 1000;
    min = 1000;
    root = NULL;
    count = new int[2000];
    for(int i=0; i<2000; i++)
        count[i] = 0;
}

BiTree::~BiTree()
{
    delete []count;
}

int BiTree::PreOrder()
{
    PreOrderTraverse(root);
    if(root)
        return 1;
    else
        return 0;
}

void BiTree::PreOrderTraverse(BiTNode *&p)
{
    int temp;
    cin>>temp;
    if(temp!=-1)
    {
        p = new BiTNode;
        p->data = temp;
        PreOrderTraverse(p->lchild);
        PreOrderTraverse(p->rchild);
    }
    else
        p = NULL;
}

void BiTree::InOrder()
{
    InOrderTraverse(root, 1000);
    for(int i=min; i<=max; i++)
    {
        if(i!=max)
            cout<<count[i]<<' ';
        else
            cout<<count[i]<<endl;
    }
}

void BiTree::InOrderTraverse(BiTNode *p, int num)
{
    if(p)
    {
        InOrderTraverse(p->lchild, num-1);
        count[num] += p->data;
        if(num>max)
            max = num;
        if(num<min)
            min = num;
        InOrderTraverse(p->rchild, num+1);
    }
}

void BiTree::Clear()
{
    root = NULL;
    max = 1000;
    min = 1000;
    for(int i=0; i<2000; i++)
        count[i] = 0;
}

int main(void)
{
    BiTree myTree;
    int num = 1;
    while(myTree.PreOrder())
    {
        cout<<"Case "<<num<<':'<<endl;
        num++;
        myTree.InOrder();
        myTree.Clear();
        cout<<endl;
    }
    return 0;
}