最近总有人问这个问题：“如何不用栈，也不用递归来实现二叉树的中序遍历”。这个问题的实现就是迭代器问题，无论是Java还是C++，利用迭代器遍历树节点(Java中是TreeMap类，C++中是map类）都使用了中序遍历，且无法使用递归和栈，算法效率近似为O(1)，不可能每个节点只访问一次。
纯C实现的办法很简单，先定义类型。
// 定义byte_t类型 typedef unsigned char byte_t; // 定义bool类型 typedef unsigned char bool; #define true 1 #define false 0
// 定义用于比较的函数指针类型 typedef int(*treeset_compare_t)(const void*, const void*);
下面结构体中的data[0]是C语言一种特殊用法，data[0]本身不表示任何大小，可以看作是一个指针，表明该结构体在内存中占据的实际大小会超过结构体本身的字节数，这样，data指针就自动指向结构体中多余的空间，该空间可以用来存储节点值。并不是所有的C编译器都能这么做，但我测试过好像就VC++6不行，这段代码在GCC下编译通过。
/**
* 定义二叉树节点类型
*/
typedef struct _btree_node
{
struct _btree_node* parent; // 指向父节点的指针
struct _btree_node* lchild; // 指向左孩子的指针
struct _btree_node* rchild; // 指向右孩子的指针
struct _treeset* owner; // 节点所属的树
byte_t data[0];
} btree_node;
/**
* 定义二叉树结构体
*/
typedef struct _treeset
{
struct _btree_node* root; // 二叉树根节点
size_t count; // 二叉树节点数量
size_t elemsize;
treeset_compare_t compare;
} treeset;
定义了以上类型，就可以进一步完成二叉树初始化以及节点添加，删除，查找等函数了，函数声明如下。
/** * 初始化二叉树结构体 * @param tree 指向二叉树结构体的指针 * @param elemsize 每个元素的大小 * @param comp 用于比较的函数指针 */ void treeset_init(treeset* tree, size_t elemsize, treeset_compare_t comp); /** * 释放二叉树占据的空间 * @param tree 指向二叉树结构体的指针 */ void treeset_free(treeset* tree); /** * 向二叉树中添加元素 * @param tree 指向二叉树结构体的指针 * @param value 指向要添加元素的指针 * @return 是否实际添加了节点 */ bool treeset_add(treeset* tree, const void* value); /** * 从二叉树中删除一个元素 * @param tree 指向二叉树结构体的指针 * @param value 要删除的节点内容 * @return 是否删除了节点 */ bool treeset_remove(treeset* tree, const void* value); /** * 在二叉树中查找一个元素 * @param tree 指向二叉树结构体的指针 * @param value 指向要查找内容的指针 * @return 是否包含要查询的值 */ bool treeset_contain(const treeset* tree, const void* value);
这部分函数实现如下：
下面这个函数用于初始化二叉树，其中参数elemsize表示每个树节点要存放的值所占内存大小，例如每个节点要保存一个整数，则elemsize的值应该为sizeof(int)，这个大小将直接反映在每个树节点上，由节点结构体分量data来表示。comp参数是一个函数指针，前面定义过，用来表示比较两个值的大小。
/**
* 初始化二叉树结构体
* @param tree 指向二叉树结构体的指针
* @param elemsize 每个元素的大小
* @param comp 用于比较的函数指针
*/
void treeset_init(treeset* tree, size_t elemsize, treeset_compare_t comp)
{
tree->root = NULL;
tree->count = 0;
// 设置节点存储的元素大小
tree->elemsize = elemsize;
// 设置用于元素大小比较的函数指针
tree->compare = comp;
}
/**
* 释放二叉树占据的空间
* @param tree 指向二叉树结构体的指针
*/
void treeset_free(treeset* tree)
{
// 从头节点开始移除二叉树中所有的节点
remove_all_node(tree->root);
// 将二叉树所有内容还原为空
memset(tree, 0, sizeof(*tree));
}
/**
* 向二叉树中添加元素
* @param tree 指向二叉树结构体的指针
* @param value 指向要添加元素的指针
* @return 是否实际添加了节点
*/
int treeset_add(treeset* tree, const void* value)
{
int result = 0;
// 判断二叉树中是否有头节点
if (tree->count == 0)
{
// 创建头节点
tree->root = create_new_node(tree, value);
result = 1;
}
else
{
/*
对于添加节点，具体操作如下：
1. 通过要添加节点的值和现有某个节点（从头节点开始）进行比较（通过指定的比较函数进行）
2. 如果要添加的节点值和现有某个节点值相同，则无需添加节点
3. 如果要添加的节点值和现有某个节点值不同，则根据比较结果继续访问该节点的左支或者右支
添加流程示意图参看[图1]
*/
// 表示比较结果
int comp;
// node变量指向要比较的节点，从头结点开始；parent变量指向其父节点
btree_node* node = tree->root, *parent;
// 遍历所有节点，直到没有节点为止
while (node)
{
// 保存父节点指针
parent = node;
// 比较要添加的值和当前节点值
comp = tree->compare(value, node + 1);
// 判断比较结果
if (comp == 0)
break;