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

到目前为止，我有以下类(class):

• 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)如下所示:

@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 数据或对另一个节点的引用？

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

最佳答案

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

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

Node *TreeRoot;

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

函数式 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);
      }
   }
}

您现在可以看到您的方法是上述两种方法的混合体。两者都有效，但由于您使用的是 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 进行内存管理，您需要插入适当的保留/释放调用。

希望能帮助您解决问题。

关于objective-c - Objective-C 中的二叉树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12066057/