Я получаю переполнение стека (поток 1: EXC_BAD_ACCESS (code = 2, address = 0x7ffeef3ffff8)) при печати двоичного дерева поиска. После некоторой проверки кажется, что корень дерева становится нулевым перед запуском метода inOrderTraversalRecursive
. Не уверен, почему корень становится нулевым. Я знаю о ресурсах это иэто, но пока они мне не помогли. Спасибо, что нашли время ответить на мой вопрос.
в файл main.m
#import <Foundation/Foundation.h>
@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
@property (nonatomic,strong) BSTNode *root;
- (void)insertNode:(int)value;
-(void)inOrderTraversal;
@end
@implementation BST
-(instancetype)init{
if (self = [super init]) {
self.root = [self initializeTreeNode];
}
return self;
}
- (BSTNode *)initializeTreeNode {
// By default, |data| is 0, |left| is nil, |right| is nil
return [[BSTNode alloc] init];
}
- (void)insertNode:(int)value {
self.root = [self insertNode:_root withData:value];
}
- (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)inOrderTraversal {
[self inOrderTraversalRecursive:self.root];
}
-(void)inOrderTraversalRecursive:(BSTNode *)root {
// inOrder = left - root - right
[self inOrderTraversalRecursive:root.left];
NSLog(@"%d",root.data);
[self inOrderTraversalRecursive:root.right];
}
@end
внутри main.m
int main(int argc, const char * argv[]) {
@autoreleasepool {
BST *bst = [BST new];
[bst insertNode:50];
[bst insertNode:30];
[bst insertNode:20];
[bst insertNode:40];
[bst insertNode:70];
[bst insertNode:60];
[bst insertNode:80];
[bst inOrderTraversal];
}
return 0;
}
PS.
Я разработал классы BST и BSTNode на основе Java-реализации BST от geeksforgeeks. Какова правильная реализация BST (вставка, поиск, печать, удаление) в Objective-C? Кажется, нигде не могу найти.
Мне не хватало проверки nil в функции обхода.
-(void)inOrderTraversalRecursive:(BSTNode *)root {
if (!root) {
return;
}
[self inOrderTraversalRecursive:root.left];
NSLog(@"%d",root.data);
[self inOrderTraversalRecursive:root.right];
}
(Thread 1: EXC_BAD_ACCESS (code=2, address=0x7ffeef3ffff8))
означает, что вы обращаетесь к блоку памяти, который уже освобожден. Это означает, что ваш объект был освобожден из памяти, и вы больше не можете получить к нему доступ. Вот почему плохой доступ.
Кроме того, это может означать, что вы держите dangling pointer
, указывающий на адрес памяти, который больше не существует.
Спасибо за объяснение. Судя по приведенному выше коду, что могло вызвать зависший указатель? Очень любопытный.