查找二叉树中的最大元素

Question

我对在

binary tree

中查找元素感到非常困惑。

问题：当我们说，在二叉树中搜索一个元素，最大，在这种情况下，我们是否假设树是有序的？？？

如果没有，请看下面的代码，我从一本书上得到它，几乎每个在线 URL 都建议类似的模式

int FindMaxNmb(BinaryTreeNode root)
{
    int root_val, left, right, max;
    if(root != null)
    {
        root_val = root.getData();
        
        //recursion - this is what I don't understand
            
        /*
        * This code would have made sense if the binary tree contained
        * Sorted elements, like  The left subtree of a node contained 
        * Only nodes with keys less than the node's key The right subtree 
        * of a node contained only nodes with keys greater 
        * than the node's key.  
        * */

        left = FindMaxNmb(root.getLeft());
        right = FindMaxNmb(root.getRight());
            
        //Find max number
        if(left > right)
        {
            max = left;
        }
        else
        {
            max = right;
        }
    
        if(root_val > max)
        {
            max = root_val;
        }
    }
    return max;
}

我不明白的是：以这个递归为例

left = FindMaxNmb(root.getLeft());

这将继续调用，除非它到达最左边的底部叶子，然后分配值，与

getRight()

相同......但是这个东西只适用于有 2 个子节点的最左边的节点......它如何检查剩余节点的值（我假设二叉树未排序）

我知道我在这里遗漏了一些非常明显的东西......请帮忙！！

Answer 1

二叉树和二叉搜索树之间的区别在于，BST在每个节点及其左/右子节点之间都有保证 - 普通的BT没有排序。

所提供的代码适用于普通二叉树，因为它以深度优先的方式遍历所有节点。 （如果数据是 BST，算法只需要找到“最右边”的节点并返回它的值即可找到树中的最大值。）

现在，在所示的 BT 实现中，每个递归函数都会查找由左或右子节点（子节点是子树的根）给出的子树的最大值，并且返回的正是该值。

例如，考虑这个二叉树，在这种情况下它不是 BST（来自维基百科）：

调用堆栈按照树的方式工作，如下所示，其中

-

表示堆栈级别，数字表示节点。

-2
--7 (l)
---2 (l)
---6 (r)
----5 (l)
----11 (r)
--5 (r)
---9 (r)
----4 (l)

堆栈只能在到达最终情况时“展开” - 之后已计算出左子树和右子树的最大值（通过递归到

FindMaxNmb

）。

在放松阶段..

• ..到达节点 11 时，没有正确的节点，因此返回到 6
• 由于这完成了在右子树（6 个）中的搜索，因此返回到 7
• 由于这完成了在右子树（7 个）中的搜索，因此返回到 2
• 由于这完成了左子树（2）中的搜索，因此进入右子树（5）..