ios - 需要有关 Objective-C 中二进制搜索树实现的指导

Question

我有一个二叉树的部分实现，但无法正常工作。我相信我缺少有关 Objective-C 中结构内存管理的基础知识，但不确定它是什么(除了 malloc 之外)。当我尝试基于结构创建一个新的树节点时，我得到

Thread 1: EXC_BAD_ACCESS (code=1, address=0x0)

这让我相信我没有为这个结构指针创建内存位置。在 Objective-C 中执行此操作的正确方法是什么？ (下面的代码)

感谢您花时间回复。从逻辑角度来看，该代码似乎是正确的，因此不确定这里的问题是什么。

编辑 我根据 @trungduc 的回复修改了源代码。但现在我在 printDescription 方法中遇到堆栈溢出 问题:

Thread 1: EXC_BAD_ACCESS (code=2, address=0x7ffeef3fffe8) // on line [self printDescription:root.left];

附言。 我确实看到了this question但没有帮助。我还看到了 this repo但我不确定对一些实现细节是否满意，所以我最终没有遵循它。有谁知道关于如何在 Objective-C 中制作树和图的任何好的指南/教程？

Main.m

#import <Foundation/Foundation.h>

// BSTNode is an Objective-C class
@interface BSTNode : NSObject

@property (nonatomic, assign) int data;
@property (nonatomic, strong) BSTNode *left;
@property (nonatomic, strong) BSTNode *right;

@end

@implementation BSTNode

@end

@interface BST: NSObject

- (BSTNode *)insertNode:(BSTNode *)root withData:(int)data;
- (void)printDescription:(BSTNode *)root;

@end

@implementation BST

- (BSTNode *)initializeTreeNode {
    // By default, |data| is 0, |left| is nil, |right| is nil
    return [[BSTNode alloc] init];
}

- (BSTNode *)insertNode:(BSTNode *)root withData:(int)data {
    if(!root) {
        root = [self initializeTreeNode];
        root.data = data;
    } else if (root.data >= data) {
        root.left = [self insertNode:root.left withData:data];
    } else {
        root.right = [self insertNode:root.right withData:data];
    }

    return root;
}

- (void)printDescription:(BSTNode *)root {
    // in order left - root - right
    [self printDescription:root.left];
    NSLog(@"%d",root.data);
    [self printDescription:root.right];
}

@end

在主方法内部:

int main(int argc, const char * argv[]) {
    @autoreleasepool {

        BST *bst = [[BST alloc] init];;
        BSTNode *root = [[BSTNode alloc]init];
        [bst insertNode:root withData:20];
        [bst insertNode:root withData:15];
        [bst insertNode:root withData:25];
        [bst printDescription:root];
   }
    return 0;
}

Answer 1

您崩溃是因为您调用了 node->data 而 node 为 NULL。

在这种情况下，我建议将 BSTNode 定义为一个 Objective-C 类。您可以在下面尝试我的代码。

// BSTNode is an Objective-C class
@interface BSTNode : NSObject

@property (nonatomic, assign) int data;
@property (nonatomic, strong) BSTNode *left;
@property (nonatomic, strong) BSTNode *right;

@end

@implementation BSTNode

@end

@interface BST: NSObject

- (BSTNode *)insertNode:(BSTNode *)root withData:(int)data;
- (void)printDescription:(BSTNode *)root;

@end

@implementation BST

- (BSTNode *)initializeTreeNode {
  // By default, |data| is 0, |left| is nil, |right| is nil
  return [[BSTNode alloc] init];
}

- (BSTNode *)insertNode:(BSTNode *)root withData:(int)data {
  if(!root) {
    root = [self initializeTreeNode];
    root.data = data;
  } else if (root.data >= data) {
    root.left = [self insertNode:root.left withData:data];
  } else {
    root.right = [self insertNode:root.right withData:data];
  }

  return root;
}

- (void)printDescription:(BSTNode *)root {
  if (!root) {
      return;
  }

  // in order left - root - right
  [self printDescription:root.left];
  NSLog(@"%d",root.data);
  [self printDescription:root.right];
}

@end