使用递归的红黑树高度

本文介绍了使用递归的红黑树高度的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我有以下这些方法来获得一个红黑树的高度，这工作（我发送根）。现在我的问题是，这是如何工作？我画了一棵树，并尝试按照这一步一步一步的每个递归调用，但我不能拉掉。 我知道代码在做什么的一般想法，这是通过所有的叶子和比较它们，但任何人都可以清楚地解释这一点？

I have these following methods to get the height of a red black tree and this works (I send the root). Now my question is, how is this working? I have drawn a tree and have tried following this step by step for each recursion call but I can't pull it off. I know the general idea of what the code is doing, which is going through all the leaves and comparing them but can anyone give a clear explanation on this?

int RedBlackTree::heightHelper(Node * n) const{ if ( n == NULL ){ return -1; } else{ return max(heightHelper(n->left), heightHelper(n->right)) + 1; } } int RedBlackTree::max(int x, int y) const{ if (x >= y){ return x; } else{ return y; } }

推荐答案

，通用算法找到任何二叉树的高度（BST，AVL树，红黑等）如下

Well, the general algorithm to find the height of any binary tree (whether a BST,AVL tree, Red Black,etc) is as follows

For the current node: if(node is NULL) return -1 else h1=Height of your left child//A Recursive call h2=Height of your right child//A Recursive call Add 1 to max(h1,h2) to account for the current node return this value to parent.

上述算法的说明如下：

（图片提供 Wikipedia ）