时间戳

首页 > 解决方案 > 查找元素在树中的级别

c - 查找元素在树中的级别

问题描述

所以我遇到了这个问题，我应该在树中找到元素的级别。似乎没有任何效果，所以我在这里寻求帮助。

这就是我到目前为止所得到的。这里的问题是第 4 个断言（返回的级别应该是 2）不起作用并且断言被警告。我想过也许尝试不递归地这样做，但那怎么能做到呢？

int findElementLevel(const BSTree tree, const int element) {

    int level = 0;

    if (tree == NULL) {
        return -1;
    }

    if (tree->data == element) {
        return level;
    }

    if (element < (tree)->data) {
        level++;
        findElementLevel(tree->left, element);
        return level;
    }

    if (element > (tree)->data) {
        level++;
        findElementLevel(tree->right, element);
        return level;
    }
}

void testNewTree(void) {

    BSTree tree = emptyTree();
    assert(isEmpty(tree));

    int arr[5] = {3,2,5,1,4}, i;

    for (i = 0; i < 5; i++)
    {
        insertSorted(&tree, arr[i]);
    }

    assert(findElementLevel(tree, 3) == 0);

    assert(findElementLevel(tree, 2) == 1);

    assert(findElementLevel(tree, 5) == 1);

    assert(findElementLevel(tree, 1) == 2);

    assert(findElementLevel(tree, 4) == 2);

}

标签： crecursiontreebinary-search-treefunction-definition

解决方案

该函数始终从设置为 0 的局部变量 level 的声明开始。

int findElementLevel(const BSTree tree, const int element) {

    int level = 0;

如果在任何实际级别中找到目标元素，则返回此值为 0（或由于在当前递归函数调用中增加而为 1）的值

if (tree->data == element) {
    return level;
}

你必须积累水平。

例如，可以通过以下方式定义递归函数

int findElementLevel(const BSTree tree, const int element) {
    if (tree == NULL) {
        return -1;
    }
    else  if ( element < tree->data ) {
        int level = findElementLevel(tree->left, element);
        return level == -1 ? level : level + 1;
    }
    else if ( tree->data < element ) {
        int level = findElementLevel(tree->right, element);
        return level == -1 ? level : level + 1;
    }
    else {
        return 0;
    } 
}

请注意，第二个参数的限定符 const 没有多大意义，因为该函数处理所提供参数的值的副本。该函数可以像这样声明

int findElementLevel(const BSTree tree, int element);

推荐阅读