二叉树数据结构完全实现(非递归遍历)

最近为了准备考MSE研究生，也顺便复习了一下数据结构的理论知识，其中书中留了一个问题，算是习题吧，叫我们用非递归的方式遍历二叉树。我想既然算是复习，就自己再写一次吧。

二叉树ADT，是一个节点最多可有两个子节点的抽象数据类型，当结点数是N时，树的平均深度是O(根号N)，平均查找时间在O(logN)。二叉树在计算机中有着非常广泛的应用，例如数据索引（二叉查找树），编译器设计（表达式树）等等。

遍历二叉树就是用不同的方式，把二叉树里面的数据逐一遍历出来，不同的遍历方式有不同的效果，例如中序遍历，遍历出来的数据一般都是已经排序的，后序遍历可以构建表达式树等。遍历的时候使用递归，当数据量很大时，可能因为应用程序自身的堆栈空间不够而导致程序的崩溃。如果自己建立堆栈的话，不仅可以保证堆栈够用，而且还减少函数调用时保存程序上下文的开销。

然后下面就是问题的解答了，这算是个完整的二叉查找树非递归遍历实现。

/**
* BTree.h
* By Hoverlees http://www.hoverlees.com
* me[at]hoverlees.com
*/
#ifndef _HOVERLEES_BTREE_H
#define _HOVERLEES_BTREE_H

typedef struct _BTREE_NODE{
	char*	key;
	long	data;
	struct _BTREE_NODE* left;
	struct _BTREE_NODE* right;
	char	mem[0]; //注意这儿，在windows下使用VC编译可能需要指定长度为1。
}BTREE_NODE;

typedef struct _BTREE_NODE_STACK{
	int pos;
	BTREE_NODE* stack[0]; //这儿同上
}BTREE_NODE_STACK;

typedef struct _BTREE{
	int numNodes;
	BTREE_NODE* root;
}BTREE;

typedef int (*BTREE_TRAVERSE_CB)(BTREE_NODE* node);

BTREE* btree_create();
BTREE_NODE* btree_create_node(const char* key,long data);
int btree_insert_node(BTREE* tree,const char* key,long data);
BTREE_NODE* btree_find(BTREE* tree,const char* key);
int btree_delete_node(BTREE* tree,const char* key);
int btree_inorder_traverse(BTREE* tree,BTREE_TRAVERSE_CB callback);
int btree_preorder_traverse(BTREE* tree,BTREE_TRAVERSE_CB callback);
int btree_postorder_traverse(BTREE* tree,BTREE_TRAVERSE_CB callback);
int btree_destroy(BTREE* tree);

#endif

/**
* BTree.c
* By Hoverlees http://www.hoverlees.com
* me[at]hoverlees.com
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "BTree.h"

/**
 * 内部使用的函数。
 */
BTREE_NODE* btree_create_node(const char* key,long data){
	BTREE_NODE* node=(BTREE_NODE*) calloc(sizeof(BTREE_NODE)+strlen(key),1);
	if(!node) return NULL;
	node->key=node->mem;
	strcpy(node->key,key);
	node->data=data;
	return node;
}

/**
 * 创建一颗二叉树。也可以理解成创建一个map,此代码已提供key->value的索引功能。
 */
BTREE* btree_create(){
	BTREE* tree=(BTREE*) calloc(sizeof(BTREE),1);
	if(tree==NULL) return NULL;
	return tree;
}

/**
 * 插入一个节点。
 */
int btree_insert_node(BTREE* tree,const char* key,long data){
	BTREE_NODE* p;
	int comp;
	p=tree->root;
	if(!p){
		tree->root=btree_create_node(key,data);
		tree->numNodes++;
		return 1;
	}
	while(p){
		comp=strcmp(key,p->key);
		if(comp>0){
			if(p->right==NULL){
				p->right=btree_create_node(key,data);
				tree->numNodes++;
				return 1;
			}
			p=p->right;
		}
		else if(comp<0){
			if(p->left==NULL){
				p->left=btree_create_node(key,data);
				tree->numNodes++;
				return 1;
			}
			p=p->left;
		}
		else{
			p->data=data;
			return 2;
		}
	}
}
/**
 * 查找节点，反回找到的node.
 */
BTREE_NODE* btree_find(BTREE* tree,const char* key){
	BTREE_NODE* p;
	int comp;
	p=tree->root;
	while(p){
		comp=strcmp(key,p->key);
		if(comp>0){
			p=p->right;
		}
		else if(comp<0){
			p=p->left;
		}
		else{
			return p;
		}
	}
	return NULL;
}

