c++ - 返回完整二叉搜索树底层最右边节点的函数

Question

我只需要帮助编写一个递归函数，该函数返回二叉搜索树最深层最右边的节点(它实际上是一个基于节点的堆)。重要的是要记住树将永远是完整的。我已经尝试了一些东西，但没有任何效果足以作为开始张贴在这里。

我发现了类似的问题，但这些问题都与我能做的最左边的节点有关，因为它总是在同一个地方，但最右边的节点根据树的填充程度而变化。

我有函数 getLeftHeight 和 getRightHeight

void HeapClass::findDeleteNode( HeapNode *&workingPtr ){

}

我有这样的原型(prototype)，我在其中发送一个指针，稍后我从中取出值并在不同的函数中删除。我是这个网站的新手，如果这个问题缺少信息或发布不正确，我深表歉意。任何帮助将不胜感激，谢谢。

Answer 1

您需要比较左子树和右子树的高度。如果右侧的高度大于或等于左侧，则在该节点上递归，否则在左侧

void HeapClass::findDeleteNode( HeapNode *&workingPtr )
{
     bool isLeaf = getLeftHeight(workingPtr)) == 0 && getRightHeight(workingPtr) == 0;
     if(isLeaf) {
         // found it
         return;
     }

     findDeleteNode(getLeftHeight(workingPtr) > getRightHeight(workingPtr) ? workingPtr->left : workingPtr->right);
}