Binary Search Tree(二叉排序树)

示例

特点

BinarySearchTree(BST)是一种特殊的BinaryTree,其特点是
1 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3 左、右子树也分别为二叉排序树；

向二叉排序树中插入值的步骤

1 如果当前节点为空(只有没有根节点这种情况)，则插入节点,结束
2 如果插入值小于当前节点的值

• 如果左子树不存在，则将插入值对应的节点设为当前节点的leftChild，结束
• 如果左子树存在，则对左子树执行步骤123

3 如果插入值大于当前节点的值

• 如果右子树不存在，则将插入值对应的节点设为当前节点的rightChild，结束
• 如果右子树存在，则对左子树执行步骤123

示例

代码创建的二叉排序树结构见文章顶部的示例图

@interface BinarySortTree : NSObject

@property(nonatomic, assign) NSInteger value;

@property(nonatomic, assign, readonly) NSUInteger count;

@property(nonatomic, strong) BinarySortTree *leftChild;

@property(nonatomic, strong) BinarySortTree *rightChild;

- (void)insertValue:(NSInteger)value;

- (NSString *)traverseInOrder;

- (NSString *)traversePreOrder;

- (NSString *)traversePostOrder;

- (BinarySortTree *)search:(NSInteger)value;

@implementation BinarySortTree

- (void)insertValue:(NSInteger)value
{
    
    if (value <= 0) return;
    
    //当树没有一个节点的时候，把value当成根节点
    if (!self.leftChild && !self.rightChild && _value == 0) {
        _value = value;
        return;
    }
    
    if (value == _value) {
        return;
    }
    
    if (value < _value) {
        //leftChild
        if (_leftChild) {
            [_leftChild insertValue:value];
        } else {
            BinarySortTree *tree = [BinarySortTree new];
            tree.value = value;
            _leftChild = tree;
        }
    } else {
        //rightChild
        if (_rightChild) {
            [_rightChild insertValue:value];
        } else {
            BinarySortTree *tree = [BinarySortTree new];
            tree.value = value;
            _rightChild = tree;
        }
    }
}

- (NSUInteger)count
{
    return [self.leftChild count] + (_value > 0 ? 1 : 0) + [self.rightChild count];
}
//遍历的时间复杂度为O(n)，因为每一个节点都会被访问
//顺序遍历，从小到大。先访问leftChild，然后访问当前节点，最后访问rightChild的顺序
- (NSString *)traverseInOrder
{
    if (_value == 0) {
        return @"";
    }
    
    return [NSString stringWithFormat:@"%@ %ld %@", [_leftChild traverseInOrder] ?: @"", _value, [_rightChild traverseInOrder] ?: @""];
}

//先访问节点，然后访问leftChild，最后访问rightChild的顺序
- (NSString *)traversePreOrder
{
    if (_value == 0) return @"";
    
    return [NSString stringWithFormat:@"%ld %@ %@",  _value, [_leftChild traversePreOrder] ?: @"", [_rightChild traversePreOrder] ?: @""];
}

//先访问leftChild，然后访问rightChild，最后访问当前节点的顺序
- (NSString *)traversePostOrder
{
    if (_value == 0) return @"";
    
    return [NSString stringWithFormat:@"%@ %@ %ld",  [_leftChild traversePostOrder] ?: @"", [_rightChild traversePostOrder] ?: @"" , _value];
}

//查找的平均时间复杂度为O(log n)，因为每次查找的时候只会在一个子树中查找
- (BinarySortTree *)search:(NSInteger)value
{
    if (value <= 0) {
        return nil;
    }
    
    if (_value == value) {
        return self;
    } else if (value < _value) {
        return [self.leftChild search:value];
    } else {
        return [self.rightChild search:value];
    }
}

@end

测试

- (void)binarySortTreeTest
{
    BinarySortTree *tree = [BinarySortTree new];
    
    [tree insertValue:7];
    [tree insertValue:10];
    [tree insertValue:2];
    [tree insertValue:1];
    [tree insertValue:5];
    [tree insertValue:9];
    
    NSLog(@"tree.count = %lu", (unsigned long)tree.count);
    NSLog(@"traverseInOrder=%@", [tree traverseInOrder]);
    NSLog(@"traversePreOrder=%@", [tree traversePreOrder]);
    NSLog(@"traversePostOrder=%@", [tree traversePostOrder]);
    
    BinarySortTree *b1 = [tree search:0];
    BinarySortTree *b2 = [tree search:1];
    BinarySortTree *b3 = [tree search:7];
}

参考链接

参考1