聚星亭

吾笨笨且懒散兮 急须改之而奋进
posts - 74, comments - 166, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理
最近把我知道的大牛的博客都拜读了一下,看到这个,感觉能用到,就转过来了,省的以后自己写,偷个懒,
嘿嘿`~

#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

Feedback

# re: [转载] 中序遍历二叉树, 非递归  回复  更多评论   

2010-08-05 00:41 by 小天狼星
这些基础在许多公司的面试题中常见。估计你能考90分了。

# re: [转载] 中序遍历二叉树, 非递归[未登录]  回复  更多评论   

2010-08-08 22:26 by besterChen
@小天狼星
可惜,转载的……

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理