二叉搜索树的总高度

我正在构建一个二叉搜索树，我想创建一个记录每个节点高度并对其进行求和的函数。我正在尝试使用递归。二叉搜索树的总高度

对我来说，困难在于给每个节点分配一个高度，然后返回并对其进行总结。除非我能一次性分配和记录高度？提前致谢。

编辑：最终代码显示对于任何将来查看此内容的人而言，我的工作方式。谢谢你们的帮助。

BST.h 

    int totalheight(node); 
    int getHeight(node); 

    class BST { 
    Node root; 
    public: 
     BST { root = NULL; } 
     int totalheight() 
     { return ::totalheight(root); 
    }; 


BST.cpp 

int totalHeight(BSTNode* node) 
{ 
    if (node == NULL) 
     return -1; 

    int leftHeight = getheight(node->left); 
    int rightHeight = getheight(node->right); 
    int totalheight = 1 + leftHeight + rightHeight; // +1 to count the root 

    return totalheight; 
} 

int getheight(BSTNode* node) 
{ 
    if (node == NULL) 
     return 0; 

     return 1 + max(getheight(node->left), getheight(node->right)); 
} 

main.cpp 

    int main() { 
     BST tree; // and various inserts 

     tree.totalheight(); 
    } // main

来源

2013-10-11 Dalkurac

你能理清一下代码？ 'totalheight（）'没有参数，'totalheigh（BSTNode *）'，'findheight（）'，'getheight（）'...这有点混乱。 – Angew

看起来你主要有命名和语法问题，并且在战略性的地方忘了'+ 1'。 – molbdnilo

已修复，请参阅上文。我包括我的头文件，看看我从main调用它。 – Dalkurac

的一个问题是在这里：

int myheight = max(leftheight, rightheight);

它应该是：

int myheight = max(leftheight, rightheight) + 1;

你需要一个accound这个节点的高度。在显示的代码findHeight中也应该是getHeight。

下面是一个整体的功能：


int getheight(BSTNode* node) 
{ 
    if (node == null) 
     return 0; 
    else 
     return 1 + max(getHeight(node->left), getHeight(node->right)); 
} // getheight

来源

2013-10-11 14:44:04 pippin1289

我首先想到了处理这种情况，即只有左边或右边是NULL但不是两个，但在技术上它已经被处理了。第一个如果检查返回-1，并且max（）调用“过滤”出。这也假设“findHeight”假设为“getHeight”。 –

对，我修改了一下我的代码。我们不需要知道这个神秘的'findHeight'就可以计算高度。 – pippin1289

短而甜。您有我的投票;） –

二叉搜索树的总高度

回答

相关问题