/**
 * 删除节点。
 */
int btree_delete_node(BTREE* tree,const char* key){
	BTREE_NODE* p;
	BTREE_NODE* temp;
	BTREE_NODE** prevTmpPos=NULL;
	BTREE_NODE** prevPos=NULL;
	int comp;
	prevPos=&tree->root;
	p=tree->root;
	while(p){
		comp=strcmp(key,p->key);
		if(comp>0){
			prevPos=&p->right;
			p=p->right;
		}
		else if(comp<0){
			prevPos=&p->left;
			p=p->left;
		}
		else{
			if(p->left){
				temp=p->left;
				while(temp->right){
					prevTmpPos=&temp->right;
					temp=temp->right;
				}
				if(prevTmpPos==NULL){
					*prevPos=temp;
					temp->right=p->right;
				}
				else{
					if(temp->left){
						*prevTmpPos=temp->left;
					}
					else{
						*prevTmpPos=NULL;
					}
					*prevPos=temp;
					temp->left=p->left;
					temp->right=p->right;
				}
				free(p);
			}
			else if(p->right){
				temp=p->right;
				while(temp->left){
					prevTmpPos=&temp->left;
					temp=temp->left;
				}
				if(prevTmpPos==NULL){
					*prevPos=temp;
					temp->left=p->left;
				}
				else{
					if(temp->right){
						*prevTmpPos=temp->right;
					}
					else{
						*prevTmpPos=NULL;
					}
					*prevPos=temp;
					temp->left=p->left;
					temp->right=p->right;
				}
				free(p);
			}
			else{
				free(p);
				*prevPos=NULL;
			}
			tree->numNodes--;
			return 1;
		}
	}
	return 0;
}

/**
 * 中序变历二叉树，每个节点调用callback
 */
int btree_inorder_traverse(BTREE* tree,BTREE_TRAVERSE_CB callback){
	BTREE_NODE* p;
	int ret=1;
	BTREE_NODE_STACK* stack=(BTREE_NODE_STACK*) malloc(sizeof(BTREE_NODE_STACK)+(sizeof(BTREE_NODE*)*tree->numNodes));
	stack->pos=0;
	p=tree->root;
	while(p!=NULL || stack->pos>0){
		while(p!=NULL){
			stack->stack[stack->pos++]=p;
			p=p->left;
		}
		if(stack->pos>0){
			p=stack->stack[--stack->pos];
			if(!callback(p)){
				ret=0;
				break;
			}
			p=p->right;
		}
	}
	free(stack);
	return ret;
}
/**
 * 前序遍历
 */
int btree_preorder_traverse(BTREE* tree,BTREE_TRAVERSE_CB callback){
	BTREE_NODE* p;
	int ret=1;
	BTREE_NODE_STACK* stack=(BTREE_NODE_STACK*) malloc(sizeof(BTREE_NODE_STACK)+(sizeof(BTREE_NODE*)*tree->numNodes));
	stack->pos=0;
	p=tree->root;
	while(p!=NULL || stack->pos>0){
		while(p!=NULL){
			stack->stack[stack->pos++]=p;
			if(!callback(p)){
				ret=0;
				break;
			}
			p=p->left;
		}
		if(stack->pos>0){
			p=stack->stack[--stack->pos];
			p=p->right;
		}
	}
	free(stack);
	return ret;
}
/**
 * 后序遍历
 */
int btree_postorder_traverse(BTREE* tree,BTREE_TRAVERSE_CB callback){
	BTREE_NODE* p;
	int ret=1;
	BTREE_NODE_STACK* stack=(BTREE_NODE_STACK*) malloc(sizeof(BTREE_NODE_STACK)+(sizeof(BTREE_NODE*)*tree->numNodes));
	stack->pos=0;
	p=tree->root;
	while(p!=NULL || stack->pos>0){
		while(p!=NULL){
			stack->stack[stack->pos++]=p;
			p=p->right;
		}
		if(stack->pos>0){
			p=stack->stack[--stack->pos];
			if(!callback(p)){
				ret=0;
				break;
			}
			p=p->left;
		}
	}
	free(stack);
	return ret;
}
/**
 * btree_destroy使用
 */
int btree_free_each_node(BTREE_NODE* node){
	free(node);
	return 1;
}

/**
 * 删除二叉树
 */
int btree_destroy(BTREE* tree){
	if(!tree) return 0;
	btree_inorder_traverse(tree,btree_free_each_node);
	free(tree);
	return 1;
}