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

树和二叉树

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

树和二叉树的转换

  • 树转换成二叉树

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