再帰によるC ++バイナリ検索ツリーの挿入
-
03-07-2019 - |
質問
だから私のコードは以下です。エラーは発生せず、ノード内のすべてが正常に配置されます。しかし、私のデバッグ文に基づいて、何かが挿入されるたびに、ルートを見つけています。それが正しいかどうかはわかりません。しかし、割り当ての出力ファイルによると、ツリーの高さ、トラバーサルに関しては私の答えは異なり、リーフカウント機能にまだ問題があります。しかし別の話。
デバッグ文に基づいて、すべてが適切な場所に向かっているように見えます。しかし、私は新鮮な目が必要かもしれないと考えています。 Inorder、preorder、postorderに影響するのは、実際にノードを処理する場所の問題だけなので、トラバーサルがどのように変化するかはまったくわかりません。
template <class T>
void BT<T>::insert(const T& item)
{
Node<T>* newNode;
newNode = new Node<T>(item);
insert(root, newNode);
}
template <class T>
void BT<T>::insert(struct Node<T> *&root, struct Node<T> *newNode)
{
if (root == NULL)
{
cout << "Root Found" << newNode->data << endl;
root = newNode;
}
else
{
if (newNode->data < root->data)
{
insert(root->left, newNode);
cout << "Inserting Left" << newNode-> data << endl;
}
else
{
insert(root->right, newNode);
cout << "Inserting Right" << newNode->data << endl;
}
}
}
挿入が実際にうまくいく場合のために、私の高さ関数は次のとおりです。
template <class T>
int BT<T>::height() const
{
return height(root);
}
template <class T>
int BT<T>::height(Node<T>* root) const
{
if (root == NULL)
return 0;
else
{
if (height(root->right) > height(root->left))
return 1 + height(root-> right);
return 1 + height(root->left);
}
}
解決
デバッグ文の文言を変更する必要があります
(ルートノードではなく)実際に読み取る必要があります
cout << "Leaf Node Found" << newNode->data << endl;
node-&gt; leftまたはnode-&gt; rightを使用した呼び出しが中間ノードになると、最初に呼び出されたときにのみルートになります。
height()を記述するには、次のようにします。
template <class T>
int BT<T>::height(Node<T>* root) const
{
if (root == NULL) {return 0;}
return 1 + max(height(root->left),height(root->right));
}
他のヒント
ルートの初期化をnullにして開始する必要があります。また、*&amp; node in;を渡します。 * nodeである必要があります。それ以外の場合は、アドレスへのポインタを渡します(または、このコンテキストではどちらが正しいかわかりませんが、両方とも正しくありません)。参照ではなく、Nodeへのポインターを渡す必要があります。
template <class T>
void BT<T>::BT()
{ root = 0;}
template <class T>
void BT<T>::insert(const T& item)
{
Node<T>* newNode;
newNode = new Node<T>(item);
insert(root, newNode);
}
template <class T>
void BT<T>::insert(struct Node<T> *root, struct Node<T> *newNode)
{
/*stuff*/
}
@Vlion:
左/右/ルートポインターへのポインター(つまり、ダブルポインター)である必要があります。そのため、投稿されたコードは正確ですが、多少不明瞭です。
@Doug:
挿入関数の変更を検討してください:
template <class T>
void BT<T>::insert(struct Node<T>** root, struct Node<T>* newNode)
{
if (*root == NULL)
{
cout << "Root Found" << newNode->data << endl;
*root = newNode;
}
最初のパラメーターとして渡されるポインター(または、むしろ、最初のパラメーターとしてアドレスが渡されるポインター)を変更するという意図が明確になります。 。
次のような、このinsert()の呼び出し:
insert(&root, newNode);
は、ポインタの値を変更するというあなたの意図も反映します。ただし、これはスタイルの問題であるため、変更したくない場合は議論できません。
ツリーが「正しい」かどうかの確認に関しては、それを引き出して自分で見てみませんか?次のようなもの:
template class<T>
void printTree(struct Node<T>* node, int level=0)
{
if (!node) {
for (int i=0; i<level; ++i)
cout << " ";
cout << "NULL" << endl;
return;
}
printTree(node->left, level+1);
for (int i=0; i<level; ++i)
cout << " ";
cout << node->data << endl;
printTree(node->right, level+1);
}
(テストされていないコード)