二叉树
基本概念
前面实现的所有链表结构都有一个共同的特征，就是每一个链表的节点都只有一个next指针指向下一个节点，是一条线性的数据结构。二叉树和线性表的不同之处就是二叉树的每一个节点有两个指针分别指向两个子节点。
链表：
二叉树：
下面首先了解一下二叉树的基本概念：
- 节点
- 构成二叉树的每一个节点。
- 根节点
- 二叉树起始的节点，如上图中的①。
- 空树
- 节点数量为0的树。
- 子节点
- 如上图，④的子节点是⑥和⑦。
- 父节点
- 如上图，④的父节点是②，根节点①没有父节点。
- 子树
- 如上图，①两个子节点分别是②和③。 以②为根节点还可以看成一棵二叉树，这棵二叉树可以看成①的子树。②在左边，称为左子树。以③为根节点的子树称为右子树。
- 节点的度
- 节点子树的个数。如上图，①的度为2，②的度为1。
- 叶子节点
- 度为0的节点，如上图⑥⑦⑧⑨。
二叉树的基本结构
通过上面介绍可以看到，二叉树是由节点构成的，这点和链表非常像。而且是由根节点开始的，就像链表是由头节点起始的一样。每一个节点由父节点指向它，而它又分别指向它的两个子节点。两个子节点一个在左边，一个在右边。所以二叉树的节点起码需要如下的属性：
- 父节点
- 左子节点
- 右子节点
- 存放在节点中的元素
通过上面的分析，我们现在先抽象出一个二叉树节点的类：
@interface JKRBinaryTreeNode : NSObject
@property (nonatomic, strong, nonnull) id object;
@property (nonatomic, strong, nullable) JKRBinaryTreeNode *left;
@property (nonatomic, strong, nullable) JKRBinaryTreeNode *right;
@property (nonatomic, weak, nullable) JKRBinaryTreeNode *parent;
@end
复制代码而二叉树只需要保存根节点就可以了；
@interface JKRBinaryTree<ObjectType> : NSObject {
JKRBinaryTreeNode *_root;
}
@end
复制代码现在我们已经创建好了一个自定义的二叉树结构，下面我们就用刚刚创建好的二叉树手动构造一组二叉树的数据：
JKRBinaryTree *tree = [JKRBinaryTree new];
JKRBinaryTreeNode *rootNode = [JKRBinaryTreeNode new];
rootNode.object = @1;
tree->_root = rootNode;
JKRBinaryTreeNode *leftChildNode = [JKRBinaryTreeNode new];
leftChildNode.object = @2;
leftChildNode.parent = rootNode;
rootNode.left = leftChildNode;
JKRBinaryTreeNode *rightChildNode = [JKRBinaryTreeNode new];
rightChildNode.object = @3;
rightChildNode.parent = rootNode;
rootNode.right = rightChildNode;
NSLog(@"%@", tree);
复制代码创建好的二叉树内存结构应该如下图，实线和虚线和用来区分iOS中的强引用和弱引用，其它语言可以无视这个区别。
上面创建一个有三个节点构成二叉树，根节点存放着数字1，根节点的两个子节点分别存放这数组2和3。打印二叉树的结构为：
┌-1 (p: (null))-┐
│ │
2 (p: 1) 3 (p: 1)
复制代码二叉树的打印
上面的打印是封装好的二叉树打印工具打印的，这个工具逻辑非常复杂而且和数据结构并没有关系，可以直接下载工具源码，这里只介绍如何使用：
#import "JKRBinaryTree.h"
/// 引用打印工具
#import "LevelOrderPrinter.h"
/// 自定义的二叉树类实现改协议
@interface JKRBinaryTree ()<LevelOrderPrinterDelegate>
@end
/// 实现LevelOrderPrinterDelegate的代理方法
@implementation JKRBinaryTree
#pragma mark - LevelOrderPrinterDelegate
/// 返回二叉树的根节点
- (id)print_root {
return _root;
}
/// 返回一个节点对象的左子节点
- (id)print_left:(id)node {
JKRBinaryTreeNode *n = (JKRBinaryTreeNode *)node;
return n.left;
}
/// 返回一个节点对象的右子节点
- (id)print_right:(id)node {
JKRBinaryTreeNode *n = (JKRBinaryTreeNode *)node;
return n.right;
}
/// 返回一个节点输出什么样的文字
- (id)print_string:(id)node {
return [NSString stringWithFormat:@"%@", node];
}
#pragma mark - 格式化输出
/// 重写二叉树的打印方法
- (NSString *)description {
return [LevelOrderPrinter printStringWithTree:self];
}
@end
@implementation JKRBinaryTreeNode
/// 重写二叉树节点的打印方法
- (NSString *)description {
// 打印格式: 节点存储的元素 (p: 父节点存储的元素)
return [NSString stringWithFormat:@"%@ (p: %@)", self.object, self.parent.object];
}
@end
复制代码二叉搜索树 Binary Search Tree
上面虽然实现并满足了二叉树的基本结构，不过并没有实际使用价值。但是当二叉树满足如下性质就可以用实用价值了：
- 任何一个节点的值都大于其左子树所有节点的值。
- 任何一个节点的值有小于其右子树所有节点的值。
而满足如上条件的二叉树就是一棵二叉搜索树(Binary Search Tree)，也称二叉查找树、二叉排序树。
如下就是一棵二叉搜索树：
┌---7 (p: (null))---┐
│ │
┌-4 (p: 7)-┐ ┌-9 (p: 7)-┐
│ │ │ │
┌-2 (p: 4)-┐ 5 (p: 4) 8 (p: 9) ┌-11 (p: 9)-┐
│ │ │ │
1 (p: 2) 3 (p: 2) 10 (p: 11) 12 (p: 11)
复制代码仔细观察就可以发现，根节点7的左子树所有节点都小于7，右子树所有节点都大于7。同样的，其它的所有节点也都满足如上的两个条件。
那么这样的二叉树有什么优点和好处呢，这里通过查找就可以知道了，假如需要从二叉搜索树中查找12。既然二叉树开始只能获取到根节点，我们搜索也是从根节点开始的：
- 第一步：12 != 7 && 12 > 7，往下搜索节点7的右子树。
- 第二步：12 != 9 && 12 > 9，往下搜索节点9的右子树。
- 第三步：12 != 11 && 12 > 11，往下搜索节点11的右子树。
- 第四步：12 == 12，找到了12。
可以发现，只需要4步就能够找到12，通过二叉搜索树可以大大提高搜索数据的效率。下面我们就自己实现基于刚刚封装的二叉树的基础上，实现一个二叉搜索树。
二叉搜索树基本结构
首先二叉搜索树也是二叉树，我们的二叉搜索树直接继承刚刚封装的二叉树就可以，同时为了内部方便的存储和记录二叉树的节点数量，同链表的设计一样，我们需要二叉树额外添加一个_size属性记录当前二叉树存书元素的个数，这个属性并非二叉搜索树独有的，而是所以二叉树共有的，所以放在二叉树类中。
/// 二叉树
@interface JKRBinaryTree<ObjectType> : NSObject {
@protected
NSUInteger _size;
JKRBinaryTreeNode *_root;
}
@end
复制代码同时由于二叉搜索树的需要比较节点元素大小的性质，二叉搜索树添加的元素一定是需要比较大小且能够比较大小的，而基于面向对象的特性，存储的元素一定是对象，我们需要告诉二叉搜索树如何比较存入对象的大小，这里我们在二叉搜树中定一个block：
typedef NSInteger(^jkrbinarytree_compareBlock)(id e1, id e2);
复制代码通过block返回的值判断大小：
- e1 = e2：返回值为0
- e1 > e2：返回值大于0
- e1 < e2：返回值小于0
二叉搜索树需要保存一个外部传入的比较大小的block来进行内部元素的大小比对：
/// 二叉搜索树继承自二叉树
@interface JKRBinarySearchTree<ObjectType> : JKRBinaryTree {
@protected
jkrbinarytree_compareBlock _compareBlock;
}
@end
复制代码二叉搜索树的接口定义
为了实现实际使用的基本功能，二叉搜索树需要定义并实现如下接口：
/*
二叉搜索树添加的元素必须具备可比较性
1，通过初始化方法传入比较的代码块
2，加入的对象是系统默认的带有compare:方法的类的实例，例如：NSNumber、NSString类的实例对象
3，加入的对象实现binaryTreeCompare:方法
*/
- (instancetype)initWithCompare:(_Nullable jkrbinarytree_compareBlock)compare;
/// 添加元素
- (void)addObject:(nonnull ObjectType)object;
/// 删除元素
- (void)removeObject:(nonnull ObjectType)object;
/// 是否包含元素
- (BOOL)containsObject:(nonnull ObjectType)object;
/// 通过元素获取对应节点
- (JKRBinaryTreeNode *)nodeWithObject:(nonnull ObjectType)object;
/// 删除节点
- (void)removeWithNode:(JKRBinaryTreeNode *)node;
复制代码二叉搜索树比较逻辑的block不是必传的，因为一些系统默认类型是有默认的比较功能的，比如NSNumber。
同时我们还可以再次支持另一种比较元素大小的方式，就是声明一个协议并定义一个比较大小的方法，如果添加的元素类实现了自定义的比较大小的方法，可以通过自定义比较方法来比较大小：
@protocol JKRBinarySearchTreeCompare <NSObject>
- (NSInteger)binaryTreeCompare:(id)object;
@end
复制代码初始化
- (instancetype)initWithCompare:(jkrbinarytree_compareBlock)compare {
self = [super init];
_compareBlock = compare;
return self;
}
复制代码比较元素大小
二叉搜索树的查找离不开比较逻辑，这里先实现元素比较的私有方法：
比较的逻辑如下：
- 首先判断二叉树是否传入了自定义对象比较的block，如果有则通过block进行比较。
- 如果没有传入block，判断添加的对象类型是否实现了我们自定义的比较方法。
- 如果没有传入block，也没有实现自定义的比较方法，判断添加的对象类型是否支持系统的默认比较方法。
- 上述三种都不满足，则添加的元素无法比较大小，中断并报错。
- (NSInteger)compareWithValue1:(id)value1 value2:(id)value2 {
NSInteger result = 0;
if (_compareBlock) { // 有比较器
result = _compareBlock(value1, value2);
} else if ([value1 respondsToSelector:@selector(binaryTreeCompare:)]) { // 实现了自定义比较方法
result = [value1 binaryTreeCompare:value2];
} else if ([value1 respondsToSelector:@selector(compare:)]){ // 系统自带的可比较对象
result = [value1 compare:value2];
} else {
NSAssert(NO, @"object can not compare!");
}
return result;
}
复制代码添加元素
既然二叉树的添加的元素必须能够比较大小，那么传入的元素不能为空，我们首先创建一个判断元素不为空的方法：
- (void)objectNotNullCheck:(id)object {
if (!object) {
NSAssert(NO, @"object must not be null!");
}
}
复制代码添加元素需要以下的判断逻辑：
- 第一步，判断元素是否为空，不为空进行第二步。
- 第二步，当前二叉树是否是空树，如果是空树则根据传入元素创建一个新节点，并将二叉树的根节点指向新节点，_size++。否则进入需要进行遍历查找比较操作，从根节点开始遍历。
- 第三步，比较添加元素和当前遍历节点元素的大小，如果小于进入第四步，大于进入第五步，相等进入第六步。
- 第四步，取出该节点的左子节点，如果左子节点存在，则返回第三步比较左子节点。否则根据添加元素创建新节点，将新节点做为该节点的左子节点，_size++。
- 第五步，取出该节点的右子节点，如果右子节点存在，则返回第三步比较右子节点。否则根据添加元素创建新节点，将新节点做为该节点的右子节点，_size++。
- 第六步，直接将添加的元素替换当前节点的保存的元素。
- (void)addObject:(id)object {
[self objectNotNullCheck:object];
if (!_root) {
JKRBinaryTreeNode *newNode = [[JKRBinaryTreeNode alloc] initWithObject:object parent:nil];
_root = newNode;
_size++;
return;
}
JKRBinaryTreeNode *parent = _root;
JKRBinaryTreeNode *node = _root;
NSInteger cmp = 0;
while (node) {
cmp = [self compareWithValue1:object value2:node.object];
parent = node;
if (cmp < 0) {
node = node.left;
} else if (cmp > 0) {
node = node.right;
} else {
node.object = object;
return;
}
}
JKRBinaryTreeNode *newNode = [[JKRBinaryTreeNode alloc] initWithObject:object parent:parent];;
if (cmp < 0) {
parent.left = newNode;
} else {
parent.right = newNode;
}
_size++;
}
复制代码通过元素获取对应节点
在二叉搜索树开始的分析时已经模拟一遍查找逻辑，通过元素获取节点和上面添加元素的比较逻辑非常相似：
- 第一步，获取根节点，并从根节点开始遍历。
- 第二步，如果当前遍历的节点为空，则没有找到对应的节点返回nil，否则进入第三步。
- 第三步，比较查找的元素和当前遍历节点的元素，如果相等，则返回该节点。大于，遍历右子节点返回第二步。否则遍历左子节点返回第二步。
- (JKRBinaryTreeNode *)nodeWithObject:(id)object {
JKRBinaryTreeNode *node = _root;
while (node) {
NSInteger cmp = [self compareWithValue1:object value2:node.object];
if (!cmp) {
return node;
} else if (cmp > 0) {
node = node.right;
} else {
node = node.left;
}
}
return nil;
}
复制代码是否包含元素
是否包含某元素即通过元素查找对应的节点是否为空：
return [self nodeWithObject:object] != nil;
复制代码测试二叉搜索树的添加的功能
依次添加 {7,4,2,1,3,5,9,8,11,10,12} 到二叉搜索树中并打印：
JKRBinarySearchTree<NSNumber *> *tree = [[JKRBinarySearchTree alloc] initWithCompare:^NSInteger(NSNumber * _Nonnull e1, NSNumber * _Nonnull e2) {
return e1.intValue - e2.intValue;
}];
int nums[] = {7,4,2,1,3,5,9,8,11,10,12};
NSMutableArray *numbers = [NSMutableArray array];
for (int i = 0; i < sizeof(nums)/sizeof(nums[0]); i++) {
printf("%d ", nums[i]);
[numbers addObject:[NSNumber numberWithInt:nums[i]]];
}
printf("\n");
for (NSNumber *number in numbers) {
[tree addObject:number];
}
/// 打印二叉树
NSLog(@"%@", tree);
复制代码打印结果：
┌---7 (p: (null))---┐
│ │
┌-4 (p: 7)-┐ ┌-9 (p: 7)-┐
│ │ │ │
┌-2 (p: 4)-┐ 5 (p: 4) 8 (p: 9) ┌-11 (p: 9)-┐
│ │ │ │
1 (p: 2) 3 (p: 2) 10 (p: 11) 12 (p: 11)
复制代码可以看到打印的结果和预期一致，满足二叉搜索树的性质。
二叉搜索树的其它功能
二叉搜索树删除相比添加更加复杂而且需要如下二叉树概念：
这里无法马上直接实现二叉搜索树的全部功能，之所以先实现二叉搜索树的添加功能，是因为需要先创建一个可以观察节点元素规律的二叉树，方便后面实现二叉树的遍历和打印。后面完成二叉树的遍历和一些其它基本概念的理解后，会继续实现二叉搜索树的其它功能。