hihocoder 1342 Full Binary Tree Picture【完全二叉树】

转自http://www.jianshu.com/p/e37495f72cf6

解释：
题目描述了一种用ASCII码绘制的满二叉树，然后将树的根设置在一个特殊坐标轴的原点（0，0），坐标轴x向下为正向，y向右是正向。树的每个树枝与节点都占用1*1的大小。现在需要求在坐标轴中任意画一个矩形，里面会有多少个树的节点。例如样例输入中，对于（0，0）与（2，2）形成的矩形里面，包含有根节点和它的右叶子节点，所以输出的是2。

分析：
1、这是是一个二叉树的问题，肯定要构造树结构，为了简单，这里就声明一个Node的结构体，通过结构体指针来构建树。代码如下：

struct Node {

    Node *lchild, *rchild;

    long px, py;

    Node(long _px, long _py)

    {

        lchild = rchild = NULL;

        px = _px;

        py = _py;

    }

};

px，py是节点的坐标，lchild与rchild分别对应左右子节点。

2、接下里就是生成树，这里输入就是树的高度，我们就根据高度来生成满二叉树。生成的时候根据题目规则，我们需要注意树的树枝占位情况。通过分析我们可以得出，高度为1的节点，它一边的树枝数量是0，高度2的为1，高度3的为2，其它高度的节点树枝数量是其子节点数量的2倍加1。这样我们可以用个递归实现。代码如下：

long stickNumWithHeight(int height)

{

    if (height == 1) {

        return 0;

    }

    if (height == 2) {

        return 1;

    }

    if (height == 3) {

        return 2;

    }

    return stickNumWithHeight(height - 1) * 2 + 1;

}

void buildTreeWithHeight(Node &node, int height)

{

    if (height == 1) {

        return;

    }

    long step = stickNumWithHeight(height) + 1;

    node.lchild = new Node(node.px + step, node.py - step);

    node.rchild = new Node(node.px + step, node.py + step);

    buildTreeWithHeight(*node.lchild, height-1);

    buildTreeWithHeight(*node.rchild, height-1);

}

3、树生成过后，我们只需要对每个矩形遍历检测这棵树，就可得到在当前矩形中节点数量，代码如下：

int checkNodeInArea(Node &node, int x1, int y1, int x2, int y2)

{

    int sum = 0;

    if (node.px >= x1 && node.py >= y1 && node.px <= x2 && node.py<= y2) {

        sum += 1;

    }

    if (node.lchild != NULL) {

        sum += checkNodeInArea(*node.lchild,x1,y1,x2,y2);

    }

    if (node.rchild != NULL) {

        sum += checkNodeInArea(*node.rchild,x1,y1,x2,y2);

    }

    return sum;

}

完整代码：

#include <iostream>

#include <algorithm>

#include <map>

#include <string>

#include <string.h>

#include <ctype.h>

#include <vector>

using namespace std;

struct Node

{

    Node *lchild,*rchild;

    long px,py;

    Node(long _px,long _py)

    {

        lchild = rchild = NULL;

        px=_px;

        py=_py;

    }

};

long stickNumWithHeight(int height)

{

    if (height == 1) {

        return 0;

    }

    if (height == 2) {

        return 1;

    }

    if (height == 3) {

        return 2;

    }

    return stickNumWithHeight(height - 1) * 2 + 1;

}

void buildTreeWithHeight(Node &node,int height)

{

    if(height==1)return;

    long step = stickNumWithHeight(height)+1;

    node.lchild = new Node(node.px+step,node.py-step);

    node.rchild = new Node(node.px+step,node.py+step);

    buildTreeWithHeight(*node.lchild,height-1);

    buildTreeWithHeight(*node.rchild,height-1);

}

int checkNodeInArea(Node &node, int x1, int y1, int x2, int y2)

{

    int sum = 0;

    if (node.px >= x1 && node.py >= y1 && node.px <= x2 && node.py<= y2) {

        sum += 1;

    }

    if (node.lchild != NULL) {

        sum += checkNodeInArea(*node.lchild,x1,y1,x2,y2);

    }

    if (node.rchild != NULL) {

        sum += checkNodeInArea(*node.rchild,x1,y1,x2,y2);

    }

    return sum;

}

int main(){

   int N,M;

    scanf("%d%d",&N,&M);

    Node *root= new Node(0,0);

    buildTreeWithHeight(*root,N);

    while(M--)

    {

        int x1,x2,y1,y2;

        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);

        int amout = checkNodeInArea(*root,x1,y1,x2,y2);

        cout<<amout<<endl;

    }

    return 0;

}

巴特西

hihocoder 1342 Full Binary Tree Picture【完全二叉树】

最新文章

热门文章