Objective-C中的二叉树 [英] Binary Tree in Objective-C
问题描述
我正在学习算法和数据结构,并且训练我正在尝试使用objective-c设计和实现二叉树。
I am learning algorithms and data structures and to train I am trying to design and implement a binary tree using objective-c.
到目前为止,我有以下课程:
So far I have the following Classes:
-
main
- 用于测试 -
节点
- 树节点 -
BinaryTree
- 适用于与树相关的所有方法
main
- for testingNode
- node of treeBinaryTree
- for all methods related to the tree
其中一个我实现的 BinaryTree
类中的第一个方法是 insertNode:forRoot:
。
One of the first methods in BinaryTree
class I implemented is 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];
}
}
}
<$> c $ c>节点类看起来像:
@interface Node : NSObject
@property(nonatomic, assign) int data;
@property(nonatomic, strong) Node * right;
@property(nonatomic, strong) Node * left;
@end
我的问题是我不知道怎么做如果我将Node作为引用传递,则访问Node类成员变量。每当我尝试访问节点属性(如数据,左或右)时,我收到以下错误消息:
My problem is that I don't know how to access the Node class member variables if I am passing Node as a reference. Whenever I try to access the node properties (like data, left or right) I am getting the following error message:
Member reference base type 'Node *__autoreleasing *' is not a structure or union
所以我的问题是:
如何访问这些属性(数据,左或右)并使用它们存储int数据或引用另一个节点?
So my questions is: how can I access those properties (data, left or right) and use them to store either int data or reference to another Node?
希望它有意义。谢谢!
推荐答案
您的代码混合了两种常见的任务方法,因此存在问题。您还使用抽象数据类型(ADT)类型方法,而不是面向对象的方法,因此有三种方法需要考虑。
Your code is mixing two common approaches to the task, hence the problem. You are also using an abstract data type (ADT) type approach, rather than an object-oriented one, so there are three approaches to consider.
在两种ADT方法中,您的树由对其根的引用表示,在Objective-C中,这可能存储在实例变量中:
In both ADT approaches your tree is represented by a reference to its root, in Objective-C this is probably stored in an instance variable:
Node *TreeRoot;
另请注意,这两种算法都使用字段引用, a-> b
,而不是属性引用, ab
- 这是因为前者引用变量而第二种算法需要传递对变量的引用。
Note also that both of these algorithms use field references, a->b
, rather than property references, a.b
- this is because the former references a variable and the second algorithm requires passing a reference to a variable.
功能性ADT:按值传递并分配结果
在此方法中,将节点插入树中,并返回已修改的树,该树将被分配回来,例如插入节点
nodeToInsert
的顶级调用将是:
In this approach a node is inserted into a tree and a modified tree is returned which is assigned back, e.g. the top-level call to insert a Node
nodeToInsert
would be:
TreeRoot = insertNode(nodeToInsert, TreeRoot);
和 insertNode
函数如下所示: / p>
and the insertNode
function looks like:
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;
}
}
请注意,在这种方法中,如果是非-empty(sub)tree算法对变量执行冗余赋值 - 赋值是变量中已有的值...因此有些人更喜欢:
Note that in this approach in the case of a non-empty (sub)tree the algorithm performs a redundant assignment into a variable - the assigned value is what is already in the variable... Because of this some people prefer:
程序ADT:传递参考
在这种方法中,保存(子)树根的变量是通过 - 引用,而不是传递的值,并根据需要由被调用的过程进行修改。例如。顶级调用将是:
In this approach the variable holding the root of the (sub)tree is passed-by-reference, rather than its value being passed, and is modified by the called procedure as needed. E.g. the top-level call would be:
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时,采用第三种方法可能更好:
You can now see that your method is a mixture of the above two approaches. Both are valid, but as you are using Objective-C it might be better to take the third approach:
面向对象的ADT
这是程序ADT的变体 - 而不是将变量传递给过程变量,现在称为对象,拥有方法更新自己。这样做意味着您必须在调用插入节点之前测试空(子)树,而前两个方法在调用中进行测试。所以现在我们在 Node
中有方法:
This is a variation of the procedural ADT - rather than pass a variable to a procedure the variable, now called an object, owns a method which updates itself. Doing it this way means you must test for an empty (sub)tree before you make a call to insert a node, while the previous two approaches test in the call. So now we have the method in 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;
}
}
你还需要更改顶级电话来做空树的相同测试:
You also need to change the top level call to do the same test for an empty tree:
if(TreeRoot != nil)
[TreeRoot insert:nodeToInsert];
else
TreeRoot = nodeToInsert;
最后一点 - 如果您使用MRC而不是ARC或GC进行内存管理我需要插入适当的保留/释放电话。
And a final note - if you are using MRC, rather than ARC or GC, for memory management you'll need to insert the appropriate retain/release calls.
希望能帮助你解决问题。
Hope that helps you sort things out.
这篇关于Objective-C中的二叉树的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!