あなたのコードは、タスクに対する 2 つの一般的なアプローチを混在させているため、問題が発生しています。オブジェクト指向ではなく、抽象データ型(ADT) 型のアプローチも使用しているため、考慮すべき 3 つのアプローチがあります。
どちらの ADT アプローチでも、ツリーはそのルートへの参照によって表されます。Objective-C では、これはおそらくインスタンス変数に格納されます。
Node *TreeRoot;
また、これらのアルゴリズムはa->bどちらも、プロパティ参照ではなくフィールド参照を使用することに注意してください。a.bこれは、前者が変数を参照し、2 番目のアルゴリズムが変数への参照を渡す必要があるためです。
Functional ADT: 値渡しと代入結果
このアプローチでは、ノードがツリーに挿入され、変更されたツリーが返されて割り当てられます。たとえば、挿入するトップレベルの呼び出しは次のNode nodeToInsertようになります。
TreeRoot = insertNode(nodeToInsert, TreeRoot);
insertNode関数は次のようになります。
Node *insertNode(Node *node, Node *root)
{
if(root == nil)
{ // empty tree - return the insert node
return node;
}
else
{ // non-empty tree, insert into left or right subtree
if(node->data > root->data) // to the right
{
root->right = insertNode(node, root->right);
}
else if(node->data < root->data)//or to the left
{
root->left = insertNode(node, root->left);
}
// tree modified if needed, return the root
return root;
}
}
このアプローチでは、空でない (サブ) ツリーの場合、アルゴリズムは変数への冗長な割り当てを実行することに注意してください。割り当てられた値は、変数に既に含まれているものです...このため、一部の人々は好みます:
手続き型 ADT: 参照渡し
このアプローチでは、(サブ) ツリーのルートを保持する変数は、その値が渡されるのではなく、参照によって渡され、必要に応じて呼び出されたプロシージャによって変更されます。たとえば、最上位の呼び出しは次のようになります。
insertNode(nodeToInsert, &TreeRoot); // & -> pass the variable, not its value
手順は次のようになりinsertNodeます。
void insertNode(Node *node, Node **root)
{
if(*root == nil)
{ // empty tree - insert node
*root = node;
}
else
{ // non-empty tree, insert into left or right subtree
Node *rootNode = *root;
if(node->data > rootNode->data) // to the right
{
insertNode(node, &rootNode->right);
}
else if(node->data < rootNode->data)//or to the left
{
insertNode(node, &root->left);
}
}
}
あなたの方法が上記の 2 つのアプローチを組み合わせたものであることがわかります。どちらも有効ですが、Objective-C を使用しているため、3 番目のアプローチを採用することをお勧めします。
オブジェクト指向ADT
これは、手続き型 ADT のバリエーションです。変数を手続きに渡すのではなく、現在objectと呼ばれている変数が、それ自体を更新するメソッドを所有しています。このようにすることは、ノードを挿入する呼び出しを行う前に空の (サブ) ツリーをテストする必要があることを意味しますが、前の 2 つのアプローチは呼び出しでテストします。これで、メソッドがNode次のようになりました。
- (void) insert:(Node *)node
{
if(node.data > self.data) // using properties, could also use fields ->
{
if(self.right != nil)
[self.right insert:node];
else
self.right = node;
}
else if(node.data < rootNode.data)
{
if(self.left != nil)
[self.left insert:node];
else
self.left = node;
}
}
空のツリーに対して同じテストを行うには、最上位の呼び出しも変更する必要があります。
if(TreeRoot != nil)
[TreeRoot insert:nodeToInsert];
else
TreeRoot = nodeToInsert;
最後に、メモリ管理に ARC や GC ではなく MRC を使用している場合は、適切な保持/解放呼び出しを挿入する必要があります。
物事を整理するのに役立つことを願っています。