数据结构之队列,栈,二叉搜索树

根据上一篇的双向循环链表,衍生出的队列,栈
一.栈:先进后出,类似往桶里放东西,从桶里取东西

#import <Foundation/Foundation.h>

NS_ASSUME_NONNULL_BEGIN

@interface GYJStack : NSObject

//栈中元素个数
- (NSInteger)size;
//是否空栈
- (BOOL)isEmpty;
//入栈
- (void)pushElement:(NSObject *)objc;
//出栈
- (NSObject *)popElement;
//查看栈顶元素
- (NSObject *)peekElement;
//清空栈
- (void)clear;

@end

#import "GYJStack.h"
#import "GYJCircleLinkList.h"

@interface GYJStack ()

@property(nonatomic,strong)GYJCircleLinkList *linkList;

@end

@implementation GYJStack

- (instancetype)init{
    if (self = [super init]) {
        _linkList = [[GYJCircleLinkList alloc]init];
    }
    return self;
}

//栈中元素个数
- (NSInteger)size
{
    return _linkList.size;
}
- (BOOL)isEmpty
{
    return _linkList.size == 0;
}
//入栈
- (void)pushElement:(NSObject *)objc
{
    [_linkList addElement:objc];
}
//出栈
- (NSObject *)popElement
{
    if (_linkList.size>0) {
        return [_linkList removeObjcAtIndex:_linkList.size-1];
    }
    return nil;
}
//查看栈顶元素
- (NSObject *)peekElement
{
    if (_linkList.size>0) {
        return [_linkList elementOfIndex:_linkList.size-1];
    }
    return nil;
}
//清空栈
- (void)clear
{
    [_linkList clear];
}

@end

二.普通队列:先进先出,类似水管

#import <Foundation/Foundation.h>

NS_ASSUME_NONNULL_BEGIN

@interface GYJQueue : NSObject

//队列中元素个数
- (NSInteger)size;
- (BOOL)isEmpty;
//入队
- (void)enterQueue:(NSObject *)element;
//出队
- (NSObject *)outQueue;
//即将出队的元素
- (NSObject *)willOutQueueElement;
//刚刚入队的元素
- (NSObject *)latestEnterQueueElement;
//清空队列
- (void)clear;

@end

#import "GYJQueue.h"
#import "GYJCircleLinkList.h"

@interface GYJQueue()

@property(nonatomic,strong)GYJCircleLinkList *linkList;

@end

@implementation GYJQueue

- (instancetype)init
{
    if (self = [super init]) {
        _linkList = [[GYJCircleLinkList alloc]init];
    }
    return self;
}
//队列中元素个数
- (NSInteger)size
{
    return _linkList.size;
}
- (BOOL)isEmpty
{
    return _linkList.size==0;
}
//入队
- (void)enterQueue:(NSObject *)element
{
    [_linkList insertElement:element atIndex:0];
}
//出队
- (NSObject *)outQueue
{
    if (_linkList.size>0) {
        return [_linkList removeObjcAtIndex:_linkList.size-1];
    }
    return nil;
}
//即将出队的元素
- (NSObject *)willOutQueueElement
{
    if (_linkList.size>0) {
        return [_linkList elementOfIndex:_linkList.size-1];
    }
    return nil;
}
//刚刚入队的元素
- (NSObject *)latestEnterQueueElement
{
    if (_linkList.size>0) {
        return [_linkList elementOfIndex:0];;
    }
    return nil;
}
//清空队列
- (void)clear
{
    [_linkList clear];
}

@end

三.双端队列:从两端入,也可从两端出,类似水泥管,从两边进入藏人,两边出人

#import <Foundation/Foundation.h>

NS_ASSUME_NONNULL_BEGIN

@interface GYJDoubleEndedQueue : NSObject
//队列中元素的个数
- (NSInteger)size;
//队列是否为空
- (BOOL)isEmpty;
//从前端入口入队
- (void)enterElementAtFront:(NSObject *)element;
//从前端入口入队
- (void)enterElementAtEnd:(NSObject *)element;
//从前端入口出队
- (NSObject *)outElementFromFront;
//从后端入口出队
- (NSObject *)outElementFronEnd;
//查看前端最近的元素,但是并不出队
- (NSObject *)peekElementAtFront;
//查看后端最近的元素,但是并不出队
- (NSObject *)peekElementAtEnd;
//清空队列
- (void)clear;
@end

