数据结构-树结构(OC实现)

作者: samstring | 来源:发表于2020-05-21 21:56 被阅读0次

数据结构-树结构(OC实现)
集合框架Set之TreeSet
详谈树结构（传统树、字典树、hash 树、Merkle Patr
iOS底层初探
OC 对象的本质
OC对象
iOS | 底层原理分析 (一)
6-玩转数据结构-二分搜索树
01-OC对象的本质
Objective-C内存结构源码解读

树和二叉树

线性结构是节点与节点间是一对一的关系，而树中节点间存在一对多的关系
二叉树是一种特殊的树结构，二叉树是最多只有两个孩子节点的树。
在现实情况下，有些问题不能用线性结构表示。如公司架构图，一个部门下可能有多种岗位，这种情况下我们需要用树来表示。

树和二叉树的转换

树转换成二叉树

1 加线。在所有兄弟结点之间加一条连线。

2 去线。对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。

3 层次调整。以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子”

6-11-2.jpg

二叉树转换成树

1 加线。若某结点的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点……哈，反正就是左孩子的n个右孩子结点都作为此结点的孩子。将该结点与这些右孩子结点用线连接起来。

2 去线。删除原二叉树中所有结点与其右孩子结点的连线。

3 层次调整。使之结构层次分明。

6-11-4.jpg

二叉树的性质

在二叉树的第i层上至多有2i-1个结点（i≥1）。
深度为k的二叉树至多有2k-1个结点（k≥1）
对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1
具有n个结点的完全二叉树的深度为|log2n+1|（|x|表示不大于x的最大整数）
如果对一棵有n个结点的完全二叉树（其深度为）的结点按层序编号（从第1层到第层，每层从左到右），对任一结点i（1≤i≤n）
- 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点。
- 如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是结点2i。
- 如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1。”

二叉树

下面给出二拆树的创建，插入节点，遍历等操作的实现代码
SFBinaryTreeNode.h

@interface SFBinaryTreeNode : NSObject
@property (nonatomic, assign) int data;
@property (nonatomic, strong) SFBinaryTreeNode *leftChild;
@property (nonatomic, strong) SFBinaryTreeNode *rightChild;
@end

SFBinaryTree.h


typedef void(^SFBinaryTreeTraverseBlock)(SFBinaryTreeNode *node);

@interface SFBinaryTree : NSObject

@property (nonatomic, strong) SFBinaryTreeNode *rootNode;
+(SFBinaryTree *)initBinaryTreeeWithRoot:(SFBinaryTreeNode *)rootNode;
@property (nonatomic, copy) SFBinaryTreeTraverseBlock traverseBlock;
-(BOOL)insertLeftChild:(SFBinaryTreeNode *)child forParent:(SFBinaryTreeNode *) parent;//插入左节点
-(BOOL)insertRightChild:(SFBinaryTreeNode *)child forParent:(SFBinaryTreeNode *) parent;//插入右节点
-(BOOL)replaceLeftChild:(SFBinaryTreeNode *)child forParent:(SFBinaryTreeNode *) parent;//替换左节点
-(BOOL)replaceRightChild:(SFBinaryTreeNode *)child forParent:(SFBinaryTreeNode *) parent;//替换右节点
-(BOOL)deleteLeftChildforParent:(SFBinaryTreeNode *) parent;//删除左节点
-(BOOL)deleteRightChildforParent:(SFBinaryTreeNode *) parent;//删除右节点
-(void )preTraverseWithTraverseBlock:(SFBinaryTreeTraverseBlock)traverseBlock;//传入根节点前序遍历树
-(void )midTraverseWithTraverseBlock:(SFBinaryTreeTraverseBlock)traverseBlock;//传入根节点中序遍历树
-(void )afterTraverseWithTraverseBlock:(SFBinaryTreeTraverseBlock)traverseBlock;//传入根节点后序遍历树
@end

SFBinaryTree.m

#import "SFBinaryTree.h"

@implementation SFBinaryTree
+(SFBinaryTree *)initBinaryTreeeWithRoot:(SFBinaryTreeNode *)rootNode{
    SFBinaryTree *binaryTree = [SFBinaryTree new];
    //    if(rootNode == nil){
    //        NSLog(@"根节点不能为空");
    //        return nil;
    //    }
    binaryTree.rootNode = rootNode;
    return  binaryTree;
    
}

-(BOOL)insertLeftChild:(SFBinaryTreeNode *)child forParent:(SFBinaryTreeNode *)parent{
    Boolean isInsertOnde = NO;
    NSMutableArray *nodesArray = [NSMutableArray array ];
    [self midTraverse:self.rootNode withTraverseBlock:^(SFBinaryTreeNode * _Nonnull node) {
        [nodesArray addObject:node];
    }];
    if(!child ){
        NSLog(@"子节点不能为空");
    }
    else if(!parent || ![nodesArray containsObject:parent]){
        NSLog(@"父节点不存在");
    }
    else if(parent.leftChild != nil){
        NSLog(@"父子节的左子节点已存在");
    }else{
        parent.leftChild = child;
        isInsertOnde = YES;
    }
    
    
    
    return isInsertOnde;
}


