序言
在百度百科中是这样定义二叉树的，在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。
二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林
OC 中没有二叉树和哈希表的概念，本文通过 OC 实现二叉树和哈希表。
一. 二叉树的实现
- BinaryTreeNode.h
/**
二叉树节点
*/
@interface BinaryTreeNode : NSObject
/**
* 值
*/
@property (nonatomic, assign) NSInteger value;
/**
* 左节点
*/
@property (nonatomic, strong) BinaryTreeNode *leftNode;
/**
* 右节点
*/
@property (nonatomic, strong) BinaryTreeNode *rightNode;
/**
类工厂方法
@param value 节点值
@return 二叉树节点
*/
+ (BinaryTreeNode *)binaryTreeNodeWithValue:(NSInteger)value;
@end
- BinaryTreeNode.m
@implementation BinaryTreeNode
+ (BinaryTreeNode *)binaryTreeNodeWithValue:(NSInteger)value {
BinaryTreeNode *treeNode = [[BinaryTreeNode alloc] init];
treeNode.value = value;
return treeNode;
}
@end
二. 哈希表的实现
在百度百科中是这样定义哈希表的。散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
- HashMap.h
/**
模拟哈希表
*/
@interface HashMap : NSObject
/**
插入新值
@param value 值
@param index 索引
*/
- (void)put:(int)value index:(int)index;
/**
根据值,返回其索引
@param value 值
@return 索引
*/
- (int)get:(int)value;
@end
- HashMap.m
@implementation HashMap {
NSMutableDictionary *_hashDict; // 保存数据
}
- (instancetype)init {
self = [super init];
if (self) {
_hashDict = [NSMutableDictionary dictionary];
}
return self;
}
/**
插入新值
*/
- (void)put:(int)val index:(int)index {
NSString *key = [NSString stringWithFormat:@"%d",index];
NSString *value = [NSString stringWithFormat:@"%d",val];
[_hashDict setValue:value forKey:key];
}
/**
根据值,返回其索引
*/
- (int)get:(int)value {
NSArray *allKeys = [_hashDict allKeys];
if (allKeys.count == 0) {
return 0;
}
int index = 0;
for (NSString *key in allKeys) {
NSString *valueStr = [_hashDict valueForKey:key];
if ([valueStr intValue] == value) {
index = [key intValue];
break;
}
}
return index;
}
@end
使用
重建二叉树
题目描述
根据二叉树的前序遍历和中序遍历的结果，重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
image.png
解题思路
前序遍历的第一个值为根节点的值，使用这个值将中序遍历结果分成两部分，左部分为树的左子树中序遍历结果，右部分为树的右子树中序遍历的结果。
详细代码如下
+ (BinaryTreeNode *)reConstructBinaryTree:(NSArray *)preorders inorders:(NSArray *)inorders {
// 初始化哈希表
HashMap *indexForInOrders = [[HashMap alloc] init];
for (int i = 0; i < inorders.count; i++) {
[indexForInOrders put:[inorders[i] intValue] index:i];
}
return [self reConstructBinaryTreeWithOrders:indexForInOrders preorders:preorders preL:0 preR:(int)preorders.count - 1 inL:0];
}
+ (BinaryTreeNode *)reConstructBinaryTreeWithOrders:(HashMap *)indexForInOrders preorders:(NSArray *)preorders preL:(int)preL preR:(int)preR inL:(int)inL {
if (preL > preR) {
return nil;
}
// 取左边二叉树的值构成一个新的节点
BinaryTreeNode *root = [BinaryTreeNode binaryTreeNodeWithValue:[preorders[preL] integerValue]];
int inIndex = [indexForInOrders get:(int)root.value];
int leftTreeSize = inIndex - inL;
root.leftNode = [self reConstructBinaryTreeWithOrders:indexForInOrders preorders:preorders preL:preL + 1 preR:preL + leftTreeSize inL:inL];
root.rightNode = [self reConstructBinaryTreeWithOrders:indexForInOrders preorders:preorders preL:preL + leftTreeSize + 1 preR:preR inL:inL + leftTreeSize + 1];
return root;
}
测试案例代码
// 7.重建二叉树
- (void)reConstructBinaryTree {
NSArray *preorders = @[@3,@9,@20,@15,@7];
NSArray *inorders = @[@9,@3,@15,@20,@7];
BinaryTreeNode *treeNode = [ReConstructBinaryTree_07 reConstructBinaryTree:preorders inorders:inorders];
NSLog(@"treeNode = %@",treeNode);
}
运行结果
image.png
如有错误，欢迎指正，多多点赞，打赏更佳，您的支持是我写作的动力。
网友评论