0

我已经实现了查找二叉树的最大和最小元素的函数。但我得到了错误的输出。

查找二叉树最大值的函数。

int FindMax(struct TreeNode *bt)
{
//get the maximum value of the binary tree... 
int max;
//get the maximum of the left sub-tree. 
int left;
//get the maximum of the right sub-tree.
int right;
//get the root of the current node.
int root;

        if(bt!=NULL)
        {

                root=bt->data;
                //Call the left tree recursively....
                left=FindMax(bt->leftChild);

                //Call the right tree recursively...
                right=FindMax(bt->rightChild);

                if(left > right)
                {
                        max=left;
                }
                else
                {
                        max=right;
                }
                if(max < root)
                {
                        max=root;
                }

        }

return max;
}

查找二叉树最小值的函数。

int FindMin(struct TreeNode *bt)
{
//get the minimum value of the binary tree... 
int min;
//get the minimum of the left sub-tree. 
int left;
//get the minimum of the right sub-tree.
int right;
//get the root of the current node.
int root;
        if(bt!=NULL)
        {

                root=bt->data;
                //Call the left tree recursively....
                left=FindMin(bt->leftChild);

                //Call the right tree recursively...
                right=FindMin(bt->rightChild);

                if(left < right)
                {
                        min=left;
                }
                else
                {
                        min=right;
                }
                if(min > root)
                {
                        min=root;
                }

        }

return min;
}

输出：树的最大值 32767

树的最小值 0

4

4 回答 4

6 
private int minElem(Node node) {
    int min= node.element;
    if(node.left != null) {
        min = Math.min(min, minElem(node.left));
    }
    if(node.right != null) {
        min = Math.min(min, minElem(node.right));
    }
    return min;
}
于 2014-04-19T18:59:17.573 回答
1

在通用二叉树中查找最小值的递归实现：这是 BinaryTreeNode 类： 

package binaryTrees;

public class BinaryTreeNode {

private int data;
private BinaryTreeNode left;
private BinaryTreeNode right;
private int max;
private int min;

public int getMax() {
    return BinaryTreeOps.maxValue(this);
}
public int getMin() {
    return BinaryTreeOps.minValue(this);
}

public BinaryTreeNode(){

}
public BinaryTreeNode(int data){
    this.data = data;
}

public int getData() {
    return data;
}
public void setData(int data) {
    this.data = data;
}
public BinaryTreeNode getLeft() {
    return left;
}
public void setLeft(BinaryTreeNode left) {
    this.left = left;
}
public BinaryTreeNode getRight() {
    return right;
}
public void setRight(BinaryTreeNode right) {
    this.right = right;
}
}

下面是具有 minValue 操作的 BinaryTreeOps 类： 关键是使用一个静态变量 min ，以便我们每次找到一个低于前一个值的值时重置同一个静态变量。如果传递一个空节点，则返回零。您可以根据需要修改此行为。

package binaryTrees;

public class BinaryTreeOps {
private static int min;

public static int minValue(BinaryTreeNode node){
    min=node.getData(); //imp step, since min is static it is init by 0
    minValueHelper(node);
    return min;
}
public static void minValueHelper(BinaryTreeNode node){
    if(node==null)
        return;
    if(node.getData()<min)
        min=node.getData();
    if(node.getLeft()!=null && node.getLeft().getData()<min)
        min=node.getLeft().getData();
    if(node.getRight()!=null && node.getRight().getData()<min)
        min=node.getRight().getData();
    minValueHelper(node.getLeft());
    minValueHelper(node.getRight());
}
}
于 2013-11-23T09:58:10.120 回答
0

问题是您允许在空树上调用该函数。如果bt是 NULL，那么你将返回一个未初始化的值min，它似乎恰好是 0。

我不喜欢你实际搜索整棵树的方式。 FindMin应该是O(logN)（如果你的树是平衡的），而不是O(N)。我建议你不要盲目打电话。相反，请始终遵循保证达到最低限度的路径。一旦找到该值，您的递归就会停止：

int FindMin( struct TreeNode *bt )
{
    if( !bt)
        return 0;  // Only if the tree contains nothing at all
    if( bt->leftChild )
        return FindMin(bt->leftChild);
    return bt->data;
}

就这么容易。

请注意，我没有沿着正确的分支走，因为它总是比当前节点大。

于 2013-06-20T22:59:34.990 回答
0

使用递归的一种方法（在 C 中）：

主要：

printf("maximum (not BST) is: %d\n", FindMax(root, root->x));

功能：

int FindMax(node *root, int max)
{
    if(root->x > max) max = root->x;
    if(root->left != NULL)
        max = FindMax(root->left, max);
    if(root->right != NULL )
        max = FindMax(root->right, max);
    return max; 
}

请注意，这里您必须在第一次调用函数时传递原始根值，然后每次传递当前最大值。您不会进入空节点的函数，也不会在函数本身中创建任何新变量。

“ravi ranjan”的实现仅在 c: 中主要：

printf("minimum (not BST) %d\n", FindMin(root));

功能：

int FindMin(node *root)
{
    int min = root->x;
    int tmp;
    if(root->left != NULL)
    {
        tmp = FindMin(root->left);
        min = (min < tmp) ? min : tmp;
    }    
    if(root->right != NULL)
    {
        tmp = FindMin(root->right);
        min = (min < tmp) ? min : tmp;

    }    
    return min; 
}

请注意，这里您确实创建了一个局部变量（很像前面示例中传递的值），并且您还需要创建一个 tmp 变量以便于使用和可读性。（或预先定义一个最小宏）。

于 2016-09-15T10:28:34.870 回答