在二叉树中找到最大元素

Question

我对在二叉树中查找元素感到非常困惑。

问题: 当我们说，在二叉树中搜索一个元素，特别是最大值时，我们是否假定该树已排序？
如果没有，看一下下面的代码，我从一本书上找到了它，几乎每个在线网址都建议使用类似的模式。

int FindMaxNmb(BinaryTreeNode root)
    {
        int root_val,left,right,max;
        if(root!=null)
        {
            root_val = root.getData();

            //recursion - this is what i dont understand

            /*
             *
             * This code would have made sense if 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 nmbr
            if(left > right)
            {
                max = left;
            }
            else
            {
                max = right;
            }

            if(root_val > max)
            {
                max = root_val;
            }
        }
        return max;
    }

我不理解的是：以递归为例，left = FindMaxNmb(root.getLeft()); 这将一直调用直到它到达最左下角的叶子节点，然后赋值，getRight() 同样如此......但这个东西只对拥有2个孩子的最左端节点有效...那么如何检查其余节点的值（我假设二叉树没有排序）？

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

- NoobEditor

---

好的，让我简单明了地说一下...在我发布的代码中，它是在二叉搜索树的前提下搜索最大元素，而不是普通二叉树...对吗？ - NoobEditor

让我们在聊天中继续这个讨论：http://chat.stackoverflow.com/rooms/47073/discussion-between-noobeditor-and-user2864740 - NoobEditor

Answer 1

“二叉树”和“二叉搜索树”的区别在于BST保证每个节点与其左/右子节点之间有序关系，而普通的二叉树则没有这种排序。所提供的代码适用于普通的二叉树，因为它以深度优先的方式遍历所有节点。（如果数据是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）...

- user2864740