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

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

作者: 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

相关文章

  • 【学习】数据结构和算法

    数据结构 线性表：数组 栈 队列 链表树：二叉树 二叉树遍历 二叉搜索树 B树 红黑树 堆图：图其他：哈希表...

  • 数据结构 - 概要

    数组 链表 堆/栈/队列 树 数据结构 - 二叉树数据结构 - 二叉查找树数据结构 - 平衡二叉树数据结构 - A...

  • 数据结构与算法

    数据结构线性与非线性数组、链表、栈、队列、树、图 树二叉树：顺序，最优、线索、搜索，平衡多路查找树3、排序算法4、...

  • 数据结构

    数据结构 数据结构概念 顺序表 链表 队列 栈 二叉树 常用排序算法

  • 舒服！阿里P9架构师熬夜梳理的2020版Java成神之路指南

    1.计算机基础： 1.1数据结构基础： 主要学习： 1.向量，链表，栈，队列和堆，词典。熟悉 2.树，二叉搜索树。...

  • 算法导论 基本数据结构

    MIT公开课没有讲到的内容，介绍几种基本数据结构- 栈和队列- 链表- 二叉树 栈和队列 栈和队列都是动态集合，元...

  • 数据结构系列0-提纲

    线性列表基于数组、基于链表ArrayList、LinkedList 栈 队列 散列表 树二叉树、搜索二叉树、平衡二...

  • python常用的算法与数据结构

    栈，队列，双端队列无序链表，有序链表二叉树，堆，二叉搜索树，AVL树图以及一些算法 coding: utf-8 u...

  • 2019-02-23 普林斯顿大学 数据结构课程笔记

    一、 数据结构：基本数据结构：栈、队列、背包、优先队列 排序：排序、归并排序、堆排序、基数排序 查找：二叉查找树、...

  • 算法攻略

    知识结构： 常见的数据结构及其实现 常见的数据结构主要有数组、链表、栈、队列、二叉堆、树、图等，其中栈和队列的题目...

网友评论

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

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

      延伸阅读

      深度阅读

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

      栏目导航

      热点阅读

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

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

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

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

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

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