logo标签列表

为每个节点分配深度

c++recursionbinary-tree
6

我在这里看了几篇其他类似的文章，但并没有完全解决我的问题。我的作业要求我为二叉树中的每个节点分配其相应的深度。但我还是无法理解。

以下是我的代码：

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);
    } 
}
1
谢谢所有回复我的帖子的人。我现在明白自己的想法是错误的了。我会根据你们告诉我的内容去尝试修复代码，并发布最终结果。我不想仅仅使用别人的代码而不完全理解它（虽然我很感激你们为我发布了它）。 - xyzjace
它有效了！我编写了一个递归算法，最终与Mr. Cooper的算法匹配。实际上，这是一个将x和y坐标分配给树节点的更大算法的一部分。该算法现在已经包含在原始问题中。 - xyzjace
6个回答
3

你不需要

else //leaf
    return depth--;

您不需要增加深度变量，只需将depth+1传递给下一次迭代即可。此外，无需返回值。请尝试以下代码：
void assignDepth(Tree T, int depth)
{
    if(T!=NULL)
    {
        assignDepth(T->left, depth+1);
        T->depth = depth;
        assignDepth(T->right, depth+1);
    }
}
我不明白为什么，但是每个人都说要删除它，所以我就删除了。递归让我很困扰。谢谢 :) - xyzjace
思考正在发生的事情是有帮助的。在第一次调用中，深度为0（或者其他值），T是树的根节点。假设T不为空，函数将在左子树上以depth + 1为参数调用自身，将深度分配给当前（根）节点，然后再次以depth + 1为参数在右子树上调用自身。正是这个中间步骤将深度参数的值分配给了节点，因此无需将该值返回到任何地方。 - Andrew Cooper
这很有道理。我在递归中的值返回方面有点困惑。但我现在想明白了。非常感谢 :) - xyzjace
2

首先，你正在使用后缀递增/递减，可能是想要正确分配++depth/--depth，然后是else return;

另外，为什么要将指针作为引用变量传递？

我按照你的建议尝试了前增量（precrement），接近正确，但还不够完美。为什么我要使用前增量而不是后增量呢？我以为这只与运算顺序有关呢？我使用指针的引用，因为看起来是这样工作的。我们只是对指针进行了非常简要的介绍，然后就直接让我们深入研究树结构了。这基本上是一个试错的过程，一直到编译器不再给我报错为止。 - xyzjace
1

我有一个稍微复杂一些的设计，其中包含不同类型的节点，因此我这样做了，所以我想分享一下。

如果你有一个类型不同的节点树（二叉、一元等），那么值得简化传统方法，避免嵌套的IF来检查节点类型。

两个函数：

  • 1：从根开始，运行每个节点，并通过递归调用自身并为每个父节点添加1来检查其与根的距离。给每个节点一个深度变量来存储这个值。
  • 2：从树中的完整节点集合中运行MAX检查，针对每个节点的深度进行比较，最高数字将等于树的深度。

以这种方式处理可以消除显式类型检查，只需计算节点数量，无论它有一个、两个或一百个子节点。

希望这能对某人有所帮助！

1
int assignDepth(Tree &T, int depth)

你已经将 Tree 定义为指向 treeNode 的指针。你不需要通过引用传递。无论如何，你都可以修改指向的节点。
{
    if(T!=NULL)
    {
        depth = assignDepth(T->left, depth++);

后缀符号++确保您传递的是原始的depth。这不是您想要的。在此之前，递增depth，并忘记将其作为函数结果返回。
    T->depth = depth;

这是可以的。

        depth = assignDepth(T->right, depth++);

与之前的递归调用类似，不同之处在于这里你不应该修改 depth，因为它已经被增加了。
    }
  else //leaf
        return depth--;

您不需要返回任何深度信息（或者说这是一个未明示的要求吗？）。

}

祝好！

我阅读所有的评论以确保不会错过任何东西。谢谢 :) - xyzjace
1

  1. 一旦到达叶节点，您就不再关心其深度，因此返回值似乎没有任何作用。

  2. 用两个语句表示：

    depth = assignDepth(T->left, depth++);
// 和
depth = assignDepth(T->right, depth++);

您在没有中间序列点的情况下修改了depth两次，这会导致未定义的行为（尽管似乎应该有一个中间序列点，在赋值的左右两侧之间没有序列点）。

我刚刚在打字的时候意识到为什么返回值是多余的了。我感觉自己好蠢啊。谢谢 :)！不确定什么是序列点，抱歉。 - xyzjace
@user475234：我曾经在考虑是否要提及它，因为修复代码也将解决此问题。除了一些例外情况，C基本上表示您只能在给定语句中修改特定变量一次，在这种情况下，您正在执行两次（一次在增量中，一次在赋值中）。 - Jerry Coffin
1
  1. 当节点为空时，为什么要返回。根据您的规定，您不需要返回任何深度。

  2. 在其他情况下，您只需要增加深度并发送到函数调用。以下是我编写的代码版本

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

它开始变得有些清晰了。我现在意识到，当递归完成时，它不需要返回深度，因为随着它从堆栈中拉出函数调用，深度与调用函数之前的值相同。谢谢:D！ - xyzjace
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接