二叉树搜索未返回预期值

Question

如果我有一个结构：

struct node{
  int key_value;
  node * p_left;
  node * p_right;
};

还有一个添加函数：

node* add(node * p_tree, int key) {
  //--The base case of the recursive function will be placed in here
  //--since binary trees are recursive in nature and linked data structures
  //--are as a whole in terms of space and memory, the recursive function will
  //--suffice for most cases involving binary trees.
  //--In this case, if the given parameter is null, we create the tree
  //--by allocating the necessary memory space
  if (p_tree == NULL) {
    node * pnew_tree = new node;
    pnew_tree->p_left = NULL;
    pnew_tree->p_right = NULL;
    pnew_tree->key_value = key;
    cout << "Added node: " << pnew_tree->key_value << endl;
    return pnew_tree;
  }// end of base case

  //--Depending of the value of the node, we determine if we will add to the left side or the right side of the subtree
  if (key < p_tree->key_value){
    // if it is less than the value, we add to the left
    p_tree->p_left = add(p_tree->p_left, key);
  }
  else{
    p_tree->p_right = add(p_tree->p_right, key);
  }
  return p_tree;
} // end of function

还有搜索功能：

node* search(node *p_tree, int key) {
  //--First:
  if (p_tree != NULL) { 
    if(key == p_tree->key_value){
      cout << "Node found" << endl;
      return p_tree;
    }
    if(key < p_tree->key_value){
      return search(p_tree->p_left, key);
    }
    else{
      return search(p_tree->p_right, key);
    }
  }
    else{
      return NULL;
    }


}//--End of recursive search function

为什么当我运行:

 add(myBinaryTree,1);
 cout << "Testing to see if it is there" << endl;
 if (search(myBinaryTree,1) == NULL {
   cout << "Node not found" << endl;
 }

输出是 "Node not found" 而不是 "Node found" ？据我所知，添加函数不会 return NULL，为什么会这样？我曾尝试研究类似的问题，但无法充分理解其中的代码以提出我自己的解决方案，我也不精通使用 IDE(codeblocks) 进行调试，因此不知道该去哪里. （我只需要一个合乎逻辑的修复，因为我自己似乎找不到）

Answer 1

函数add return是一个指向二叉树根的指针。通常这只是与函数参数 p_tree 相同的指针，因为二叉树的根永远不会改变。

但在空树 (p_tree == NULL) 的情况下，add 将 return 指向新创建的树根的指针。所以你必须更新你的变量myBinaryTree。执行后

node* myBinaryTree = NULL;
add(myBinaryTree,1);

变量 myBinaryTree 的值仍然是 NULL。您尚未将其更新到树的根目录。以下代码有效：

node* myBinaryTree = NULL;
myBinaryTree = add(myBinaryTree,1);
cout << "Testing to see if it is there" << endl;
if (search(myBinaryTree,1) == NULL) {
    cout << "Node not found" << endl;
}

二叉树搜索未返回预期值

Binary Tree Search not returning the expected value

c++

binary-tree

binary-search

binary-search-tree