NS_ASSUME_NONNULL_END

#import "GYJDoubleEndedQueue.h"
#import "GYJCircleLinkList.h"

@interface GYJDoubleEndedQueue ()

@property(nonatomic,strong)GYJCircleLinkList *linkList;

@end

@implementation GYJDoubleEndedQueue

- (instancetype)init
{
    if (self = [super init]) {
        _linkList = [[GYJCircleLinkList alloc]init];
    }
    return self;
}

//队列中元素的个数
- (NSInteger)size
{
    return [_linkList size];
}
//队列是否为空
- (BOOL)isEmpty
{
    return [_linkList isEmpty];
}

//从前端入口入队
- (void)enterElementAtFront:(NSObject *)element
{
    [_linkList insertElement:element atIndex:0];
}
//从后端入口入队
- (void)enterElementAtEnd:(NSObject *)element
{
    [_linkList addElement:element];
}
//从前端入口出队
- (NSObject *)outElementFromFront
{
    if (![_linkList isEmpty]) {
        return [_linkList removeObjcAtIndex:0];
    }
    return nil;
}
//从后端入口出队
- (NSObject *)outElementFronEnd
{
    if (![_linkList isEmpty]) {
        return [_linkList removeObjcAtIndex:_linkList.size-1];
    }
    return nil;
}
//查看前端最近的元素,但是并不出队
- (NSObject *)peekElementAtFront
{
    if (_linkList.size!=0) {
        return [_linkList elementOfIndex:0];
    }
    return nil;
}
//查看后端最近的元素,但是并不出队
- (NSObject *)peekElementAtEnd
{
    if (_linkList.size!=0) {
        return [_linkList elementOfIndex:_linkList.size-1];
    }
    return nil;
}
//清空队列
- (void)clear
{
    [_linkList clear];
}

@end

四:二叉搜索树:如下所示

image.png

1.每个节点都有左右子节点
2.节点的左边元素比自己小,节点的右边元素比自己大
3.前驱/后继节点:如上图的数据顺序从小到大为 8, 11, 21, 40, 41, 63, 76, 77, 87, 89, 94,那么40这个元素的前驱节点为21,40的后继节点为41
4.查找前驱节点,先left,然后一直right,最后的那个点即为前驱
5.查找后继节点,先right,然后一直left,最后的那个点即为后继

#import <Foundation/Foundation.h>

NS_ASSUME_NONNULL_BEGIN

typedef int (^CompareBlock)(NSObject *objc1,NSObject *objc2);;

@interface GYJBinarySearchTree : NSObject

//元素的个数
@property(nonatomic,assign,readonly)NSInteger size;

- (instancetype)initWithCompareBlock:(CompareBlock)compareBlock;

//添加元素
- (void)addElement:(NSObject *)element;
//移除元素
- (void)removeElement:(NSObject *)element;
//前序遍历
- (void)preOrderAllElement:(void(^)(NSObject *objc))completeBlock;
//中序遍历->升序
- (void)inOrderAllElementAscend:(void(^)(NSObject *objc))completeBlock;
//中序遍历->降序
- (void)inOrderAllElementDscend:(void(^)(NSObject *objc))completeBlock;
//后续遍历
- (void)postOrderAllElement:(void(^)(NSObject *objc))completeBlock;
//层序遍历
- (void)levelOrderAllElementDscend:(void(^)(NSObject *objc))completeBlock;
//清空所有元素
- (void)clear;


@end
//树节点
@interface GYJTreeNode : NSObject

@property(nonatomic,strong,nullable)GYJTreeNode *left;
@property(nonatomic,strong,nullable)GYJTreeNode *right;
@property(nonatomic,weak,nullable)GYJTreeNode *parent;
@property(nonatomic,strong)NSObject *element;

- (instancetype)initWithLeft:(nullable GYJTreeNode *)left right:(nullable GYJTreeNode *)right parent:(nullable GYJTreeNode *)parent element:(NSObject *)element;
//是否含有2个子节点
- (BOOL)hasTwoChildren;
//是否为叶子函数
- (BOOL)isLeaf;

