iOS标准库中常用数据结构和算法之二叉排序树

上一篇：iOS标准库中常用数据结构和算法之排序

二叉排序树

功能：二叉排序树的标准实现是一颗平衡二叉树。二叉排序树主要用来解决高效插入和高效检索以及进行排序的问题。系统分别提供了二叉排序树节点的查找、添加、删除、遍历4个功能。

iOS中实现的二叉排序树并不是一颗平衡二叉树，因此进行检索时其时间复杂度可能不是O(logN)。这里极度鄙视一下！但是其它UNIX系统中的实现则是正确的。

对于二叉排序树节点的数据结构，系统给出了一个模板：

typedef	struct node {
	char *key; //第一个数据成员必须是指针类型！
	struct node *llink; //左子树 
 struct node *rlink; //又子树
} node_t;
复制代码

要实现用二叉排序树时需要我们自己来定义节点的数据结构，因为下列函数中所有关于节点的参数都是void*类型的。所以其内部实现不关心结构体是如何的，但是一定要满足上面的模板的格式。

头文件：#include <search.h>

平台: BSD Unix。

1.查找和添加

函数签名：

 //查找节点，如果找不到则返回NULL。
 void *tfind(const void *key, void *const *rootp, int (*compar) (const void *key1, const void *key2));
//查找节点，如果找不到则添加到树中去。
 void *tsearch(const void *key, void **rootp, int (*compar) (const void *key1, const void *key2));
复制代码

参数：

key:[in] 要查找或者插入的内容

rootp:[in/out] 二叉树根节点指针的指针，这里作为输出的原因是因为要构造出一颗平衡二叉树，所以树根节点可能会变化。如果要建立的是第一个节点则可以传一个空指针的指针作为输入输出。

compar:[in] 节点函数比较器，这个比较器的格式如下：

/*
@key1: 函数传递进来的关键字。
@key2: 树中节点中的关键字，注意的是这个参数并不是树的节点指针而是节点中的key数据成员。
@return: 如果比较结果相等则返回0, 如果key1在key2前返回小于0，如果key1在key2后面则返回大于0
*/
 int compar(const void *key1, const void *key2);
复制代码

return:[out] 对于tfind来说如果在树中查找到对应的节点则返回节点指针，如果没有找到则返回NULL。对于tsearch来说如果在树中查找到对应的节点则返回节点指针，如果没有找到则会将创建一个新的节点并将要查找的key作为新插入节点的key属性，同时把新创建的节点返回。

描述：

这两个函数分别负责查找和插入操作。树节点的内存分配和构建由系统来完成。

2.删除

函数签名：

void * tdelete(const void *restrict key, void **restrict rootp, int (*compar) (const void *key1, const void *key2));
复制代码

参数： key:[in] 要删除的节点key属性。 rootp:[in/out] 树的根节点，随着节点的删除为了保证平衡性会调节树的根节点，因此这里需要传递指针的指针值。 compar:[in] 节点函数比较器。 return:[out] 返回删除的节点的父节点指针，如果删除的是根节点则返回根节点本身，如果要删除的key并不在树中则返回NULL。

描述 系统内部负责节点内存的创建和销毁，因此当某个树节点被删除后这个树节点内存会被销毁而不能再访问了，否则会出现crash。

3.遍历

函数签名：

void twalk(const void *root, void (*action) (const void *node, VISIT order, int level));
复制代码

参数：

root:[in] 树的根节点指针，注意这里不是指针的指针。因为遍历不会调整树的根节点。

action:[in] 遍历一棵树有前序遍历、中序遍历和后序遍历三种遍历方式，因为系统不知道你要怎么处理遍历的节点，因此通过提供一个回调函数来实现节点的遍历。这个回调函数的格式如下：

@node: 要遍历的节点。
@order:要遍历的顺序，这个VISIT是一个枚举类型。
@level: 当前遍历的节点所处的树的层级，层级以0开始，对应树根节点的层级。
void action(const void *node, VISIT order, int level);
复制代码

描述：

可以看出上面要实现遍历时必须提供一个回调的action函数，在action函数中通过对VISIT类型的参数order进行判断可以实现各种遍历。VISIT的定义如下：

typedef	enum {
	preorder,
	postorder,
	endorder,
	leaf
} VISIT;
复制代码

当order的值是preorder或者leaf时系统将执行的是前序遍历，当order的值是postorder或者leaf时系统将执行的是中序遍历，当order的值是endorder或者leaf时系统将执行的是后序遍历，当order的值是leaf系统将执行的叶子遍历。下面的代码将演示对遍历的处理。

void action(const void *node, VISIT order, int level)
{
 if (order == preorder || order == leaf)
 {
 //前序遍历
 }
 
 if (order == postorder || order == leaf)
 {
 //中序遍历
 }
 if (order == endorder || order == leaf)
 {
 //后序遍历
 }
 
 if (order == leaf)
 {
 //只遍历叶子
 }
}
复制代码

示例代码

//定义一个树节点类型，节点必须按这个格式定义
typedef struct _node
{
 char *key; //树节点的内容。
 struct _node *left;
 struct _node *right;
}node_t;
//树排序比较器函数
int bintreecompar(const char *key1, const char *key2)
{
 return strcmp(key1, key2);
}
//树遍历函数，这里进行前序遍历，按树节点升序输出。
void action(node_t *node, VISIT order, int level)
{
 if (order == preorder || order == leaf)
 {
 printf("node's key = %s\n", node->key);
 }
}
void main()
{
 node_t *root = NULL; //定义树的根节点，最开始时根节点为空。
 //添加
 //看这里对root参数传递的规则，因为每次插入都有可能会改变根节点的值。
 node_t *p1 = tsearch("Bob", &root, bintreecompar); //返回节点对象，我们不需要负责节点对象的销毁，而是通过调用tdelete函数来销毁。
 NSAssert(strcmp(p1->key, "Bob")==0, @"oops!");
 node_t *p2 = tsearch("Alice", &root, bintreecompar);
 node_t *p3 = tsearch("Max", &root, bintreecompar);
 node_t *p4 = tsearch("Lucy", &root, bintreecompar);
 //查找
 node_t *p = tfind("Lily", &root, bintreecompar);
 NSAssert(p == NULL, @"oops!");
 p = tfind("Lucy", &root, bintreecompar);
 NSAssert(p != NULL, @"oops!");
 //删除
 p = tdelete("Jone", &root, bintreecompar);
 NSAssert(p == NULL, @"oops!");
 p = tdelete("Lucy", &root, bintreecompar);
 NSAssert(p != NULL, @"oops!");
 //遍历树
 twalk(root, action);
}
复制代码