이진 트리의 최소 요소

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의 경우, 당신은 그냥 보인다 난 당신이 실제로 전체 트리를 검색하는 방법을 좋아하지 않아 0

될 일이있는 min에 대한 초기화되지 않은 값을 반환 할 것입니다. FindMin은 이어야합니다. O (N)이 아니라 O (logN) (트리 균형이 조정 된 경우)이어야합니다. 나는 맹목적으로 전화하지 말 것을 제안합니다. 대신, 항상 최소로 이어질 수있는 경로를 따르십시오. 그 값을 발견하자마자 재귀가 중지됩니다.

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

일반적인 이진 트리에서 최소값을 찾는

재귀 구현 :

다음

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 클래스입니다 : 요점은 정적을 사용하는 것입니다 여기에 는 BinaryTreeNode 클래스입니다 변수 min을 사용하여 이전 값보다 낮은 값을 찾을 때마다 동일한 정적 변수를 재설정합니다. null 노드를 전달하면 0을 반환합니다. 요구 사항에 따라이 동작을 수정할 수 있습니다. 메인에서

:

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를 통과해야합니다. lue 함수를 처음 호출하면 매 순간 현재 최대 값을 전달합니다. 빈 노드에 대해서는 함수로 가지 않고 함수 자체에 새로운 변수를 만들지 않습니다.

는 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 변수를 만들어야합니다. (또는 최소 매크로를 미리 정의하십시오).