递归查找二叉树中节点的深度

Question

我无法使用递归函数来查找二叉树中节点的深度，更具体地说是在 else 条件下：

如果树是一棵二叉搜索树，知道左子节点的值总是低于父节点的值而右子节点的值总是高于父节点，我可以添加一个 if 条件，这样如果节点 x 的值是低于根我总是 return 与 root->leftchild 反之亦然，但因为树不是二进制搜索树我必须检查左右两个连续的 return在else条件下。

看函数时，假设节点一直存在，节点x永远不是根，一开始传递的深度总是0。

int node_depth (Node x,Node root,int depth){
   if(x->parent==root){
       return depth;
   }
   else{
       return node_depth(x,root->leftchild,depth+1);
       return node_depth(x,root->rightchild,depth+1);
   }
}

如果树是二分查找：

else{
        if(x->value<root->value){
           return node_depth(x,root->leftchild,depth+1);
        }
        if(x->value>root->value){
           return node_depth(x,root->rightchild,depth+1);
        }
    }

Answer 1

您需要找到任何给定节点的最大深度 x 从根：

int node_depth(Node x, int depth){
    if (!x->parent) return depth;
    return node_depth(x->parent, depth + 1); 
}

你只要去 'up' 树，直到你发现父树不存在（意思是 x 是根，）

递归查找二叉树中节点的深度

Recursively find depth of a node in a binary tree

c

recursion

binary-tree