c++ - 为每个节点分配深度

Question

我在这里阅读了其他几篇看起来相似的文章，但没有完全回答我的问题。我得到了一个分配问题，为二叉树中的每个节点分配其各自的深度。我就是不太明白。

作为引用，这是我的代码:

struct treeNode {
   int item;
   int depth;
   treeNode *left;
   treeNode *right;
};
typedef treeNode *Tree;

int assignDepth(Tree &T, int depth)
{
    if(T!=NULL)
    {
        depth = assignDepth(T->left, depth++);
        T->depth = depth;
        depth = assignDepth(T->right, depth++);
    }
    else //leaf
        return depth--;
}

我尝试用笔和纸完成它，看起来还不错，但我显然缺乏案头检查技能。

谁能给我指明正确的方向，好吗？这是我第一次使用树，递归不是我的强项。

回答:

void treecoords(Tree &T, int depth)
{
    static int count = -1; //set to -1 so the precrement before assignment doesn't give the wrong values
    if(T!=NULL)
    {
        treecoords(T->left, depth+1); //depth decrements automatically once this function call is removed from the stack
        count++;
        T->x = count;
          T->y = depth;
        treecoords(T->right, depth+1);
    } 
}

Answer 1

你不需要

else //leaf
    return depth--;

您也不想增加深度变量，只需将深度+1 传递给下一个交互。

也不需要返回值。

试试这个:

void assignDepth(Tree T, int depth)
{
    if(T!=NULL)
    {
        assignDepth(T->left, depth+1);
        T->depth = depth;
        assignDepth(T->right, depth+1);
    }
}