到目前为止,我有以下课程：
>主要 – 用于测试
>节点 – 树的节点
> BinaryTree – 用于与树相关的所有方法
我实现的BinaryTree类中的第一种方法之一是insertNode：forRoot :.
- (void)insertNodeByRef:(Node **)node forRoot:(Node **)root{
if (head == NULL) {
head = *node;
}
// Case 2 root is null so can assign the value of the node to it
if (root == NULL) {
root = node;
} else {
if (node.data > root.data) { // to the right
[self insertNode:node forRoot:root.right];
} else if (node.data < root.data) { //or to the left
[self insertNode:node forRoot:root.left];
}
}
}
Node类的接口如下所示：
@interface Node : NSObject @property(nonatomic,assign) int data; @property(nonatomic,strong) Node * right; @property(nonatomic,strong) Node * left; @end
我的问题是,如果我传递Node作为参考,我不知道如何访问Node类成员变量.每当我尝试访问节点属性(如数据,左或右)时,我收到以下错误消息：
Member reference base type 'Node *__autoreleasing *' is not a structure or union
所以我的问题是：
如何访问这些属性(数据,左或右),并使用它们存储int数据或引用到另一个Node？
希望是有道理的.谢谢！
解决方法
在这两个ADT方法中,您的树都以对其根的引用表示,在Objective-C中,这可能存储在一个实例变量中：
Node *TreeRoot;
还要注意,这两种算法都使用字段引用a-> b而不是属性引用a.b – 这是因为前者引用了变量,第二种算法需要传递对变量的引用.
功能ADT：传递值并分配结果
在这种方法中,将节点插入到树中,并且返回被修改的树,例如.插入节点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);
}
}
}
您现在可以看到,您的方法是上述两种方法的混合体.两者都是有效的,但是正如您使用Objective-C一样,最好采用第三种方法：
面向对象的ADT
这是程序ADT的一个变体 – 而不是将变量传递给一个过程,变量(现在称为对象)拥有一个更新自身的方法.这样做意味着您必须在进行呼叫插入节点之前测试一个空(子)树,而前两种方法在调用中进行测试.所以现在我们在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进行内存管理,则需要插入适当的保留/释放调用.
希望能帮助你整理事情.
