为每个节点分配深度

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);
    }
}