@end


NS_ASSUME_NONNULL_END

#import "GYJBinarySearchTree.h"
#import "GYJQueue.h"

@interface GYJBinarySearchTree ()

@property(nonatomic,strong)GYJTreeNode *root;
@property(nonatomic,copy)CompareBlock compareBlock;

@end

@implementation GYJBinarySearchTree

- (instancetype)initWithCompareBlock:(CompareBlock)compareBlock
{
    if (self = [super init]) {
        _compareBlock = compareBlock;
    }
    return self;
}

//添加元素
- (void)addElement:(NSObject *)element
{
    if (element==nil) return;
    if (_root==nil) {
        GYJTreeNode *node = [[GYJTreeNode alloc]initWithLeft:nil right:nil parent:nil element:element];
        _root = node;
    }else{
        GYJTreeNode *tempNode = _root;
        GYJTreeNode *parentNode = _root;
        int cmpResult = 0;
        while (tempNode!=nil) {
            parentNode = tempNode;
            cmpResult = _compareBlock(element,tempNode.element);
            if (cmpResult<0) {
                tempNode = tempNode.left;
            }else if (cmpResult>0){
                tempNode = tempNode.right;
            }else{ //如果结果相同,则进行替换
                tempNode.element = element;
                return;
            }
        }
        GYJTreeNode *node = [[GYJTreeNode alloc]initWithLeft:nil right:nil parent:parentNode element:element];
        if (cmpResult<0) {
            parentNode.left = node;
        }else{
            parentNode.right = node;
        }
    }
    _size++;
}
//移除元素
- (void)removeElement:(NSObject *)element
{
    if(element==nil)return;
    GYJTreeNode *node = [self nodeByElement:element];
    if (node==nil) return;
    _size--;
    BOOL hasTwoChild = [node hasTwoChildren];
    BOOL isLeaf = [node isLeaf];
    if (hasTwoChild) {
        GYJTreeNode *predesessor = [self predecessorNode:node];
        node.element = predesessor.element;
        if ([predesessor isLeaf]) {
            if ([predesessor.parent.left isEqual:predesessor]) {
                predesessor.parent.left=nil;
            }else{
                predesessor.parent.right=nil;
            }
        }else{
            GYJTreeNode *child = predesessor.left!=nil?predesessor.left:predesessor.right;
            BOOL isLeft = [predesessor.parent.left isEqual:predesessor]?YES:NO;
            if (isLeft) {
                node.left = child;
            }else{
                node.right = child;
            }
            child.parent = node;
        }
        return;
    }
    if (isLeaf) {
        if ([node.parent.left isEqual:node]) {
            node.parent.left = nil;
        }else{
            node.parent.right = nil;
        }
        return;
    }
    //最后来到单个节点的地方
    GYJTreeNode *childNode = node.left==nil?node.right:node.left;
    BOOL isLeft = [node.parent.left isEqual:node]?YES:NO;
    if (node.parent!=nil) {
        if (isLeft) {
            node.parent.left = childNode;
            childNode.parent = node.parent;
        }else{
            node.parent.right = childNode;
            childNode.parent = node.parent;
        }
    }else{
        _root = childNode;
    }
}
//前序遍历
- (void)preOrderAllElement:(void(^)(NSObject *objc))completeBlock
{
    [self preOrderAllElement:completeBlock node:_root];
}
- (void)preOrderAllElement:(void (^)(NSObject * _Nonnull))completeBlock node:(GYJTreeNode *)node
{
    if (node==nil) return;
    if (completeBlock) {
        completeBlock(node.element);
    }
    [self preOrderAllElement:completeBlock node:node.left];
    [self preOrderAllElement:completeBlock node:node.right];
}
//中序遍历->升序
- (void)inOrderAllElementAscend:(void(^)(NSObject *objc))completeBlock
{
    [self inOrderAllElementAscend:completeBlock node:_root];
}
- (void)inOrderAllElementAscend:(void(^)(NSObject *objc))completeBlock node:(GYJTreeNode *)node
{
    if (node==nil) return;
    [self inOrderAllElementAscend:completeBlock node:node.left];
    if (completeBlock) {
        completeBlock(node.element);
    }
    [self inOrderAllElementAscend:completeBlock node:node.right];
}
//中序遍历->降序
- (void)inOrderAllElementDscend:(void(^)(NSObject *objc))completeBlock
{
    [self inOrderAllElementDscend:completeBlock node:_root];
}
//中序遍历->降序
- (void)inOrderAllElementDscend:(void(^)(NSObject *objc))completeBlock node:(GYJTreeNode *)node
{
    if (node==nil) return;
    [self inOrderAllElementDscend:completeBlock node:node.right];
    if (completeBlock) {
        completeBlock(node.element);
    }
    [self inOrderAllElementDscend:completeBlock node:node.left];
}
//后续遍历
- (void)postOrderAllElement:(void(^)(NSObject *objc))completeBlock
{
    [self postOrderAllElement:completeBlock node:_root];
}
//后续遍历
- (void)postOrderAllElement:(void(^)(NSObject *objc))completeBlock node:(GYJTreeNode *)node
{
    if (node==nil) return;
    [self postOrderAllElement:completeBlock node:node.left];
    [self postOrderAllElement:completeBlock node:node.right];
    if (completeBlock) {
        completeBlock(node.element);
    }
}
//层序遍历
- (void)levelOrderAllElementDscend:(void(^)(NSObject *objc))completeBlock
{
    GYJTreeNode *node = _root;
    GYJQueue *queue = [[GYJQueue alloc]init];
    [queue enterQueue:node];
    while (![queue isEmpty]) {
        node = (GYJTreeNode *)[queue outQueue];
        if (completeBlock) {
            completeBlock(node.element);
        }
        if (node.left!=nil) {
            [queue enterQueue:node.left];
        }
        if (node.right!=nil) {
            [queue enterQueue:node.right];
        }
    }
}

