-1

これは本当に簡単なはずですが、私はかなり長い間これに問題を抱えています。タイトルが示すように、私は最小値を持つバイナリツリー（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);

}

可能であれば、コードをよりクリーンにするために、「カウント」も追跡せずにこれを試してみたいと思います。さらに説明が必要な場合はお知らせください。

4

3 に答える 3

6

元のコードで、通過した要素の量を追跡する必要がある理由がよくわかりません。これが私の解決策です：

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;
}
于 2012-07-30T19:31:48.320 に答える
1

基本的にあなたがする必要があるのは、すべてのノードにアクセスして、あなたが見た最小の値を追跡することです。これは実際にはかなり簡単に行うことができます。

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

}
于 2012-07-30T19:34:13.780 に答える
1

さて、あなたは順序付けられていない二分木を持っていて、その中で最も低い要素を見つけようとしています。

ツリーは順序付けされていないため、最下位の要素はツリー内の任意の位置に配置できます。したがって、ツリー全体を検索する必要があります。

検索の特徴は次のとおりです。

  • 徹底的（ツリー全体が検索されます）
  • 再帰的（反復的ではなく、本当に厄介です）
  • 基本ケース：ノードは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();
}

ジミーランを見る

于 2012-07-30T19:46:10.007 に答える