The Falling Leaves 简单的遍历+建树

大意：给你一棵树，让你求竖直位置相同的节点的和

和一般的建树 + 遍历没什么不同的，不过需要在树的结构体里面加一个 pos 记录节点位置，再用一个数字储存节点的和

#include<cstdio>
#include<cstring>
#include<iostream>
#include<malloc.h>
using namespace std;
#define MAX_SIZE 100000
#define Base 10000
int counts[MAX_SIZE];
int visa  [MAX_SIZE];
struct Tree
{
    int value;
    int pos;
    Tree *Left;
    Tree *Right;
};
Tree *BuildTree(int pos){ /*构建一棵树*/
    int valued;
    Tree *node = (Tree*)malloc(sizeof(Tree));
    scanf("%d",&valued);
    if(valued == -1){
        node = NULL;
        return node;
    }
    else {
        node -> value = valued;
        node -> pos = pos;
        node -> Left =  BuildTree(pos - 1);
        node -> Right = BuildTree(pos + 1);
        return node;
    }
}
void dfs(Tree *node){
    if(node == NULL)
        return ;
    else {
        int p = node -> pos;
        counts[Base + p] += node -> value;
        visa[Base + p] = 1; /*记录是否被访问过*/
        dfs(node -> Left);
        dfs(node -> Right);
        return ;
    }
}
int main()
{
    int Case = 1;
    while(true){
        Tree *root;
        memset ( counts, 0 , sizeof(counts) );
        memset ( visa, 0 , sizeof(visa) );
        root = BuildTree(0);
        if(root == NULL)  break;
        dfs(root);
        printf("Case %d:n",Case);
        for(int i = 0,k = 0 ;i < MAX_SIZE; i++ )
            if(visa[i]&&k == 0){
            k = 1;
            printf("%d",counts[i]);
            }
            else if(visa[i]){
                printf(" %d",counts[i]);
            }
        printf("nn");
        Case++;
    }
    return 0;
}

最后

以上就是顺利大山为你收集整理的The Falling Leaves 简单的遍历+建树的全部内容，希望文章能够帮你解决The Falling Leaves 简单的遍历+建树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。