您的代码混合了两种常见的任务方法,因此出现了问题。您还使用抽象数据类型(ADT)类型的方法,而不是面向对象一,因此需要考虑三种方法。
在这两种 ADT 方法中,你的树都是通过对其根的引用来表示的,在 Objective-C 中,这可能存储在实例变量中:
Node *TreeRoot;
另请注意,这两种算法都使用字段引用,a->b
,而不是属性引用,a.b
- 这是因为前者引用了variable第二种算法需要传递对变量的引用。
函数式 ADT:按值传递并分配结果
在这种方法中,一个节点被插入到一棵树中,并且一个modified返回分配回来的树,例如插入的顶级调用Node
nodeToInsert
将会:
TreeRoot = insertNode(nodeToInsert, TreeRoot);
and the 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
and the 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);
}
}
}
您现在可以看到您的方法是上述两种方法的混合。两者都是有效的,但当您使用 Objective-C 时,最好采用第三种方法:
面向对象的ADT
这是过程 ADT 的变体 - 不是将变量传递给过程,而是将变量(现在称为变量)传递给过程。object,拥有一个method它会自行更新。这样做意味着您必须测试空(子)树before您调用插入节点,而前两种方法在调用中进行测试。所以现在我们有这个方法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;
最后一点 - 如果您使用 MRC 而不是 ARC 或 GC 进行内存管理,您将需要插入适当的保留/释放调用。
希望能帮助您解决问题。