c - 某级二叉树数组

Question

我需要将二叉树的值放入数组中，但问题是，我应该只将处于特定深度的值放入数组中。它应该输出插入数组的元素数。

我做了这个:

int nivel2_(ABin a, int n, int v[], int level, int *i){
    int t;
    if(!a) return 0;

    if(n == level){
        v[(*i)++] = a->value;
        return 1;
    }else{
        t = nivel2_(a->left, n, v, level+1, i) + nivel2_(a->right, n, v, level+1, i);
    }

    return t;
}

int nivel2(ABin a, int n, int v[]){
    int k = 0;
    int *i;
    i = &k;

    return nivel2_(a, n, v, 1, i);
}

因为我会不断递归地改变索引，并且只有当我们达到我们想要的深度时，我想到了使用一个指针，这样，当递归折叠的一部分发生时，它会将值更改为所有其他折叠过程.有道理吗？

结构:

typedef struct slist
{
    int value;
    struct slist* next;
} *SList;

typedef struct arvbin* ABin;
typedef struct arvbin
{
    int value;
    ABin right;
    ABin left;
} arvb;

它有效吗？

只有当我想要第一层深度的元素时!

这样调用:

 nivel2(tree2, 1, v);

完整代码

#include <stdio.h>
#include <stdlib.h>

typedef struct slist
{
    int value;
    struct slist* next;
} *SList;

typedef struct arvbin* ABin;
typedef struct arvbin
{
    int value;
    ABin right;
    ABin left;
} arvb;


int nivel2_(ABin a, int n, int v[], int level, int *i){
    int t;
    if(!a) return 0;

    if(n == level){
        v[(*i)++] = a->value;
        return 1;
    }else{
        t = nivel2_(a->left, n, v, level+1, i) + nivel2_(a->right, n, v, level+1, i);
    }

    return t;
}

int nivel2(ABin a, int n, int v[]){
    int k = 0;
    int *i;
    i = &k;

    return nivel2_(a, n, v, 1, i);
}

void insertTree(ABin *tree, int val){
    if((*tree)==NULL){
        *tree = (ABin) malloc(sizeof(arvb));
        (*tree)->value = val;
        (*tree)->left = NULL;
        (*tree)->right = NULL;
        return;
    }
    else if(val > (*tree)->value)
    {
        insertTree(&((*tree)->right), val);
    }
    else if(val <= (*tree)->value)
    {
        insertTree(&((*tree)->left), val);
    }
    return;
}

int main(){

    int v[10] = {0};

    ABin tree2 = NULL;
    insertTree(&tree2, 22);
    insertTree(&tree2, 1);
    insertTree(&tree2, 3);

    nivel2(tree2, 1, v);

    int i;    
    for(i=0; i<5; i++){
        printf("%d\n", v[i]);
    }

    return 0;

}

Answer 1

代码在我看来基本没问题。这是一个稍微修改过的版本，主要是添加了树打印功能、一些诊断和扩展树。我怀疑您希望您的树只有 2 层，但实际上有 3 层。

代码

#include <stdio.h>
#include <stdlib.h>

typedef struct slist
{
    int value;
    struct slist* next;
} *SList;

typedef struct arvbin* ABin;
typedef struct arvbin
{
    int value;
    ABin right;
    ABin left;
} arvb;

static int nivel2_(ABin a, int n, int v[], int level, int *i)
{
    int t = 0;
    if (a)
    {
        if (n == level)
        {
            v[(*i)++] = a->value;
            t = 1;
        }
        else
        {
            t += nivel2_(a->left, n, v, level + 1, i);
            t += nivel2_(a->right, n, v, level + 1, i);
        }
    }

    return t;
}

static int nivel2(ABin a, int n, int v[])
{
    int k = 0;
    int r = nivel2_(a, n, v, 1, &k);
    printf("r = %d; k = %d\n", r, k);
    return k;
}

static
void insertTree(ABin *tree, int val)
{
    if ((*tree) == NULL)
    {
        *tree = (ABin) malloc(sizeof(arvb));
        (*tree)->value = val;
        (*tree)->left = NULL;
        (*tree)->right = NULL;
        return;
    }
    else if (val > (*tree)->value)
    {
        insertTree(&((*tree)->right), val);
    }
    else if (val <= (*tree)->value)
    {
        insertTree(&((*tree)->left), val);
    }
}

static void tree_to_array(ABin tree, int level)
{
    int v[10] = { 0 };
    int n = nivel2(tree, level, v);
    printf("Converted level %d to array:", level);
    for (int i = 0; i < n; i++)
        printf(" %d", v[i]);
    putchar('\n');
}

static void print_tree(ABin tree, int level)
{
    if (tree != 0)
    {
        printf("Level %d: %d\n", level, tree->value);
        print_tree(tree->left, level + 1);
        print_tree(tree->right, level + 1);
    }
}

int main(void)
{
    ABin tree2 = NULL;
    insertTree(&tree2, 22);
    insertTree(&tree2, 10);
    insertTree(&tree2, 13);
    insertTree(&tree2, 33);
    insertTree(&tree2, 39);
    insertTree(&tree2, 43);
    insertTree(&tree2, 19);

    print_tree(tree2, 1);

    for (int level = 1; level < 5; level++)
        tree_to_array(tree2, level);

    return 0;
}

示例输出

Level 1: 22
Level 2: 10
Level 3: 13
Level 4: 19
Level 2: 33
Level 3: 39
Level 4: 43
r = 1; k = 1
Converted level 1 to array: 22
r = 2; k = 2
Converted level 2 to array: 10 33
r = 2; k = 2
Converted level 3 to array: 13 39
r = 2; k = 2
Converted level 4 to array: 19 43

打印的树形在我看来是正确的。