二叉树，return节点的父节点

Question

我尝试编写一个函数，return 值 node.The createAB 函数的父函数可以工作，但我不知道迭代二叉树 elements.How 以递归地进行电话？请帮帮我。

 ifstream f("store.txt");//store.txt:10 7 8 0 0 0 13 9 0 11 0 0 12 0 0
    struct elem {
        int inf;
        elem* st;
        elem* dr;
    };
    //this function create the binary tree
    void createAB(elem*& p) {
        int n;
        f >> n;
        if (n!=0) {
            p = new elem;
            p->inf = n;
            createAB(p->st);
            createAB(p->dr);
        }
        else 
            p = NULL;
    }
    `

        elem* parent(elem* rad, int n) {//my function,doesn't work
        if (rad == NULL)
            return NULL;
        else
            if (rad->st->inf == n || rad->dr->inf == n) 
                return rad;//return the element
            else {
                return parent(rad->st, n);//here is a problem
                return parent(rad->dr, n);
            }
    }
      10
   7       13
 8       9    12
           11
node 12 => parent 13
node 8 => parent 7

Answer 1

在使用 rad->st->inf 和 rad->dr->inf 之前，您应该检查 rad->st 和 rad->dr 是否为 null。

Answer 2

正如 sebi519 所指出的，您需要检查 rad->st 和 rad->dr 不是 NULL。

但是正如您正确评论的那样，这里的主要问题出在 return 语句中。问题是第二行永远不会执行，因为第一行已经从函数中 returns。

return parent(rad->st, n);//This returns and the next line is not executed
return parent(rad->dr, n);

您需要保存第一次调用的结果并检查它是否成功，如果不成功则进行第二次调用：

elem* result = parent(rad->st,n);
if (result != NULL)
  return result;
else
  return parent(rad->dr,n);

完整修正函数：

elem* parent(elem* rad, int n) {
  if (rad == NULL)
    return NULL;
  else
    if ( (rad->st!=NULL && rad->st->inf == n) || (rad->dr!=NULL) && (rad->dr->inf == n)){
      return rad;//return the element
    }
    else {
      elem* result= parent(rad->st, n);
      if (result!=NULL){
        return result;
      }
      else{
        return parent(rad->dr, n);
      }
    }
}

二叉树，return节点的父节点

Binary tree,return the parent of the node

c++

tree

binary-tree