如何找到二叉树的最小值？

Question

我正在寻找二叉树的最小值。每次我运行我的代码时，我都会得到一个很长的 5 位数字，例如“32675”。我很确定我对指针的理解是错误的，但我并不肯定。如果我能得到一些建议，我将不胜感激。谢谢！

节点定义

@interface Node:NSObject {
    @property (nonatomic, strong) Node *left;
    @property (nonatomic, strong) Node *right;
    @property (nonatomic, assign) int *value;
}

-(id)initWithValue:(int)val {
    self = [super init];
    if(self) {
        self.value = &(val);
        self.left = nil;
        self.right = nil;
    }
    return self;
}

为树插入算法

-(void)insertValue:(int)value {
    Node *node = [[Node alloc] initWithValue:value];
    [self insertNode:node];
}

-(void)insertNode:(Node *)node {
    if (root == nil) {
        root = node;
    } else {
        [node insertNode:node];
    }
}

为节点插入算法

-(void)insertNode:(Node *)node{
    if (node.value < self.value) {
        [self insertOnLeft:node];
    } else {
        [self insertOnRight:node];
    }
}

-(void)insertOnLeft:(Node *)node {
    if (self.left == nil) {
        self.left = node;
    } else {
        [self.left insertNode:node];
    }
}

-(void)insertOnRight:(Node *)node {
    if (self.right == nil) {
        self.right = node;
    } else {
        [self.right insertNode:node];
    }
}

3 个值进入我的树：

[tree insertValue:4];
[tree insertValue:6];
[tree insertValue:2];

int min = [tree findMinimum];

调用了Tree的findMinimum方法

-(int)findMinimum {
    assert(root != nil);
    return [root findMinimum];
}

哪个调用根的findMinimum - 根是一个节点

-(int)findMinimum {
    Node *node = self;
    int min = 0;
    while (node != nil) {
        min = *(node.value);
        node = node.left;
    }
    return min;
}

Answer 1

初始化程序中指向参数的指针的赋值将不起作用。除非你有充分的理由不这样做，否则实际上将 int 分配到 Node 结构中，方法是将其声明为 int，而不是 int *。所以你的初始化器看起来像这样：

-(id)initWithValue:(int)val {
    self = [super init];
    if(self) {
        self.value = val;
    }
    return self;
}

EDIT 如果您没有对插入进行排序（我在 OP 中遗漏了），您可以按如下方式递归搜索最小值：

-(int)findMinimum {
    if (self.left && self.right)
        return MIN([self.left findMinimum], [self.right findMinimum]);
    else if (self.left)
        return [self.left findMinimum];
    else if (self.right)
        return [self.right findMinimum];
    else
        return self.value;
}

Answer 2

您不是用整数而是用堆栈地址填充您的树，这些地址对于此代码立即无效：

self.value = &(val);

这里val是一个参数变量，一旦方法returns就会消失。只应在极少数情况下获取其地址，并且该地址不应 永远不会 存储在比 val.

更长寿的位置

将 Node 的 value 属性的类型更改为 int 并删除地址 (&) 和间接寻址 (*) 与属性.

关联

HTH

如何找到二叉树的最小值？

How do I find the minimum value of a binary tree?

tree

objective-c

nodes