c++ - 每个指向节点的 BST 设置高度

Question

我正在尝试实现递归方法以递归地设置每个节点的高度。部分解决方案已实现，但我不完全确定我可以在哪里减少高度并检查特定节点的顺序遍历是否完成。我的程序基于此实现:http://visualgo.net/bst.html

谢谢

Answer 1

如果您在这里的意思是高度代表节点所在的树的级别，那么使用全局变量会给您带来非常奇怪的结果。我也承认不能完全确定您对变量 u 做了什么。

也就是说，我认为您应该接受这样的事情:

public void setHeight(struct node *r, int h = -1) {
    // pointer pointing to null, return
    if(r == NULL)  {
        return;
    }
    h++; // increment height
    r.height = h; // set update height to a current node

    setHeight(r ->u.lc, h); // traverse the list pointing to the left child
    visit(r) // visit pointing node
    setHeight(r ->u.rc, h); // visit right child of the node
}

编辑:我还没有发表评论的名誉，所以我只能通过编辑来回应。 @ProgLearner，你不需要一个单独的变量 u 因为你的节点指针是一个函数参数，所以每次调用函数时你都会有一个新的。同样，正如 Jonathan Mee 所说，h 变量不需要外部初始化，因为它也是函数的本地变量。在您不提供任何初始值的情况下(例如当您在根上调用它时)，它将默认为 -1。