Posted on 2010-03-16 09:57
sin 阅读(588)
评论(0) 编辑 收藏 引用 所属分类:
数据结构算法
这里的二叉树不是一般的二叉树，而是棵二叉查找树。
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 128
struct node
{
int data;
struct node* lchild;
struct node* rchild;
};
struct bin_search_tree
{
struct node* root;
};
void init_search_tree(struct bin_search_tree *tree);
void clear_search_tree(struct bin_search_tree *tree);
void insert_node(struct bin_search_tree *tree, int element);
void pre_order(struct node *p);
void in_order(struct node *p);
void post_order(struct node *p);
void visit(struct node *p);
int main()
{
struct bin_search_tree tree;
int i,arr[] = {40, 30, 50, 11, 27, 98, 74, 79, 9, 150, 37};
init_search_tree(&tree);
for (i=0; i<sizeof(arr)/sizeof(int); i++)
{
insert_node(&tree, arr[i]);
}
//前序遍历
pre_order(tree.root);
printf("\n");
//中序遍历
in_order(tree.root);
printf("\n");
//后续遍历
post_order(tree.root);
printf("\n");
clear_search_tree(&tree);
getchar();
return 0;
}
/*
* 二叉树的初始化
*/
void init_search_tree(struct bin_search_tree *tree)
{
tree->root = NULL;
}
/*
* 清除二叉树，用二叉树层次遍历
*/
void clear_search_tree(struct bin_search_tree *tree)
{
int i,j;
struct node *p,*queue[MAX_SIZE];
i = j = 0;
queue[0] = tree->root;
while (i<=j)
{
for ( ; i<=j; i++ )
{
p = queue[i];
if (p->lchild)
queue[++j] = p->lchild;
if (p->rchild)
queue[++j] = p->rchild;
}
}
for (i=0; i<=j; i++)
{
free(queue[i]);
}
tree->root = NULL;
}
/*
* 二叉树中插入节点element
*/
void insert_node(struct bin_search_tree *tree, int element)
{
struct node *p = tree->root;
struct node *child, *newnode;
newnode = (struct node*)malloc(sizeof(struct node));
newnode->data = element;
newnode->lchild = NULL;
newnode->rchild = NULL;
if (tree->root == NULL)
{
tree->root = newnode;
return;
}
while (p)
{
if ( element < p->data )
{
child = p->lchild;
if (NULL == child)
{
p->lchild = newnode;
return;
}
}
else
{
child = p->rchild;
if (NULL == child)
{
p->rchild = newnode;
return;
}
}
p = child;
}
}
/*
* 前序遍历，非递归
*/
void pre_order(struct node *p)
{
int top = -1;
struct node *stack[MAX_SIZE];
if (p == NULL)
return;
stack[++top] = p;
while (top>-1)
{
visit(p=stack[top--]);
if (p->rchild)
stack[++top] = p->rchild;
if (p->lchild)
stack[++top] = p->lchild;
}
}
/*
* 中序遍历，非递归
*/
void in_order(struct node *p)
{
int top = -1;
struct node *stack[MAX_SIZE];
while (top>-1 || p!=NULL)
{
while (p)
{
stack[++top] = p;
p = p->lchild;
}
visit(p=stack[top--]);
p = p->rchild;
}
}
/*
* 后序遍历，非递归
*/
void post_order(struct node *p)
{
int top = -1;
int flag[MAX_SIZE];
struct node *stack[MAX_SIZE];
while (top>-1 || p!= NULL)
{
while (p) //将p的所有左节点压入栈
{
stack[++top] = p;
flag[top] = 0;
p = p->lchild;
}
p = stack[top]; //弹出栈顶
if (flag[top--]==0 && p->rchild)
{
stack[++top] = p;
flag[top] = 1;
p = p->rchild;
}
else
{
visit(p);
p = NULL; //将p置为NULL，防止进入while(p)循环
}
}
}
/*
* 访问一个节点
*/
void visit(struct node *p)
{
printf("%d ", p->data);
}