学步园

  2-d树,昨天写的.今天本想来好好玩会球,不想玩了一小会就散伙了.于是来上会网.

  这个东西,支持二维的范围查找,十分有用.关于优化的部分,我并不承认.我觉得我所知的那种优化方式开销太大,而且实现十分困难,于是没有去实现.写的这套ADT很不错,关于范围查找非递归的实现,我想到了层序遍历,这真是一个好主意,我都为自己高兴,觉得自己的想法很到位.事实证明,问题也确实依次解决的,很不错,很不错.呵呵.

  如果自顶向下进行判断,左右子树都要判断,并且左右子树很有可能同时满足条件,于是不适用递归很难实现,层序遍历真是个好办法.好吧,不多夸自己了.贴出来了.

/* 2dTree.h -- 2-d树头文件 */<br /> #include <stdio.h><br /> #include <stdlib.h></p> <p>/* 明显常量定义 */</p> <p>#define FALSE (0)<br /> #define TRUE (1)<br /> #define TWO (2)<br /> #define MASK (1)</p> <p>/* 数据类型定义 */</p> <p>typedef int BOOL ;</p> <p>/* 2-d树部分 */<br /> typedef int Item ;<br /> typedef struct node<br /> {<br /> Item item[TWO] ;<br /> int deleted ;<br /> struct node * left, * right ;<br /> } Node ;<br /> typedef struct twoDTree<br /> {<br /> Node * root ;<br /> int current ;<br /> } * TwoDTree ;</p> <p>/* 队列部分 */<br /> typedef struct queueNode<br /> {<br /> Node * node ;<br /> int index ;<br /> struct queueNode * next ;<br /> } QueueNode ;<br /> typedef struct queue<br /> {<br /> QueueNode * front, * rear ;<br /> int current ;<br /> } * Queue ;</p> <p>/* 接口函数声明 */</p> <p>/* 队列部分 */<br /> /* 操作: 创建并初始化一个队列 */<br /> /* 操作前: pq 指向一个队列 */<br /> /* 操作前: 如果内存分配成功, 创建并初始化该队列, 返回 TRUE ; 否则返回 FALSE */<br /> /* 时间复杂度: O (1) */<br /> BOOL Initialize_Q (Queue * const pq) ;</p> <p>/* 操作: 确定队列是否为空 */<br /> /* 操作前: pq 指向一个已初始化的队列 */<br /> /* 操作后: 如果该队列为空, 返回 TRUE ; 否则返回 FALSE */<br /> /* 时间复杂度: O (1) */<br /> BOOL IsEmpty_Q (const Queue * const pq) ;</p> <p>/* 操作: 向队列中添加一个数据域为指定数据的结点 */<br /> /* 操作前: pq 指向一个已初始化的队列, pn 和 index 是待添加的数据 */<br /> /* 操作后: 如果内存分配成功, 向该队列中添加数据域为 pn 和 index 的结点, 返回 TRUE ; 否则返回 FALSE */<br /> /* 时间复杂度: O (1) */<br /> BOOL EnQueue_Q (const Queue * const pq, Node * const pn, const int index) ;</p> <p>/* 操作: 删除队列头部的结点, 取出该结点指向地址的值赋给 * pqn */<br /> /* 操作前: pq 指向一个已初始化的队列, pqn 是一个指向QueueNode类型结点的指针 */<br /> /* 操作后: 如果该队列非空, 删除该队列头部结点, 取出该结点指向地址的值赋给 * pqn, 返回 TRUE ; 否则返回 FALSE */<br /> /* 时间复杂度: O (1) */<br /> BOOL DeQueue_Q (const Queue * const pq, QueueNode * const pqn) ;</p> <p>/* 操作: 释放一个队列占用的内存空间 */<br /> /* 操作前: pq 指向一个已初始化的队列 */<br /> /* 操作后: 该队列占用的内存空间被释放 */<br /> /* 时间复杂度: O (N) */<br /> void Release_Q (const Queue * const pq) ;</p> <p>/* 2-d树部分 */<br /> /* 操作: 创建并初始化一个2-d树 */<br /> /* 操作前: pt 指向一棵2-d树 */<br /> /* 操作后: 如果内存分配成功, 创建并初始化该2-d树, 返回 TRUE ; 否则返回 FALSE */<br /> /* 时间复杂度: O (1) */<br /> BOOL Initialize_T (TwoDTree * const pt) ;</p> <p>/* 操作: 确定一棵2-d树是否为空 */<br /> /* 操作前: pt 指向一棵已初始化的2-d树 */<br /> /* 操作后: 如果该2-d树为空, 返回 TRUE ; 否则返回 FALSE */<br /> /* 时间复杂度: O (1) */<br /> BOOL IsEmpty_T (const TwoDTree * const pt) ;</p> <p>/* 操作: 向一棵2-d树中插入数据域为指定数据的结点 */<br /> /* 操作前: pt 指向一棵已初始化的2-d树, pi 指向第一个待添加数据的地址 */<br /> /* 操作后: 如果内存分配成功, 向该2-d树中添加数据域为 pi[0] 和 pi[1] 的结点(重复元将添加到右子树上), 返回 TRUE ; 否则返回 FALSE */<br /> /* 平均时间复杂度: O (log N) */<br /> BOOL Insert_T (const TwoDTree * const pt, const Item * const pi) ;</p> <p>/* 操作: 在一棵2-d树中将一个函数作用于满足查找范围的所有结点1次 */<br /> /* 操作前: pt 指向一棵已初始化的2-d树, low 和 high 分别是指向相应范围数据中第一个数据的指针, pfun 指向一个没有返回值, 接受一个 Node * 类型参数的函数 */<br /> /* 操作后: 将 pfun 指向的函数作用于满足范围的所有结点1次, 返回找到的结点的个数 */<br /> /* 平均时间复杂度: O (log N) */<br /> int Find_T (const TwoDTree * const pt, const Item * const low, const Item * const high, void (* pfun) (const Node * const pn)) ;</p> <p>/* 操作: 从一棵2-d树中懒惰删除数据域为指定数据的所有结点 */<br /> /* 操作前: pt 指向一棵已初始化的2-d树, pi 是指向第一个待删除数据的指针 */<br /> /* 操作后: 删除数据域为待删除数据并且未被删除的结点, 返回此次调用删除结点的个数 */<br /> /* 平均时间复杂度: O (log N) */<br /> int Delete_T (const TwoDTree * const pt, const Item * const pi) ;</p> <p>/* 操作: 释放一棵2-d树占用的内存空间 */<br /> /* 操作前: pt 指向一棵已初始化的2-d树 */<br /> /* 操作后: 该2-d树占用的内存空间被释放 */<br /> /* 平均时间复杂度: O (log N) */<br /> void Release_T (const TwoDTree * const pt) ;