二叉樹的最小元素

Question

我已經實現了查找二叉樹的最大和最小元素的函數。但是我得到了錯誤的輸出。

函數用於查找二叉樹的最大值。

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

Answer 1

問題的最小最大值爲您允許的函數，在一個空的樹被調用。如果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; 
} 

就是這麼簡單。

請注意，我不會沿着正確的分支走，因爲它總是比當前節點大。

Answer 2

遞歸實現了一般二叉樹找到最小值： 這裏是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; 
} 
} 

這裏是BinaryTreeOps類是minvalue操作：關鍵是使用靜態變量min，以便每當我們找到一個低於前一個值的值時重置相同的靜態變量。如果傳遞一個空節點，它將返回零。您可以按照您的要求修改此行爲。

在主：

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

的功能：

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()); 
} 
} 

Answer 3

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; 
} 

Answer 4

一種方法使用遞歸做到這一點（在C）

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; 
} 

請注意，在這裏你必須通過原始的根VA當你第一次調用這個函數，然後每次通過當前的最大值。您不會進入空節點的函數，並且您不會在函數本身中創建任何新變量。

只在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變量以便於使用和易讀。 （或預先定義一個最小宏）。