//BiTree.h
struct BiTNode //采用二叉链表存储结构
{
char data;
struct BiTNode* lchild;
struct BiTNode* rchild;
}BiTNode;
struct BiTNode* CreateBiTree();
int DestroyBiTree(struct BiTNode* T);
int visit(char elem);
//递归遍历算法
int PreOrderTraverse_R(struct BiTNode* T, int (*visit)(char elem));
int InOrderTraverse_R(struct BiTNode* T, int (*visit)(char elem));
int PostOrderTraverse_R(struct BiTNode* T, int (*visit)(char elem));
//非递归遍历算法
void PreOrderTraverse(struct BiTNode* T, int (*visit)(char elem));
void InOrderTraverse(struct BiTNode* T, int (*visit)(char elem));
void PostOrderTraverse(struct BiTNode* T, int (*visit)(char elem));
//stack.h 堆栈数据结构，用于非递归算法中的附加空间
#define STACK_SIZE 256
struct stack
{
struct BiTNode* elem[STACK_SIZE];
int top; //top总是指向栈顶元素的上一个元素
int bottom; //恒0
};
void initStack(struct stack* s);
struct BiTNode* getTop(struct stack* s);
struct BiTNode* pop(struct stack* s);
void push(struct stack* s,struct BiTNode* p);
int isEmpty(struct stack* s);
//stack.c 堆栈的实现
#include<stdio.h>
#include<string.h>
#include "stack.h"
//初始化堆栈为0，栈指针为0
void initStack(struct stack* s)
{
memset(s->elem,0,STACK_SIZE);
s->top = s->bottom = 0;
}
//获取栈顶元素，栈顶指针不变
struct BiTNode* getTop(struct stack* s)
{
return s->elem[s->top-1];
}
//弹出&返回栈顶元素
struct BiTNode* pop(struct stack* s)
{
if(s->top == s->bottom) //若栈空
{
printf("Stack is empty!\n");
return 0;
}
--s->top;
return s->elem[s->top];
}
//将pB指针压入栈中
void push(struct stack* s,struct BiTNode* pB)
{
if(s->top<STACK_SIZE) //栈未满
{
s->elem[s->top] = pB;
++s->top;
}
else
printf("Stack is full!\n");
}
//判断栈是否为空，空返回非0
int isEmpty(struct stack* s)
{
return s->top == s->bottom;
}
//BiTree.c 二叉树创建、销毁、递归算法实现
#include<stdio.h>
#include<malloc.h>
#include "BiTree.h"
#include "stack.h"
struct BiTNode* CreateBiTree() //采用先序递归方法创建一棵二叉树
{
struct BiTNode* T;
char ch,tmp;
printf("please input the value of the node:\n");
scanf("%c",&ch);
tmp = getchar(); //忽略回车符
if(ch == ''&'') //输入&符号表示此节点为空
{
printf("Null BiTreeNode Created!\n");
T = NULL;
return NULL;
}
T = (struct BiTNode *)malloc(sizeof(BiTNode)); //为当前节点分配内存
if(!T)
{
printf("Allocate memory failed!\n");
return NULL;
}
T->data = ch; //为当前节点赋值
T->lchild = CreateBiTree(); //递归创建左子树
T->rchild = CreateBiTree(); //递归创建右子树
return T;
}
//销毁二叉树,销毁成功返回0，错误返回1
int DestroyBiTree(struct BiTNode* T)
{
if(T)
{
struct BiTNode* lchild = T->lchild;
struct BiTNode* rchild = T->rchild;
free(T);
if(0 == DestroyBiTree(lchild))
{
if(0 == DestroyBiTree(rchild))
return 0;
else
return 1;
}
}
return 0;
}
//访问节点元素
int visit(char elem)
{
if(elem == ''&'')
return 1;
printf("%c ",elem);
return 0;
}
//先序遍历递归算法,返回值为0表示遍历成功，1为失败
int PreOrderTraverse_R(struct BiTNode* T, int (*visit)(char elem))
{
if(T)
{
if(0 != visit(T->data)) //访问根节点
return 1;
if(T->lchild)
{
if(0 != InOrderTraverse_R(T->lchild,visit)) //递归遍历左子树
return 1;
}
if(T->rchild)
{
if(0 != InOrderTraverse_R(T->rchild,visit)) //递归遍历右子树
return 1;
}
}
return 0;
}
//中序遍历递归算法,返回值为0表示遍历成功，1为失败
int InOrderTraverse_R(struct BiTNode* T, int (*visit)(char elem))
{
if(T)
{
if(T->lchild)
{
if(0 != InOrderTraverse_R(T->lchild,visit)) //递归遍历左子树
return 1;
}
if(0 != visit(T->data)) //访问根节点
return 1;
if(T->rchild)
{
if(0 != InOrderTraverse_R(T->rchild,visit)) //递归遍历右子树
return 1;
}
}
return 0;
}
//后序遍历递归算法,返回0表示遍历成功，1为失败
int PostOrderTraverse_R(struct BiTNode* T, int (*visit)(char elem))
{
if(T)
{
if(T->lchild)
{
if(0 != PostOrderTraverse_R(T->lchild,visit)) //递归遍历左子树
return 1;
}
if(T->rchild)
{
if(0 != PostOrderTraverse_R(T->rchild,visit)) //递归遍历右子树
return 1;
}
if(0 != visit(T->data)) //访问根节点
return 1;
}
return 0;
}
//先序遍历非递归算法
void PreOrderTraverse(struct BiTNode* T, int (*visit)(char elem))
{
struct stack ss;
struct BiTNode* p = T;
initStack(&ss);
while(p||!isEmpty(&ss))
{
if(p)
{
visit(p->data);
push(&ss,p);
p=p->lchild;
}
else
{
p = getTop(&ss);
pop(&ss);
p = p->rchild;
}
}
}
//中序遍历非递归算法
void InOrderTraverse(struct BiTNode* T, int (*visit)(char elem))
{
struct stack ss;
struct BiTNode* p;
initStack(&ss);
push(&ss,T);
while(!isEmpty(&ss))
{
while(p = getTop(&ss))
push(&ss,p->lchild); //向左走到尽头
p = pop(&ss); //空指针退栈
if(!isEmpty(&ss))
{
p = pop(&ss);
visit(p->data); //访问节点
push(&ss,p->rchild); //向右一步
}
}
}
//后序遍历非递归算法
void PostOrderTraverse(struct BiTNode* T, int (*visit)(char elem))
{
struct stack ss;
struct BiTNode* p = T;
struct BiTNode* q;
initStack(&ss); //初始化空栈
while(p || !isEmpty(&ss))
{
if(p)
{
push(&ss,p);
p = p->lchild;
}
else
{
p =getTop(&ss);
if(p)
{
push(&ss,NULL);
p = p->rchild;
}
else
{
pop(&ss);
q = pop(&ss);
visit(q->data);
}
}
}
}
//main.c 测试主程序
#include<stdio.h>
#include "BiTree.h"
int main()
{
struct BiTNode* bt = 0;
bt = CreateBiTree(bt);
printf("先序遍历序列：\n");
PreOrderTraverse_R(bt,visit);
printf("\n中序遍历序列：\n");
InOrderTraverse_R(bt,visit);
printf("\n后序遍历序列：\n");
PostOrderTraverse_R(bt,visit);
printf("\n非递归先序遍历序列：\n");
PreOrderTraverse(bt,visit);
printf("\n非递归中序遍历序列：\n");
InOrderTraverse(bt,visit);
printf("\n非递归后序遍历序列：\n");
PostOrderTraverse(bt,visit);
DestroyBiTree(bt);
return 0;
}
