13

我正在学习算法和数据结构并训练我正在尝试使用objective-c设计和实现二叉树。

到目前为止，我有以下课程：

  • main- 供测试用
  • Node- 树的节点
  • 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 数据或对另一个节点的引用？

希望这是有道理的。谢谢！

4

4 回答 4

28

您的代码混合了两种常见的任务方法，因此出现了问题。您还使用了一种抽象数据类型(ADT) 类型方法，而不是面向对象的方法，因此需要考虑三种方法。

在这两种 ADT 方法中，您的树都由对其根的引用表示，在 Objective-C 中，这可能存储在实例变量中：

Node *TreeRoot;

另请注意，这两种算法都使用字段引用，a->b而不是属性引用，a.b这是因为前者引用了变量，而第二种算法需要传递对变量的引用。

函数式 ADT：按值传递和分配结果

在这种方法中，一个节点被插入到树中并返回一个修改过的树，该树被分配回来，例如插入 a 的顶级调用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);
      }
   }
}

您现在可以看到您的方法是上述两种方法的混合。两者都是有效的，但是当您使用 Objective-C 时，采用第三种方法可能会更好：

面向对象的 ADT

这是过程 ADT 的一种变体 - 而不是将变量传递给过程，变量，现在称为object，拥有一个更新自身的方法。这样做意味着您必须在调用插入节点之前测试空（子）树，而前两种方法在调用中进行测试。所以现在我们有了以下方法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 进行内存管理，则需要插入适当的保留/释放调用。

希望能帮助你解决问题。

于 2012-08-22T05:19:34.937 回答
27

首先，不要写你要采取的方法Node **。这只是令人困惑。

其次，考虑它应该如何工作。向自己描述它应该如何在非常抽象的层面上工作。将该描述直接翻译成代码，并在必要时创造新的（尚未编写的！）消息。如果有一些步骤你还不知道怎么做，只需将它们放到你稍后会写的新消息中。我会引导你完成它。

大概您希望公共 APIBinaryTree包含此消息：

@interface BinaryTree

- (void)insertValue:(int)value;

那么如何实施insertValue:呢？假装你是BinaryTree对象。您对插入值需要做什么的高级描述是什么？你想创建一个新的Node. 然后你想把那个新的Node插入自己。将该描述直接翻译成代码：

@implementation BinaryTree {
    Node *root_; // root node, or nil for an empty tree
}

- (void)insertValue:(int)value {
    Node *node = [[Node alloc] initWithData:value];
    [self insertNode:node];
}

现在考虑如何进行插入。好吧，如果您是一棵空树，则您的root_值为 nil，您可以将其设置为新节点。否则，您可以只要求您的根节点将新节点插入到他自己的下面。将该描述直接翻译成代码：

- (void)insertNode:(Node *)node {
    if (root_ == nil) {
        root_ = node;
    } else {
        [root_ insertNode:node];
    }
}

现在假装你是一个Node。你被要求Node在自己下面插入一个新的。你怎么做呢？您必须将新节点的值与您的值进行比较。如果新节点的值小于您的值，您希望在左侧插入新节点。否则，您想将其插入右侧。将该描述直接翻译成代码：

@implementation Node

- (void)insertNode:(Node *)node {
    if (node.data < self.data) {
        [self insertNodeOnLeftSide:node];
    } else {
        [self insertNodeOnRightSide:node];
    }
}

现在您仍然是Node，并且您被要求在左侧插入一个新节点。你怎么做呢？好吧，如果您的左侧还没有孩子，只需将新节点用作您的左孩子。否则，你要求你的左孩子在他自己下面插入新节点。将该描述直接翻译成代码：

- (void)insertNodeOnLeftSide:(Node *)node {
    if (self.left == nil) {
        self.left = node;
    } else {
        [self.left insertNode:node];
    }
}

我将把实现insertNodeOnRightSide:作为练习留给读者。;^)

于 2012-08-22T04:55:39.163 回答
0

(Node **)node是指向对象指针的指针，因此node.something无效，因为您是对远离对象的引用。

但(*node).something会工作。

补充说明：
你当初调用这个方法的时候：-(void)insertNodeByRef:(Node **)node forRoot:(Node **)root 你是怎么调用的？
从您在评论中发布的错误来看，您正在做的事情是：
Node *n = [[Node alloc] init];
[aNode insertNodeByRef:n forRoot:aRoot];

当您的方法签名状态需要这样调用它时：
[aNode insertNodeByRef:&n forRoot:&aRoot];
将指针的地址传递给对象。

我这样说是因为您的错误现在表明您正在发送Node *而不是发送Node **2 个不同的东西。（（Incompatible pointer types sending 'Node *' to parameter of type 'Node **'）我已经删除了 2 * 之间的 __autoreleasing，它掩盖了错误消息。）
换句话说，pointer to an object当您的方法要求 a 时，您正在传递 a pointer TO A pointer to an object。

于 2012-08-22T03:53:47.980 回答
0

在我看来，您的代码有很多逻辑错误。也许考虑查看指针到指针是什么，以确保您正在设计所需的效果。同样，您需要取消引用 node/root 才能在正常状态下访问它们。否则，错误有效，Node** 不是结构或联合类型。

于 2012-08-22T04:01:35.943 回答