美文网首页
数据结构之队列,栈,二叉搜索树

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

作者: ZZ_军哥 | 来源:发表于2022-04-27 15:48 被阅读0次

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

    #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

    相关文章

      网友评论

          本文标题：数据结构之队列,栈,二叉搜索树

          本文链接：https://www.haomeiwen.com/subject/hzclyrtx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|数据结构之队列,栈,二叉搜索树|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！