二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
1. 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 任意节点的左、右子树也分别为二叉查找树；
4. 没有键值相等的节点；
本文跟前文一样只是实现了增加和查找功能，需要一个节点辅助类:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
@interface BinaryNode:NSObject
@property (strong,nonatomic) NSString *key;//键
@property (strong,nonatomic) NSString *value;//值
@property (strong,nonatomic) BinaryNode *left;//左子树的节点
@property (strong,nonatomic) BinaryNode *right;//右子树的节点
@property (assign,nonatomic) NSInteger childCount;//以该结点为根的自述中的结点总数
-(void)initWithData:(NSString *)key value:(NSString *)value childCount:(NSInteger)childCount;
@end |
BinaryNode实现代码：
|
1
2
3
4
5
6
7
8
9
|
@implementation BinaryNode
-(void)initWithData:(NSString *)key value:(NSString *)value childCount:(NSInteger)childCount{
self.key=key;
self.value=value;
self.childCount=childCount;
}@end |
二叉查找树需要定义一个根结点:
|
1
2
3
4
5
6
7
8
9
|
@interface BinarySearchTree : NSObject
@property (strong,nonatomic) BinaryNode *root;//二叉平衡树的根节点
-(NSString *)get:(NSString *)key;//获取键对应的值
-(void)put:(NSString *)key value:(NSString *)value;//插入键值对
@end |
实现代码:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
@implementation BinarySearchTree
-(NSString *)get:(NSString *)key{
return [self getByKey:self.root key:key];
}-(NSString *)getByKey:(BinaryNode *)node key:(NSString *)key{
//在node为根结点的子树种查找并返回key所对应的值
//如果找不到返回null
if (node==nil) {
return nil;
}
//左右节点进行比较，每个结点的键值大于左子树的结点值小于右子树的结点值
NSInteger compare=[key integerValue]-[node.key integerValue];
if (compare>0) {
return [self getByKey:node.right key:key];
}else if(compare<0){
return [self getByKey:node.left key:key];
}else{
return node.value;
}
}//http://www.cnblogs.com/xiaofeixiang-(void)put:(NSString *)key value:(NSString *)value{
//查找键值，找到则更新它的值，否则为它创建一个新的结点
self.root=[self putNode:self.root key:key value:value];
}-(BinaryNode *)putNode:(BinaryNode *)node key:(NSString *)key value:(NSString *)value{
if (node==nil) {
BinaryNode *newNode=[[BinaryNode alloc]init];
[newNode initWithData:key value:value childCount:1];
return newNode;
}
NSInteger compare=[key integerValue]-[node.key integerValue];
if (compare>0) {
node.right=[self putNode:node.right key:key value:value];
}else if(compare<0){
node.left=[self putNode:node.left key:key value:value];
}else{
node.value=value;
}
node.childCount=[self childSizeCount:node.left]+[self childSizeCount:node.right]+1;
return node;
}-(NSInteger)childSize{
return [self childSizeCount:self.root];
}-(NSInteger)childSizeCount:(BinaryNode *)node{
if (node==nil) {
return 0;
}else{
return node.childCount;
}
}@end |
测试:
|
1
2
3
4
5
6
7
|
BinarySearchTree *binaryTree=[[BinarySearchTree alloc]init];[binaryTree put:@"3" value:@"FlyElephant"];
[binaryTree put:@"9" value:@"http://www.cnblogs.com/xiaofeixiang"];
[binaryTree put:@"10" value:@"博客园"];
[binaryTree put:@"0" value:@"228407086"];
NSString *temp=[binaryTree get:@"9"];
NSLog(@"二叉查找树:%@",temp);
|
效果如下:
本文转自Fly_Elephant博客园博客，原文链接：http://www.cnblogs.com/xiaofeixiang/p/4634487.html，如需转载请自行联系原作者