检查，如果树是使用递归

实现平衡：检查，如果树是使用递归

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，空树的高度为零。因此，空树被认为是完美平衡的。

如何处理随着我们向下移动树而递增的递归？

来源

2012-10-19 Bob John

你的问题是你担心递归深度还是你不知道如何做递归？ –

我发现可能难以递归地实现该函数，而无需将其重定向到返回高度的函数并递归地同时检查平衡。 – Serge

@Serge嗯......我注意到在第一次阅读这个问题时，忘记了它。想想我需要一些早晨的咖啡（或类似的替代品）。 :) –

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

如果你担心最大递归深度，并可能吹出来的调用栈：有一两件事你可以做的是不使用调用堆栈的。也就是说，将递归实现为一个作用于标准堆栈对象之上的循环。在这种情况下，这会将大部分内存使用量移动到堆上（通过动态重新分配基础列表，deque等）并防止泛滥您的调用堆栈。（请注意，关于内存使用情况和stack vs heap的讨论实际上是C++实现依赖的，但是，据我所知，它适用于所有主要的PC环境。

来源

2012-10-19 18:08:14 WeirdlyCheezy

检查，如果树是使用递归

回答

相关问题