关于Objective-C中二进制搜索树实现的需求指导 [英] Need direction about Binary Search Tree implementation in Objective-C

问题描述

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

I have a partial implementation of a binary tree that doesn't work properly. I believe I am missing fundamental knowledge about struct memory management in objective-c but not sure what it is(besides malloc). When I try to create a new tree node based on a struct I get

线程1:EXC_BAD_ACCESS(代码= 1，地址= 0x0)

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

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

which led me to believe I didn't create a memory location for this struct pointer. What is the proper way of doing this in Objective-C? (Code in below)

感谢您抽出宝贵的时间来回复.从逻辑角度来看，该代码似乎是正确的，因此不能确定问题出在哪里.

Thank you for taking the time to respond. The code seems correct from the logic perspective so not sure what the issue is here.

编辑 我已经根据@trungduc的响应修改了源代码.但是现在我在printDescription方法中出现堆栈溢出 问题:

EDIT I've modified the source code based on @trungduc 's response. But now I am getting a stack overflow in the printDescription method issue:

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

PS. 我确实看到了这个问题，但是没有帮助.我还看到了此仓库，但是我不确定对某些实施细节感到满意，所以我最终没有跟着它.有谁知道如何在Objective-C中做树和图的任何好的指南/教程?

PS. I did see this question but didn't help. I also saw this repo but I am not sure happy with some of the implementation details so I ended up not following it. Does anyone know any good guides/tutorials on how to do trees and graphs in 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

以及main方法内:

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;
}

推荐答案

由于在node为NULL时调用了node->data，因此崩溃.

You got crash because you called node->data while node is NULL.

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

In this case, I suggest to define BSTNode as an Objective-C class. You can try my code below.

// 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中二进制搜索树实现的需求指导的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！