二叉树内部搜索问题

huangapple go评论64阅读模式
英文:

Issues with searching within a binary tree

问题

以下是您要翻译的代码部分:

tree* find_node(tree *root, unsigned int index){
    if(root==NULL){
        return NULL;
    }else if(root->value==index){
        return root;
    }else if(root->value<=index){
        find_node(root->left, index);
    }else if(root->value>index){
        find_node(root->right, index);
    }
}

void create_node_link(tree **root, int value, int index, int link_type){
    tree *new_node=malloc(sizeof(tree));
    if(new_node!=NULL){
        new_node->left=NULL;
        new_node->right=NULL;
        new_node->value=value;
    }

    tree *position=find_node(*root, index);
    if(position==NULL){
        printf("NOT FOUND");
        getch();
        return;
    }

    if(link_type==1)
        link_left(position, new_node);
    else if(link_type==2)
        link_right(position, new_node);
    viz_tree(*root);
}

希望这对您有所帮助。

英文:

I am trying to add nodes to a binary tree, by searching the node to which the new node is supposed to be linked, sometimes my function works if I keep going to the left branch only, or to the right branch, if I have added nodes to the left one then trying to add nodes to the right, my function finds the right node but return root does not get triggered and recursion continues till the root is NULL;

I am using GCC on Ubuntu, if it has anything to do with it.

Here is my code:

tree* find_node(tree *root, unsigned int index){
    if(root==NULL){
        return NULL;
    }else if(root-&gt;value==index){
        return root;

    }else if(root-&gt;value&lt;=index){
        find_node(root-&gt;left, index);
    }else if(root-&gt;value&gt;index){
        find_node(root-&gt;right, index);
    }
}

void create_node_link(tree **root, int value, int index, int link_type){
    tree *new_node=malloc(sizeof(tree));
    if(new_node!=NULL){
        new_node-&gt;left=NULL;
        new_node-&gt;right=NULL;
        new_node-&gt;value=value;
    }

    tree *position=find_node(*root, index);
    if(position==NULL){
        printf(&quot;NOT FOUND&quot;);
        getch();
        return;
    }

    if(link_type==1)
        link_left(position, new_node);
    else if(link_type==2)
        link_right(position, new_node);
    viz_tree(*root);
}

I just can't wrap my head around why return root doesn't terminate the function.

My tree is stored in the following way:

typedef struct my_tree tree; // in the header file

then in the header_name.c the struct looks like this:

struct my_tree{
unsigned int value;
tree *left;
tree *right;

};

The root is initialized the following way:

tree *root=create_node(1); //in the main program

tree *create_node(int value){ //function in header.c file
 tree* result=malloc(sizeof(tree));
  if(result!=NULL){
    result-&gt;left=NULL;
    result-&gt;right=NULL;
    result-&gt;value=value;
  }
return result;
}

答案1

得分: 1

由于递归调用的返回值从未被使用。初始调用只能返回NULLroot,但永远不会返回递归调用中的值。你应该返回这些值以在初始调用中获得该值:

tree* find_node(tree *root, unsigned int index) {
    if (root == NULL) {
        return NULL;
    } else if (root->value == index) {
        return root;
    } else if (root->value < index) {  // 永远不会相等,所以使用 < 而不是 <=
        return find_node(root->left, index);
    }
    return find_node(root->right, index);  // 不需要 if 语句
}
英文:

Because the recursice calls' return values never get used. The initial call can only return either NULL or root, but never the values in the recursive calls. You should return those to get that value in the initial call:

tree* find_node(tree *root, unsigned int index) {
    if (root == NULL) {
        return NULL;
    } else if (root-&gt;value == index) {
        return root;
    } else if (root-&gt;value &lt; index) {  // can never be equal, so &lt; over &lt;=
        return find_node(root-&gt;left, index);
    }
    return find_node(root-&gt;right, index);  // no if needed
}

huangapple
  • 本文由 发表于 2023年3月7日 04:42:06
  • 转载请务必保留本文链接:https://go.coder-hub.com/75655633.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定