Posted on 2009-03-29 19:32
besterChen 阅读(647)
评论(2) 编辑 收藏 引用
最近把我知道的大牛的博客都拜读了一下，看到这个，感觉能用到，就转过来了，省的以后自己写，偷个懒，
嘿嘿`~
#include <stdio.h>
#include <windows.h>
#define STACK_STRUCT_SIZE 1048576
typedef struct _BST_NODE {
PVOID data;
struct _BSTNODE *left, *right;
} BST_NODE, *PBST_NODE;
typedef struct _STACK_STRUCT {
ULONG ptr;
PVOID data[STACK_STRUCT_SIZE];
} STACK_STRUCT, *PSTACK_STRUCT;
VOID IcyAllocateStack(OUT PSTACK_STRUCT *Stack)
{
PSTACK_STRUCT stack;
stack = malloc(sizeof(STACK_STRUCT));
stack->ptr = 0;
*Stack = stack;
}
VOID IcyFreeStack(IN PSTACK_STRUCT Stack)
{
free(Stack);
}
BOOLEAN IcyPushStack(IN OUT PSTACK_STRUCT Stack, IN PVOID Data)
{
int ptr = Stack->ptr;
if (ptr == STACK_STRUCT_SIZE - 1) {
return FALSE;
} else {
Stack->data[ptr] = Data;
Stack->ptr = ptr + 1;
return TRUE;
}
}
BOOLEAN IcyPopStack(IN OUT PSTACK_STRUCT Stack, OUT PVOID *Data)
{
int ptr = Stack->ptr;
if (ptr) {
ptr--;
*Data = Stack->data[ptr];
Stack->ptr = ptr;
return TRUE;
} else {
return FALSE;
}
}
VOID IcyAllocateBSTNode(OUT PBST_NODE *Node, IN PVOID Data)
{
PBST_NODE node;
node = malloc(sizeof(BST_NODE));
node->data = Data;
node->left = 0;
node->right = 0;
*Node = node;
}
VOID IcyBSTInsertData(IN OUT PBST_NODE *Node, IN PVOID Data)
{
while (1) {
if (*Node) {
if (Data < (*Node)->data) {
Node = (PBST_NODE *)&((*Node)->left);
} else {
Node = (PBST_NODE *)&((*Node)->right);
}
} else {
IcyAllocateBSTNode(Node, Data);
break;
}
}
}
VOID IcyBSTMidOrder(IN PBST_NODE Node, VOID (*IN CALLBACK CallbackFunction) (PBST_NODE))
{
PSTACK_STRUCT stack;
if (Node) {
IcyAllocateStack(&stack);
while (1) {
if (Node->left) {
if (!IcyPushStack(stack, Node)) break;
Node = (PBST_NODE)Node->left;
} else {
loop:
CallbackFunction(Node);
if (Node->right) {
Node = (PBST_NODE)Node->right;
} else if (IcyPopStack(stack, (PVOID *)&Node)) {
goto loop;
} else {
break;
}
}
}
IcyFreeStack(stack);
}
}
VOID MidOrderCallback(PBST_NODE Node)
{
printf("%d\n", Node->data);
}
int main()
{
BST_NODE *tree = 0;
int x;
do {
scanf("%d", &x);
IcyBSTInsertData(&tree, (PVOID)x);
} while (x);
IcyBSTMidOrder(tree, MidOrderCallback);
return 0;
}
（声明：以上代码转载于 ：
iceboy @ baidu.hi）