-(BOOL)replaceLeftChild:(SFBinaryTreeNode *)child forParent:(SFBinaryTreeNode *)parent{
    Boolean isRepaceDone = NO;
    NSMutableArray *nodesArray = [NSMutableArray array ];
    [self midTraverse:self.rootNode withTraverseBlock:^(SFBinaryTreeNode * _Nonnull node) {
        [nodesArray addObject:node];
    }];
   if(!parent || ![nodesArray containsObject:parent]){
        NSLog(@"父节点不存在");
    }
    else{
        parent.leftChild = child;
        isRepaceDone = YES;
    }
    
    
    
    return isRepaceDone;
}

-(BOOL)insertRightChild:(SFBinaryTreeNode *)child forParent:(SFBinaryTreeNode *)parent{
    Boolean isInsertOnde = NO;
    NSMutableArray *nodesArray = [NSMutableArray array ];
    [self midTraverse:self.rootNode withTraverseBlock:^(SFBinaryTreeNode * _Nonnull node) {
        [nodesArray addObject:node];
    }];
    
    if(!child ){
        NSLog(@"子节点不能为空");
    }
    
    else if(!parent ||  ![nodesArray containsObject:parent]){
        NSLog(@"父节点不存在");
    }
    else if(parent.rightChild != nil){
        NSLog(@"父子节的右子节点已存在");
    }
    else{
        parent.rightChild = child;
        isInsertOnde = YES;
    }
    
    
    
    return isInsertOnde;
}

-(BOOL)replaceRightChild:(SFBinaryTreeNode *)child forParent:(SFBinaryTreeNode *)parent{
    Boolean isRepaceDone = NO;

    NSMutableArray *nodesArray = [NSMutableArray array ];
    [self midTraverse:self.rootNode withTraverseBlock:^(SFBinaryTreeNode * _Nonnull node) {
        [nodesArray addObject:node];
    }];
    
    if(!parent || ![nodesArray containsObject:parent]){
        NSLog(@"父节点不存在");
    }
    else{
        parent.rightChild = child;
        isRepaceDone = YES;
    }
    
    
    
    return isRepaceDone;
}


-(BOOL)deleteLeftChildforParent:(SFBinaryTreeNode *) parent{
   return  [self replaceLeftChild:nil forParent:parent];
}
-(BOOL)deleteRightChildforParent:(SFBinaryTreeNode *) parent{
    return [self replaceRightChild:nil forParent:parent];
}


+(NSMutableArray *)midTraverse:(SFBinaryTreeNode *)rootNode{
    NSMutableArray *array = [NSMutableArray array];
    return array;
}

-(void)midTraverseWithTraverseBlock:(SFBinaryTreeTraverseBlock)traverseBlock{
    [self midTraverse:self.rootNode withTraverseBlock:traverseBlock];
}
-(void)midTraverse:(SFBinaryTreeNode *)rootNode withTraverseBlock:(nonnull SFBinaryTreeTraverseBlock)traverseBlock{
    if (rootNode == nil) {
//        NSLog(@"根节点不能为空");
        return;
    }
    //访问左子树
    [self midTraverse:rootNode.leftChild withTraverseBlock:traverseBlock];
    //访问节点
    if(traverseBlock){
        traverseBlock(rootNode);
    }
    //访问右子树
    [self midTraverse:rootNode.rightChild withTraverseBlock:traverseBlock];
}

-(void)preTraverseWithTraverseBlock:(SFBinaryTreeTraverseBlock)traverseBlock{
    [self preTraverse:self.rootNode withTraverseBlock:traverseBlock];
}
-(void)preTraverse:(SFBinaryTreeNode *)rootNode withTraverseBlock:(nonnull SFBinaryTreeTraverseBlock)traverseBlock{
    if (rootNode == nil) {
//        NSLog(@"根节点不能为空");
        return;
    }
    //访问节点
    if(traverseBlock){
        traverseBlock(rootNode);
    }
    
    //访问左子树
    [self preTraverse:rootNode.leftChild withTraverseBlock:traverseBlock] ;
    
    //访问右子树
    [self preTraverse:rootNode.rightChild withTraverseBlock:traverseBlock];
}

-(void)afterTraverseWithTraverseBlock:(SFBinaryTreeTraverseBlock)traverseBlock{
    [self afterTraverse:self.rootNode withTraverseBlock:traverseBlock];
}
- (void)afterTraverse:(SFBinaryTreeNode *)rootNode withTraverseBlock:(nonnull SFBinaryTreeTraverseBlock)traverseBlock{
    if (rootNode == nil) {
//        NSLog(@"根节点不能为空");
        return;
    }
    //访问左子树
    [self afterTraverse:rootNode.leftChild withTraverseBlock:traverseBlock];
    
    //访问右子树
    [self afterTraverse:rootNode.rightChild withTraverseBlock:traverseBlock];
    
    //访问节点
    if(traverseBlock){
        traverseBlock(rootNode);
    }
}
@end

二叉树的线索化

