学步园

      用c语言实现了二叉树的数据定义，二叉树的构建、销毁，以及先序、中序、后序的递归算法，非递归算法正在研究中。

/*--------------------------------------------------------------------------------------------*/

// 二叉树的二叉链表存储结构C语言实现。                                                   

// 实现了利用先序序列创建一棵二叉树，先序、中序、后序遍历算法的递归

// 和非递归算法。                                                                                      

// 版本： v1.0

// 环境：Visual C++ 6.0

// 作者： sunnyrain

// 日期： 2007-8-24

/*--------------------------------------------------------------------------------------------*/

//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;
}