为每个节点分配一个深度

我在这里阅读了一些其他文章，看起来很相似，但没有完全回答我的问题。我已经给出了一个分配的问题，即为二叉树中的每个节点分配相应的深度。我无法完全理解。为每个节点分配一个深度

供参考，这是我的代码：

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

来源

2010-10-14 xyzjace

谢谢大家谁回复我的帖子。我明白我现在正在考虑这一切都是错误的。我会走开，并尝试修复代码，给你告诉我并发布我的最终结果。我不想在没有完全理解的情况下使用某些代码（尽管我很欣赏你已经发布了它，谢谢）。 – xyzjace 2010-10-14 02:02:52

它的工作原理！我做了一个递归算法，最终匹配库珀先生的。它实际上是一个更大的算法的一部分，它将x和y坐标分配给树节点。该算法现在在原始问题中。 – xyzjace 2010-10-14 02:24:57

你根本不需要

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

来源

2010-10-14 01:44:11

我不明白为什么不可以，但每个人都说要删除它，所以我做到了。递归打破了我的想法。谢谢:) – xyzjace 2010-10-14 01:53:04

它有助于思考发生了什么。在第一个调用深度= 0（或其他）和T是树的根。假设T不为NULL，函数在深度为+1的左子树上调用自身，为当前（根）节点分配深度，然后在右子树上调用自身，深度为+1。这是将深度参数的值分配给节点的中间步骤，因此不需要将值返回到任何位置。 – 2010-10-14 02:01:49

这很有道理。我对递归中的值有点困惑。但我想我现在明白了。非常感谢:) – xyzjace 2010-10-14 02:05:25

嗯，首先，你使用后递增/递减，你可能是指++depth/--depth对于权的分配和其他回报;

另外，为什么传递指针作为参考变量？

来源

2010-10-14 01:42:03 cthom06

我按照你的建议尝试了这个增量，它到达那里，但不是很正确。为什么我会使用precrement而不是post？我认为只有按照操作顺序才重要？我使用指针的引用，因为这是它的工作原理。我们对指针进行了非常简短的介绍，然后投入了树木的海洋中。这是一个猜测和检查，看看编译器何时停止向我抛出错误。 – xyzjace 2010-10-14 01:49:52

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

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

干杯&心连心，

来源

2010-10-14 01:47:58

我读了所有的评论，以确保我不会错过任何东西。谢谢:) – xyzjace 2010-10-14 01:54:06

一旦你已经达到了一个叶子结点，你不关心它的深度了，所以返回值似乎一事无成。

在两个语句：

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

你必须从改变depth两次中间没有序列点（尽管它好像应该是不确定的行为，有不之间的序列点任务的右侧和左侧）。

来源

2010-10-14 01:49:31

我刚刚意识到为什么返回值是多余的，因为我正在输入这个。男人我感到愚蠢。谢谢：）！不确定什么序列点，对不起。 – xyzjace 2010-10-14 01:58:10

@ user475234：我辩论甚至提到它，因为修复代码否则会消除此问题。除了少数例外，C基本上说你只能在一个给定的语句中修改一个特定的变量，在这种情况下你要做两次（一次是增量，一次是赋值）。 – 2010-10-14 02:18:02

为什么你在节点为NULL时返回。根据你的规格，你不需要返回任何深度
在其他情况下，你只需要增加深度并发送到函数调用。以下是我的代码版本

无效assignDepth（树& T，INT深度） { 如果（T == NULL）回报; 否则 { 深度=深度; （T-> left！= NULL）assignDepth（T-> left，depth + 1）; （T-> right！= NULL）assignDepth（T-> right，depth + 1）; }}

来源

2010-10-14 01:54:33 rkg

它开始变得更有意义了。我现在意识到，当递归完成时，它不需要返回深度，因为它将函数调用从堆栈中取出，深度与调用该函数之前的值相同。感谢：D！ – xyzjace 2010-10-14 02:00:14

我有不同的节点类型稍微复杂一点的设计，这样做，所以我想ID份额。

如果你有一个节点到节点类型不同的树（二进制，一元等），值得简化传统的方法，以避免讨厌的嵌入式IF检查节点类型。

两个功能：

1：从根，通过每个节点运行，并通过recursivly调用本身和每个父加入1检查其对根距离。给每个节点一个深度变量来存储这个。
2：从树中的整个节点集合中针对每个节点深度运行MAX检查，最高的数字将等于该树的深度。

以这种方式处理，删除明确的类型检查，并简单地统计节点，无论它是否有一个，两个或一百个孩子。

希望这可以帮助别人！

来源

2014-06-20 15:33:18 CAR182

为每个节点分配一个深度

回答

相关问题