对于二叉树，二叉树的叶子节点的左右子树为空。对于二叉树的叶子节点，能否也利用起来呢？能拿来做什么呢？
其实，我们可以把叶子节点的左子节点指向叶子节点的前驱，把右子节点指向后继。这样的话就可以形成一个双向链表。
但是如果叶子节点需要指向前驱后继的话，需要一个标志去表明左右节点指针指向的是前驱后继还是指向子节点。

其实线索化的就是遍历节点，如果节点的左孩子节点指针为空，则把指针指向前驱节点。如果节点的右孩子节点指针为空，则把指针指向后继节点。
这里采用中序遍历去线索化二叉树，在中序遍历中，因为前驱节点A已经被访问过的原因，访问节点B时我们可以轻易的拿到前驱节点A，但是后继节点C没有访问过，所以在访问B的时候我们无法直接指向后继节点C。但是我们可以在访问后继节点C的时候，让节点B的右子节点指向C，以达到节点B的右子节点只想后继节点的目的。

实现如下
SFThreadedBinaryTreeNode.h

#import <Foundation/Foundation.h>


typedef enum : NSUInteger {
    Child_Content_Child = 0,//指向子节点
    Child_Content_Thread,//点指向前驱或是后继
} ChildContentType;
NS_ASSUME_NONNULL_BEGIN

@interface SFThreadedBinaryTreeNode : NSObject
@property (nonatomic, assign) int data;
@property (nonatomic, strong) SFThreadedBinaryTreeNode *leftChild;
@property (nonatomic, strong) SFThreadedBinaryTreeNode *rightChild;
@property (nonatomic, assign) ChildContentType leftChildType;
@property (nonatomic, assign) ChildContentType rightChildType;
@end

NS_ASSUME_NONNULL_END

SFThreadedBinaryTree.h


#import <Foundation/Foundation.h>
#import "SFThreadedBinaryTreeNode.h"
NS_ASSUME_NONNULL_BEGIN

@interface SFThreadedBinaryTree : NSObject

@property (nonatomic, strong) SFThreadedBinaryTreeNode *rootNode;
@end

NS_ASSUME_NONNULL_END

SFThreadedBinaryTree.m

#import "SFThreadedBinaryTree.h"

@interface SFThreadedBinaryTree ()

@property (nonatomic, strong) SFThreadedBinaryTreeNode *preNode;//做线索话使用

@end

@implementation SFThreadedBinaryTree

-(void)threadingBinaertTree{
    [self threadingBinaertTreeWithRootNode:self.rootNode];
}

-(void)threadingBinaertTreeWithRootNode:(SFThreadedBinaryTreeNode *)rootNode{
    
    if(!rootNode){
        
        return;
    }
    
    
    [self threadingBinaertTreeWithRootNode:rootNode.leftChild];
    
    //如果左孩子节点为空，将将左节点设指向上一个节点，以形成前驱节点
    if(!rootNode.leftChild){
        rootNode.leftChild = self.preNode;
        rootNode.leftChild.leftChildType = Child_Content_Thread;
    }
    
    if(!self.preNode.rightChild)
    {
        self.preNode.rightChildType = Child_Content_Thread;
        self.preNode.rightChild = rootNode;
    }
    
    self.preNode = rootNode;
    
    
    [self threadingBinaertTreeWithRootNode:rootNode.rightChild];
}
@end

数据结构-树结构(OC实现)
树和二叉树线性结构是节点与节点间是一对一的关系，而树中节点间存在一对多的关系二叉树是一种特殊的树结构，二叉树是最...
集合框架Set之TreeSet
TreeSet Set 接口的一种实现类它的底层实现是基于TreeMap(底层实现的数据结构是树结构,并不...
详谈树结构（传统树、字典树、hash 树、Merkle Patr
关于数据结构中树结构的相关分享本文参考：树结构参考文献一、传统的数据结构中的树结构树结构是一种非线性存储结...
iOS底层初探
OC底层实现原理 oc对象以及类的是底层实现首先，通过数据结构的特性可以猜测类的底层应该是结构体这种数据结构，因...
OC 对象的本质
OC的本质我们平时写的OC代码的底层都是c/c++代码实现的 OC的面向对象都是基于c/c++的数据结构实现的 ...
OC对象
OC的本质 oc代码，底层是由c/c++实现 Objective-C的面向对象都是基于C\C++的数据结构实现的 ...
iOS | 底层原理分析 (一)
一. OC对象本质 1.1 OC对象数据结构我们平时编写的Objective-C代码，底层实现其实都是C\C++...
6-玩转数据结构-二分搜索树
之前我们的课程都在关注线性的数据结构，我们从本章开始学习树结构,二分搜索树。树结构: 线性数据结构是将数据排成一...
01-OC对象的本质
OC是通过C/C++的什么数据结构实现我们的OC对象呢结构体--OC对象的本质就是C/C++的结构体 Class...
Objective-C内存结构源码解读
我们平时编写的OC代码，底层实现其实都是C\C++代码，所以OC的对象和类主要是基于C和C++的数据结构实现的，这...