如何創建一個返回無序二叉樹的最小值的函數

Question

這看起來應該很容易，但我一直有這個問題很長一段時間。正如標題所說，我只是試圖在二叉樹（不是BST！）中找到具有最小值的節點並將其返回。我可以很容易地編寫一個遞歸的void函數，它至少可以分配函數中的最小值，但是當我到達NULL指針時，我會陷入如何返回前一個節點的軌道。

我有一個節點類，它有一個指向左右子節點的指針，每個節點都有自己的值。這裏是我的（失敗）的嘗試至今：

int preOrder(Node *node, int value, int count, int sizeOfTree) 
{ 
    count++; //keeps track of whether or not we have traversed the whole tree 

    if(value < node->getValue()) 
    value = node->getValue(); 

    if(count == sizeOfTree); 
    return value; 

    if(node == NULL) 
    //Want to return to the previous function call 
    //How do I do this for a non void function? 
    //for a void function, you could jsut type "return;" and the function 
    //back tracks to your previous place in the tree 
    //but since I'm returning a value, How would I go about doing this? 

    //these 2 calls are incorrect but the idea is that I first traverse the left subtree 
    //followed by a traversal of the right subtree. 
    preOrder(node->getLeft(), value); 

    preOrder(node->getRight(), value); 

} 

如果可能的話，我想嘗試做這個不保持的「計數」，以及使代碼更清潔的軌道。 讓我知道是否需要澄清。

Answer 1

我不明白爲什麼在你的原始代碼中，你需要跟蹤遍歷元素的數量。這裏是我的解決方案：

int find_min(Node* node) 
{ 
    int value = node->getValue() 

    Node* left_node = node->getLeft(); 
    if (left_node != NULL) 
    { 
    int left_value = find_min(left_node); 
    if (left_value < value) 
     value = left_value; 
    } 

    Node* right_node = node->getRight(); 
    if (right_node != NULL) 
    { 
    int right_value = find_min(right_node); 
    if (right_value < value) 
     value = right_value; 
    } 

    return value; 
} 

Answer 2

基本上你需要做的就是訪問每個節點並跟蹤你所看到的最小值。這實際上可以相當簡單做到：

#include <algorithm> 
#include <limits> 

int preOrder(Node *node) 
{ 
    if(node == NULL) return std::numeric_limits<int>::max(); 
    // this should never affect the calculation of the minimum 
    // (What could possibly be bigger than INT_MAX? At worst it's equal) 

    int value = std::min(
    node->getValue(), 
    preOrder(node->getLeft()) 
    ); 

    value = std::min(
    value, 
    preOrder(node->getRight()) 
    ); 

    return value; 

} 

Answer 3

OK，讓你擁有一個無序二叉樹和你試圖找到最低的元素在裏面。

由於樹是無序的，最低的元素可以在樹中的任何位置，因此您必須搜索整個樹。

搜索的特點將是如下：

• 徹底（整個樹被搜索）
• 遞歸（而不是重複的，這將是非常難吃）
• 基本情況：節點NULL
• 鹼結果：維持電流值

允許它寫然後：

#include <algorithm> 
using namespace std; 

int searchLowest(Node * node, int value = INT_MAX) 
{ 
    if (node == NULL) // base case 
     return value; // base outcome 

    // at this point, node must not be NULL 

    value = min(value, preOrder(node->getRight(), value)); // thorough, always recurse 
    value = min(value, preOrder(node->getLeft(), value)); // and check children 
    value = min(value, node->getValue()); 
    return value; 
} 

編輯爲徹底，公正，OOness：

// Node.h 
#include <algorithm> 
using namespace std; 

template <typename T> 
class Node 
{ 
public: 
    Node(T item) 
    { 
     data = item; 
    } 

    T lowest() 
    { 
     T value = data; 

     if (right != NULL) 
      value = min(value, right->lowest()); 
     if (left != NULL) 
      value = min(value, left->lowest()); 

     return value; 
    } 

    Node<T> * getRight() 
    { 
     return right; 
    } 

    Node<T> * getLeft() 
    { 
     return left; 
    } 

private: 
    T data; 

    Node<T> * right; 
    Node<T> * left; 
}; 

// main.cpp 
#include <iostream> 
#include "Node.h" 
using namespace std; 

int main(int c, char * v[]) 
{ 
    Node<int> * tree = sycamore(); // makes a nice big tree 

    cout << tree->lowest(); 
} 

SEE JIMMY RUN