二叉搜索树-将每个节点添加到一个结果中

Question

我尝试在Java中以迭代的方式将每个节点添加到一个结果中。例如:如果我有一个根5，它的右节点= 7，左节点=3，结果是15。我尝试了很多方法，但我不知道当我的树很庞大时，如何不遗漏任何节点。

我将感激每一个小费。

Answer 1

查找树遍历。有三种基本类型:订单、预购和后购。实际上，您需要创建一个接受节点作为参数并返回整数的函数。

假设你有一个这样的节点:

struct Node {
int value;
Node *right, *left;
}

这样做就可以了。

int tree_sum(Node *root) {
if (root == nullptr) return 0; // stops recursion. occurs at leaves
return root->value + tree_sum(root->left) + tree_sum(root->right);
}

在树的根节点上调用函数。这被称为预顺序遍历。我用c++写代码，因为我不懂Java。

对于没有递归的树遍历，使用如下所述的堆栈:

https://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion/