c - 查找任意树 C 中的节点

Question

我想使用函数从任意树中查找节点并返回该节点

这是我的结构:

    typedef struct binary_tree {
    int index;
    struct binary_tree * left;
    struct binary_tree * right;
} binary_tree;

我使用的函数是

binary_tree * search (binary_tree * tree, int index) {
    binary_tree * found = NULL;

    if(tree == NULL)
        return NULL;

    if(tree->index == index)
        return tree;

    found = search(tree->left, index);
    if (found) {
        return found;
    }

    found = search(tree->right, index);
    if (found) {
       return found;
    }
    return NULL;
}

但是这不起作用。

我需要修改或更正什么才能找到该节点？

或者如果您能给我其他建议，我将不胜感激!

Answer 1

通常您使用键(=您的索引)对元素进行排序并更快地找到它们。

您的代码当前搜索树中的每个元素，时间复杂度为O(n)，尽管也可以使用O(log n)。

正确的解决方案取决于您如何在树中存储元素(如何对元素排序)。以下示例期望左侧节点索引小于右侧节点索引。

binary_tree * search (binary_tree * arbore, int index) {        
    if(arbore == NULL){
        return NULL;
    }

    if(arbore->index == index){
        return arbore;
    }
    if(arbore->index < index){
        return search (arbore->left, index);
    }else{
        return search (arbore->right, index);
    }
}

如果(无论出于何种原因)您的树未排序，您需要到处搜索:

binary_tree * search (binary_tree * arbore, int index) {        
    if(arbore == NULL){
        return NULL;
    }

    if(arbore->index == index){
        return arbore;
    }
    binary_tree* result = NULL;

    result = search (arbore->left, index);
    if(result == NULL){
        result = search (arbore->right, index);
    }
    return result;
}

此外:您应该始终使用括号。忽略它们只会导致错误并且没有任何优势。