当前位置: 首页 > 知识库问答 >
问题:

实现递归的Void函数(查找二进制搜索树的高度)

郁烨
2023-03-14

我需要实现一个空函数,它计算二叉树中每个节点的高度,并将其存储在每个节点中。我在网上找到了一些本质上是递归的解决方案,但它们返回int。例子包括(https://www.geeksforgeeks.org/write-a-c-program-to-find-the-maximum-depth-or-height-of-a-tree/)。模型答案之间的区别,除了它不是空函数之外,它也不存储每个节点的高度。

这是我对解决方案的尝试,但我似乎无法让代码工作,也无法修改模型答案以递归方式应用于空函数。当我在助手代码中运行我的代码进行测试时,它甚至没有显示任何输出。

void computeHeight(Node *n) {
  Node* ltraverser = n;
  Node* rtraverser = n;
  int lheight = 0;
  int rheight =0;

  if (n == NULL) {
   n->height = 0;
  }

  while (ltraverser->left != NULL) {
   ltraverser = ltraverser->left;
   lheight += 1;
  }

  while (rtraverser->right != NULL) {
   rtraverser = rtraverser->right;
   lheight += 1;
  }

  if (lheight > rheight) {
    n->height = lheight;
  }

  else {
    n->height = rheight;
  }

  computeHeight(n->left);
  computeHeight(n->right);
}

供参考:

The starter code below defines a class called "Node" that has two child pointers ("left" , "right") and an integer "height" member variable. There is also a constructor Node() that initializes the children to nullptr and the height to -1.

/*
The height of a node is the number of edges in
its longest chain of descendants.

Implement computeHeight to compute the height
of the subtree rooted at the node n. Note that
this function does not return a value. You should
store the calculated height in that node's own
height member variable. Your function should also
do the same for EVERY node in the subtree rooted
at the current node. (This naturally lends itself
to a recursive solution!)

Assume that the following includes have already been
provided. You should not need any other includes
than these.

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>

You have also the following class Node already defined.
You cannot change this class definition, so it is
shown here in a comment for your reference only:

class Node {
public:
  int height; // to be set by computeHeight()
  Node *left, *right;
  Node() { height = -1; left = right = nullptr; }
  ~Node() {
    delete left;
    left = nullptr;
    delete right;
    right = nullptr;
  }
};
*/

用于测试代码

// This function prints the tree in a nested linear format.
void printTree(const Node *n) {
  if (!n) return;
  std::cout << n->height << "(";
  printTree(n->left);
  std::cout << ")(";
  printTree(n->right);
  std::cout << ")";
}

  Node *n = new Node();
  n->left = new Node();
  n->right = new Node();
  n->right->left = new Node();
  n->right->right = new Node();
  n->right->right->right = new Node();

  computeHeight(n);

  printTree(n);
  std::cout << std::endl << std::endl;
  printTreeVertical(n);

  delete n;
  n = nullptr;

  return 0;
}

共有2个答案

张腾
2023-03-14

您的错误是在以下部分,因此您的程序退出而不显示错误

if (n == NULL) {
   n->height = 0;
}

当n为空时;您不应该尝试访问n-

if (n == NULL) {
    return;
}

另外,正如另一个答案所提到的,当您想要递归计算高度时,您不需要一个当循环,只需使用以下递归公式:

Height(n) = 1 + max(Height(n->left), Height(n->right))

此外,出于一致性原因,空子树的高度通常定义为-1。这使得递归公式能够正常工作。

建议:为了调试任何程序,一个简单的方法就是在函数调用和/或某些行之前和之后打印消息。通过检查未打印的消息,可以快速确定哪些功能/行导致问题,然后进行调查。

孔阎宝
2023-03-14

不返回节点高度,只需在左侧和右侧节点上反复调用computeHeight,然后在节点结构中存储最大高度。

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <algorithm>

class Node {
public:
  int height;
  Node *left, *right;
  Node() { height = -1; left = right = nullptr; }
  ~Node() {
    delete left;
    left = nullptr;
    delete right;
    right = nullptr;
  }
};

void computeHeight(Node *node) {

    if (node == nullptr) {
        return;
    }

    computeHeight(node->left);
    computeHeight(node->right);

    int leftHeight = -1;
    int rightHeight = -1;

    if (node->left != nullptr) {
        leftHeight = node->left->height;
    }

    if (node->right != nullptr) {
        rightHeight = node->right->height;
    }

    node->height = std::max(leftHeight, rightHeight) + 1;
}

void printNode(Node *n, int level = 0) {
    if (n == nullptr) {
        return;
    }

    std::cout << std::string(level * 2, ' ') << "Height = " << n->height << "\n";

    printNode(n->left,  level + 1);
    printNode(n->right, level + 1);
}


int main() {
  Node *n = new Node();
  n->left = new Node();
  n->right = new Node();
  n->right->left = new Node();
  n->right->right = new Node();
  n->right->right->right = new Node();


  computeHeight(n);
  printNode(n);
}
 类似资料:
  • 我正在尝试使用递归在python中实现二进制搜索树。我被困在程序中发生的一些无限递归中。我通过传递地址和数据对函数RecursBST进行递归调用,直到顶部遍历到它的左或右子级的None值为止。 我运行到以下错误:

  • 这是作业,不要贴代码。求你了,谢谢你。 我被指派创建一个计算BST中特定的深度的方法。 为此,我需要a方法。因此,要递归地找到它,我需要创建一个助手方法。 我知道我需要在树中搜索包含我要查找的数据的节点。为此,我编写了以下代码: 然而,这是行不通的,因为每次进行递归调用时,将保持;本质上,它是在重置深度值。我不知道如何在调用之间保持的值。

  • 从二叉查找树中删除节点时,您可以将节点替换为左侧的最大子节点或右侧的最小子节点。 我很难理解以下实现执行删除操作的方式。 上面的代码包括以下步骤: < li >查找替换节点。 < li >让替换节点引用已删除节点的左右子节点。 < li >让已删除节点的左右子节点将替换节点作为父节点。 < li >让替换节点引用已删除节点的父节点作为自己的父节点。 < li >清理。 我有困难的部分特别是递归。据

  • 问题内容: 我正在编写一个使用二进制搜索树存储数据的程序。在以前的程序中(无关),我能够使用Java SE6随附的实现来实现链表。二进制搜索树是否有类似的东西,还是我需要“从头开始”? 问题答案: 您可以使用。被实现为一棵红黑树,这是一个自平衡二进制搜索树。

  • 问题内容: 我知道Go有一个包含搜索功能的程序包,但这是出于教育目的。我一直在尝试在Go中实现二进制搜索算法,但无法使其正常工作。 这是我的代码: 它总是打印。为什么? 问题答案: 二进制搜索的逻辑是合理的。唯一的问题是您忘记了将每个递归调用的结果分配给和。 当前,您有以下这些递归调用: 您只需要分配结果:

  • 我正在尝试实现一个二叉查找树,但是“搜索”函数对于除了根之外的每个条目都返回了错误的值。 该函数应返回其值与键参数匹配的节点的地址,如果节点不存在,则返回 NULL。 当我运行代码时,我得到以下内容: 我知道每个节点的“左”和“右”指针链接正确,因为“delAll”函数成功删除了所有节点。 将“cout”语句添加到“search”函数表明该函数似乎返回了正确的地址。为什么从主主调用时会打印错误的地