//获取前驱节点
- (GYJTreeNode *)predecessorNode:(GYJTreeNode *)treeNode
{
    if (treeNode==nil) return nil;
    GYJTreeNode *node = treeNode.left;
    GYJTreeNode *parentNode = treeNode;
    while (node!=nil) {
        parentNode = node;
        node = node.right;
    }
    return parentNode;
}
//获取后续节点
- (GYJTreeNode *)succssorNode:(GYJTreeNode *)treeNode
{
    if (treeNode==nil) return nil;
    GYJTreeNode *node = treeNode.right;
    GYJTreeNode *parentNode = treeNode;
    while (node!=nil) {
        parentNode = node;
        node = node.left;
    }
    return parentNode;
}

//获取对应元素的节点
- (GYJTreeNode *)nodeByElement:(NSObject *)element
{
    GYJTreeNode *node = _root;
    int cmpResult = 0;
    while (node!=nil) {
        cmpResult = _compareBlock(element,node.element);
        if (cmpResult==0) {
            return node;
        }else if (cmpResult<0){
            node = node.left;
        }else{
            node = node.right;
        }
    }
    return nil;
}
//清空所有元素
- (void)clear
{
    _root = nil;
    _size = 0;
}

@end

@implementation GYJTreeNode

- (instancetype)initWithLeft:(nullable GYJTreeNode *)left right:(nullable GYJTreeNode *)right parent:(nullable GYJTreeNode *)parent element:(NSObject *)element
{
    if (self = [super init]) {
        _left = left;
        _right = right;
        _parent = parent;
        _element = element;
    }
    return self;
}

//是否含有2个子节点
- (BOOL)hasTwoChildren
{
    return _left!=nil && _right!=nil;
}
//是否为叶子函数
- (BOOL)isLeaf
{
    return _left == nil && _right == nil;
}
@end

最后编辑于：2022.04.29 10:46:57

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 214,922评论 6赞 497
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 91,591评论 3赞 389
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 160,546评论 0赞 350
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,467评论 1赞 288
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,553评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,580评论 1赞 293
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,588评论 3赞 414
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,334评论 0赞 270
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,780评论 1赞 307
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,092评论 2赞 330
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,270评论 1赞 344
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,925评论 5赞 338
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,573评论 3赞 322
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,194评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,437评论 1赞 268
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,154评论 2赞 366
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,127评论 2赞 352

数据结构之队列,栈,二叉搜索树

推荐阅读更多精彩内容