２分探索木、挿入

質問

行き詰まりました。
２分探索木の要素挿入です。
何がいけないのでしょうか？？
思うように動作しません。
ルートはどうやら設定されるようですが、
その他のデータがうまく挿入されません。
たぶんポインタの使い方がなってないようなのですが、
どこをどうしていいか分からないのでどなたか教えてください。
(インデントくずれました・・・見にくくてすみません)

データ構造は以下の通りです。
node{
key //item template ですがint とみなしてください。
　 node *left //左の子へのポインタ
　 node *right //右の子へのポインタ
}
root{
node *root //ルートへのポインタ
}

//ここからソース（多少省略してます。）
insert(const K & newKey)
{
　　　　node<K> *temp;

　　　　if(empty()){//ルートの設定。
　　　　　　　　temp = new node<K>(newKey, NULL,NULL);
　　　　　　　　root = temp;
　　　　}else{//木が既存する場合
　　　　　　　　insertItem(root, newKey);
　　　　}
}

insertItem(node<K> *fact, const K & newKey)
{
　　　　node<K> *temp,test;

　　　　if(fact == NULL){//要素挿入
　　　　　　　　temp = new node<K>(newKey,NULL,NULL);
　　　　　　　　fact = temp;
　　　　　　　　test = *fact;
　　　　}else{//挿入場所探索
　　　　　　　　test=*fact;
　　　　　　　　if(test.key == newKey){
　　　　　　　　　　　cout<<"same key";
　　　　　　　　}else if(test.key > newKey){
　　　　　　　　　　　insertItem(test.left, newKey);
}else{
insertItem(test.right, newKey);
}
}
}

回答No.1

S117 · ベストアンサー

ちょっとソースが省略されすぎに見えますが。
ただ、おかしいところは見つけました。

>insertItem(node<K> *fact, const K & newKey)
>fact = temp;

引数としてポインタ値を受け取ってそれを書き換えてももとのポインタ値は書き換わりません。

insertItem(node<K> & *fact, const K & newKey)

あたりでどうでしょ。(factを参照渡しに変更)

見分けるこつとしては、参照(Reference)で受け取ってない引数への代入があったら何かを間違えています。

お礼

まだ参照とポインタがよく理解してなかったです。

＞insertItem(node<K> & *fact, const K & newKey)
参照渡しにして見ましたらうまく動作しました。

ありがとうございます。

以下は訂正後のソースです。
(すみません。インデントがそろえれません。（なぜ・・・・？）)
insertItem(node<K> *& fact, const K & newKey)
{
　　 node<K> *temp;

if(fact == NULL){
temp = new node<K>(newKey, NULL, NULL);
fact = temp;
}else{
if(fact->key == newKey){
cout<<"same key";
}else if(fact->key > newKey){
insertItem(fact->left, newKey);
}else{
insertItem(fact->right, newKey);
}
}
}

回答No.3

BLK314

ちなみに
C++ではSTLが使えます
Standerd なので"標準"です。
どこかのメーカーのライブラリ専用とかでないので
安心して使えます

STLのmapを使えばよいと考えます
http://brain.cc.kogakuin.ac.jp/~kanamaru/lecture/C++2/11/11-A02.html

自分で実装するのも"学習"としては重要かも知れませんが、
実際にプログラミングする際には
STLでサポートされているものはSTLを使うことを考えたほうが良いと思います。

もちろん、STLとて万能ではないので
STLを検討して、その上で、あえて、自作ということもあると思います。

お礼

＞STLのmapを使えばよいと考えます

あらかじめ与えられたデータ構造、その他いくつかの関数を
使い、挿入、削除などの新たな関数をインプリメントする課題でしたので
今回は使うことはできませんが、自学習の際に考えてみようと思います。

＞自分で実装するのも"学習"としては重要かも知れませんが、
＞実際にプログラミングする際には
＞STLでサポートされているものはSTLを使うことを考えたほうが良いと思います。

要素追加、削除などO(log n)で行えるようですし、mapを使用した方が
将来的にはいいようですね。

回答No.2

επιστημη（@episteme）

#include <iostream>

template<typename T>
struct node {
　T key;
　node *left;
　node *right;
　node(const T& k) : key(k), left(0), right(0) {}
};

template<typename T>
class tree {
　node<T>* root;
public:
　tree() : root(0) {}
　bool insert(const T& newKey);
　bool empty() const { return root == 0; }
　void print(std::ostream& out) const { print(root, out); }
private:
　static bool insert(node<T>*& fact, const T& newKey);
　static void print(const node<T>* fact, std::ostream& out);
};

template<typename T>
bool tree<T>::insert(const T& newKey) {
　if ( empty() ){
　　root = new node<T>(newKey);
　} else {
　　return insert(root, newKey);
　}
　return true;
}

template<typename T>
bool tree<T>::insert(node<T>*& fact, const T& newKey) {
　if ( fact == 0 ) {
　　fact = new node<T>(newKey);
　} else {
　　if ( fact->key == newKey ) {
　　　return false;
　　} else {
　　　return insert( ( fact->key > newKey ) ? fact->left : fact->right, newKey);
　　}
　}
　return true;
}

template<typename T>
void tree<T>::print(const node<T>* fact, std::ostream& out) {
　if ( fact != 0 ) {
　　print(fact->left, out);
　　out << fact->key << ' ';
　　print(fact->right, out);
　}
}

int main() {
　tree<int> t;
　t.insert(4);
　t.insert(2);
　t.insert(6);
　t.insert(8);
　t.insert(0);
　t.insert(9);
　t.insert(1);
　t.insert(5);
　t.insert(3);
　t.insert(7);
　t.print(std::cout);
}

お礼

ありがとうございます。

＞bool tree<T>::insert(node<T>*& fact, const T& newKey)
nodeを参照渡しにしましたらうまく動作しました。

訂正後のソースは前の回答者へのお礼の欄に載せてあります。