0

实施：

bool tree_isBalanced(tree_t tree);
    // EFFECTS: returns true if tree is balanced, false otherwise

鉴于您可以假设已经为您实现了以下功能：

bool tree_isEmpty(tree_t tree);
   // EFFECTS: returns true if tree is empty, false otherwise

tree_t tree_make();
   // EFFECTS: creates an empty tree.

tree_t tree_make(int elt, tree_t left, tree_t right);
   // EFFECTS: creates a new tree, with elt as it's element, left as
   //          its left subtree, and right as its right subtree

int tree_elt(tree_t tree);
   // REQUIRES: tree is not empty
   // EFFECTS: returns the element at the top of tree.

tree_t tree_left(tree_t tree);
   // REQUIRES: tree is not empty
   // EFFECTS: returns the left subtree of tree

tree_t tree_right(tree_t tree);
   // REQUIRES: tree is not empty
   // EFFECTS: returns the right subtree of tree

如果树中每个节点的右子树和左子树的高度相同，则树是平衡的。树的高度定义为从树根到树中最深节点的路径中存在的节点数。只有一个节点的树的高度为 1，而空树的高度为零。因此，空树被认为是完美平衡的。

当我们向下移动一棵树时，我该如何处理递归增长？

4

1 回答 1

0

这取决于您担心递归增长的哪个方面。如果您担心递归调用的总数，可能值得指出的是，这里的典型实现将是 O(N) 总调用，其中 N 是树节点的数量。由于高度的定义是每个节点，很难想象比 O(N) 做得更好。

如果您担心最大递归深度，并且可能会破坏您的调用堆栈：您可以做的一件事是根本不使用调用堆栈。也就是说，将递归实现为作用于标准堆栈对象之上的循环。在底层，这会将大部分内存使用转移到堆上（通过底层列表、双端队列等的动态重新分配）并防止调用堆栈泛滥。（请注意，内存使用和堆栈与堆的讨论实际上取决于 C++ 实现。但是，据我所知，它适用于所有主要的 PC 环境）。

于 2012-10-19T18:08:14.177 回答