Objective-C中的二进制树

在这两个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;

最后一个注释 – 如果您使用R_451_11845@RC而不是ARC或GC进行内存管理,则需要插入适当的保留/释放调用.

希望能帮助你整理事情.