1

以前にこのトピックに関する質問を投稿しましたが、これもわかりません。キー値で順序付けられていないバイナリ ツリーを検索し、再帰関数を介して関連する値を返そうとしています。

クラスの形式は次のとおりです。

  Class Node
  {
     private:
       Node *leftChild;
       Node *rightChild;
       int key;
       int value;
 }

各変数には get メソッドが関連付けられています。したがって、基本的にはバイナリ ツリーを検索し、正しいノードに到達したらその値を返したいと考えています。

これまでの私の試みは次のとおりです。私はかなり近いと思います：

int preOrder(Node *node, int key)
{
   if(node->getKey() == key)
     return node->getValue();

  Node* leftNode = node->getLeft();

  if(leftNode != NULL)
  {
    return preOrder(leftNode, key);
  }

  Node* rightNode = node->getRight();

  if(rightNode != NULL)
  {
    return preOrder(rightNode, key);
  }

  //I know a return statement needs to be placed here
  //in case both pointers are NULL in order to return to the previous
  //node in the tree, but I'm not sure how to do this...
}

誰かアドバイスはありますか？

4

3 に答える 3

2

どうぞ。これには、値ノードだけでなくキー/値ノードをサポートするように変更された、最後の質問に答えるコードが含まれています。また、変更により、ノードに含まれる値ではなく、ノードへのポインターを返すことが理にかなっていたので、lowest も更新してそのようにしました。

template <typename KeyT, typename ValueT>
class Node
{
public:
    Node(KeyT k, ValueT v)
    {
        key = k;
        value = v;
        right = NULL;
        left = NULL;
    }

    Node<KeyT, ValueT> * lowest()
    {
        Node<KeyT, ValueT> * v = this;

        if (right != NULL)
            if (v->value > left->value) v = left;
        if (left  != NULL)
            if (v->value > right->value) v = right;

        return v;
    }

    Node<KeyT, ValueT> * searchByKey(KeyT k)
    {
        if (key == k)
            return this;

        Node<KeyT, ValueT> * n = NULL;

        if (left != NULL)
            n = left->searchByKey(k);
        if (n != NULL) return n;
        if (right!= NULL)
            n = right->searchByKey(k);
        if (n != NULL) return n;

        return NULL;
    }

    Node<KeyT, ValueT> * getRight()
    {
        return right;
    }

    Node<KeyT, ValueT> * getLeft()
    {
        return left;
    }

    void setRight(Node<KeyT, ValueT> * nright)
    {
        right = nright;
    }

    void setLeft(Node<KeyT, ValueT> * nleft)
    {
        left = nleft;
    }

    KeyT getKey()
    {
        return key;
    }

    ValueT getValue()
    {
        return value;
    }

private:
    KeyT   key;
    ValueT value;

    Node<KeyT, ValueT> * right;
    Node<KeyT, ValueT> * left;
};

出力例を見てください: http://ideone.com/l5ZNc

于 2012-07-30T23:21:36.890 に答える
0

はい、あなたは近くにいます。キーが見つからない場合は、何を返せばよいかを考える必要があります。左のノードが NULL でない場合、右のノードをチェックしないことに注意してください。

于 2012-07-30T23:05:08.960 に答える
0 
    int value=NULL;
    void preOrder(Node *node, int key)
    {
       if (node!=NULL){
          if(node->getKey() == key)
            value=node->getValue();

          preOrder(node->getLeft(),key);
          preOrder(node->getRight(),key); 
       }     
    }
于 2012-07-30T23:07:04.147 に答える