需要有关 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];

PS。我确实看到了 this question but didn't help. I also saw this repo，但我对某些实现细节不太满意，所以我最终没有遵循它。有谁知道 guides/tutorials 如何在 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-Cclass。您可以在下面尝试我的代码。

// 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

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

Need direction about Binary Search Tree implementation in Objective-C

ios

objective-c

data-structures

binary-search-tree

recursive-datastructures