0

数字を順番に印刷するための単純なBST。私が何を間違えたのか理解できませんでした。

#include <iostream>
using namespace std;

class bst {
 private:
  bst* root;
  bst* left;
  bst* right;
  int value;

 public:
  bst(const int& numb) : root(NULL), left(NULL), right(NULL) {
    value = numb;
  }

  void insert(const int& numb) {
    if (numb < value) {
      if (left == NULL) {
        left = new bst(numb);
        left->root = left;
      } else { 
        left->insert(numb);
      }
    } else if (numb > value) {
      if (right == NULL) {
        right = new bst(numb);
        right->root = right;
      } else {
       left->insert(numb);  
      }
    } else if (numb == value) {
      cout << "duplicated value" << endl;
    }
  }

  void inorder() {
    if (left == NULL) cout << value << endl;
    else left->inorder();
    right->inorder();
  }
};


int main() {
  bst tree(5);
  tree.insert(7);
  tree.insert(1);
  tree.insert(3);
  tree.insert(2);
  tree.insert(9);
  tree.insert(10);
  return 0;
}
4

4 に答える 4

3

29行目は次のようになります。

 right->insert(numb);

現在のところ：

 left->insert(numb);

このような状況を解決するには、gdbを調べることを強くお勧めします。

于 2012-06-01T03:57:32.930 に答える
1

全体の論理エラー。

クラッシュはここにあります：

  if (right == NULL) { 
    right = new bst(numb); 
    right->root = right; 
  } else { 
   left->insert(numb);   
  }

elseの場合は、左ではなく右に使用します。

于 2012-06-01T04:00:40.180 に答える
1

inorder()次のようにする必要があります。

if (left != NULL) left->inorder();
cout << value << endl;
if (right != NULL) right->inorder();

残りは正しいと思います。

于 2012-06-01T03:54:16.180 に答える
1

少なくとも私が見る限り、あなたの基本的な設計には欠陥があります。多くの教科書 (など) では、ツリーは、各ノードに 2 つのサブツリーがある再帰構造として説明されていますが、コードを設計するための非常に良い方法を見つけたことはありません。

少なくとも私の経験では、実際のコードでは、ツリー内のノードの概念をツリー全体の概念から分離する方が (はるかに) 優れています。外の世界から見えるのはツリーだけです。node外の世界からは見えないように、ツリーの中に隠されている必要があります。

class bst {
    class node {
        int value;
        node *left;
        node *right;

        // ...

    };

    // ...

    node *root;   
};

insert次に、2 つの部分に分割します。値を受け取りroot、開始点として を使用して 2 番目の関数に転送するパブリック関数です。2 番目は実際に 3 つをトラバースし、新しいアイテムを挿入します。

// public interface:
void insert(int v) {    
    insert(new node(v), root);
}

// private workhorse:
void insert(node *n, node *&pos) {
    if (pos == NULL)
        pos = n;
    else if (n->value < pos->value)
        insert(n,pos->left);
    else if (n->value > pos->value)
        insert(n,pos->right);
            else
                // duplicate value.
}

同様に、inorderget は public と private のペアに分割され、public はインターフェースのみを提供し、private はすべての実際の作業を行います。

// public interface:
void inorder() {
    inorder(root);
}

// private worker
void inorder(node *n) {
    if (n==NULL)
        return;
    inorder(n->left);
    std::cout << n->value << endl;
    inorder(n->right);
}

価値があるのは: はい、私はこのコードをテストしましたが、少なくとも you で使用した入力で動作しますmain。ただし、欠点があります。たとえば、 と の両方がツリーを再帰的insertにinorderトラバースするため、大規模でひどく不均衡なツリーはスタック オーバーフローにつながる可能性があります。繰り返し挿入を行うのはかなり簡単ですが、実際に使用する場合は通常、代わりに何らかのバランスの取れたツリーに切り替えるだけです。

于 2012-06-01T04:45:15.943 に答える