Objective-C中的二叉树

Question

我正在学习算法和数据结构,并训练我正在尝试使用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数据或引用另一个节点？

希望它有意义.谢谢!

Answer 1

您的代码混合了两种常见的任务方法,因此存在问题.您还使用抽象数据类型(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的变体 - 而不是将变量传递给过程,变量(现在称为对象)拥有一个更新自身的方法.这样做意味着您必须在调用插入节点之前测试空(子)树,而前两个方法在调用中进行测试.所以现在我们有了这样的方法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进行内存管理,则需要插入适当的保留/释放调用.

希望能帮助您解决问题.

Answer 2

首先,不要写你的方法Node **.这只是令人困惑.

其次,考虑它应该如何运作.自己描述它应该如何在一个非常抽象的层面上工作.将该描述直接翻译成代码,在必要时发明新的(尚未编写的)消息.如果有一些步骤你不知道该怎么做,那就把它们放到你以后写的新消息上.我会引导你完成它.

据推测,您希望公共API BinaryTree包含以下消息:

@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_就是零,你可以将它设置为新节点.否则,您可以让您的根节点在他自己下面插入新节点.将该描述直接翻译成代码:

- (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:作为练习留给读者.; ^)