c - 是否可以在不使用递归或堆栈/队列的情况下获得二叉树的高度？

Question

我正在用 C 编写一个程序，其中涉及对返回二叉树高度的函数的多次调用。最初我使用递归来做到这一点，但很快又回来咬我，因为我收到堆栈溢出错误(不是由于无限递归)。为了解决这个问题，我试图修改函数以不使用递归，而是使用迭代。是的，可以使用堆栈/队列来执行此操作，但我更希望不必这样做。

我找到了一个网站，该网站提供无需递归或堆栈即可遍历树的代码。这是链接:http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/

我试图修改它，而不是打印出每个节点，而是测量最大深度，但我不确定我会怎么做。我该怎么做。

Answer 1

您链接到的代码似乎通过修改树将其转换为 threaded binary tree 来工作。 .这是一棵二叉树，其中每个缺少子指针的节点不是存储空指针，而是存储指向其有序前驱或后继的指针(取决于它是否缺少左子树或右子树)。

这允许您在不需要任何辅助存储空间的情况下导航整个树。要下降到子树，您可以像往常一样进行。要向上爬到父节点，如果您当前的节点是左子节点，则跟踪原始节点 v，然后下降到右子节点，直到您在此过程中跟随线程回到 v 的父节点，您可以识别它，因为它将 v 作为左 child 。 (你可以对正确的 child 做类似的技巧)。

您链接到的代码的工作原理是从一个常规的旧二叉树开始，然后在遍历它时惰性地插入然后删除线程。通过跟踪线程并跟踪线程的添加和删除时间，了解如何向上和向下下降，这是一个很好的跟踪代码的练习。

直接回答您的问题:是的，可以跟踪树中任何节点的最大深度。为此，请修改通过插入和删除线程工作的搜索算法，跟踪您遇到的节点的深度，并在树中向上或向下移动时小心调整它们。

话虽这么说，但我很少在实践中看到这样做。例如，它不能很好地处理多线程(这与此处描述的线程无关)。不过，这是一项很棒的练习!