您能否举一个函数（递归或非递归）的示例来查找二叉搜索树是否太高？

Question

如果二叉搜索树太高相对较快（大多数情况下），我如何使用 C 查找？

更具体地说，假设我需要查找一棵树的高度是否至少为 10，而无需搜索整棵树大部分时间.

（这是可能的，因为我希望大部分输入是高度大于 10 的二叉搜索树。）

Answer 1

如果没有关于树结构的先决条件，除了检查树的一侧，然后检查另一侧，别无他法。

int check_depth(struct tree *root, int depth)
{
    if (!root) {
        return 0;
    } else if (depth <= 1) {
        return 1;
    } else {
        return check_depth(root->left,  depth-1) ||
               check_depth(root->right, depth-1);
    }
}

Answer 2

这是一个简单算法的示例，returns true 一旦找到一个长于 10 的分支。

#include <stdbool.h>
#include <stdio.h>

typedef struct _node
{
    int data;
    struct _node *l, *r;
}
node;

node *tree; // some tree
...

bool is_too_tall(node *node, int depth, int max_depth)
{
    if (node == NULL)
        return false;
    if (depth > max_depth)
        return true;
    
    return is_too_tall(node->l, depth + 1, max_depth) 
        || is_too_tall(node->r, depth + 1, max_depth);
}

int main()
{
    if (is_too_tall(tree, 1, 10))
        puts("Tree is too tall");
}

我认为depth first search is the best option for this algorithm (as opposed to breadth first search因为它更快更简单。

您能否举一个函数（递归或非递归）的示例来查找二叉搜索树是否太高？

Could you give an example of a function (recursive or not) that finds if a binary search tree is too tall?

c

time-complexity