二叉树.txt

这是有关数据结构的例程序

definition.h
=========================================
#define INIT_SIZE 100 //存储空间初始分配量
#define INCREMENT 10  //存储空间分配增量

typedef char TElemType;

typedef struct{
TElemType data;
struct BiTNode *lchild, *rchild;//左右孩子指针
}BiTNode, *BiTree;//二叉树的二叉链表存储表示

typedef struct{
BiTree *top, *base; //栈顶指针和栈底指针
unsigned stacksize;   //当前已分配的存储空间，以元素为单位
}SqStack;

BiTree CreateBiTree(void);//按先序次序输入二叉树中结点的值，'#'代表空树
void PreOrderTraverse(BiTree);//先序遍历二叉树
int InOrderTraverse(BiTree);//中序遍历二叉树，非递归
int InOrderTraverse2(BiTree);
int InitStack(SqStack *);//创建一个空栈
int Push(SqStack *, BiTree);     //插入栈顶
===========================================================================

main.c
================================================
#include <stdio.h>
#include "definition.h"

int main()
{ BiTree bt;

printf("请输入根结点：");
bt = CreateBiTree();//按先序次序创建二叉树
PreOrderTraverse(bt); //先序遍历二叉树
printf("\n");
if( InOrderTraverse(bt) )//中序遍历二叉树，非递归
  return 1;//遍历失败，返回
printf("\n");
if( InOrderTraverse2(bt) )//中序遍历二叉树，非递归
  return 1;//遍历失败，返回
printf("\n");

return 0;
} ===================================================================

function.c
======================================================
#include <stdio.h>
#include <malloc.h>
#include "definition.h"

BiTree CreateBiTree(void)//按先序次序输入二叉树中结点的值，'#'代表空树
{ TElemType e;
BiTree tmp = NULL;

if( (e=getchar())!='#' ){
  getchar();//接收回车符
  tmp=(BiTree)malloc(sizeof(BiTNode));
  if(!tmp)
   return NULL;
  tmp->data=e;
  printf("请输入左孩子：");
  tmp->lchild=CreateBiTree();
  printf("请输入右孩子：");
  tmp->rchild=CreateBiTree();
}
else
  getchar();//接收回车符

return tmp;
}

void PreOrderTraverse(BiTree bt)//先序遍历二叉树
{ if(bt){
  printf("%c", bt->data);
  PreOrderTraverse(bt->lchild);
  //printf("%c", bt->data);不要上面的printf，而用这个printf，则为中序遍历
  PreOrderTraverse(bt->rchild);
  //printf("%c", bt->data);不要上面的printf，而用这个printf，则为后序遍历
}
}

int InOrderTraverse(BiTree bt)//中序遍历二叉树，非递归
{ SqStack S;
BiTree tmp;

if( InitStack(&S) )
  return 1;//如果创建空栈失败，返回1
if( Push(&S, bt) )//根指针进栈
  return 1;//如果压栈失败，返回1
while(S.base!=S.top){
  while( tmp=*(S.top-1) ){
   if( Push(&S, tmp->lchild) )//向左走到尽头
    return 1;
   //printf("%c", tmp->data);//printf放于此处即为先序遍历
  }
  --S.top;//空指针退栈
  //访问结点，向右一步
  if(S.base!=S.top){
   tmp = *(--S.top);
   printf("%c", tmp->data);
   if( Push(&S, tmp->rchild) )
    return 1;
  }
}

free(S.base);
return 0;
}

int InOrderTraverse2(BiTree bt)
{ SqStack S;
BiTree tmp = bt;

if( InitStack(&S) )
  return 1;//如果创建空栈失败，返回1
while( tmp||(S.base!=S.top) ){
  if(tmp){
   if( Push(&S, tmp) )//根指针进栈，遍历左子树
    return 1;
   //printf("%c", tmp->data);//printf放于此处即为先序遍历
   tmp = tmp->lchild;
  }
  //根指针退栈，访问根结点，遍历右子树
  else{
   tmp = *(--S.top);
   printf("%c", tmp->data);
   tmp = tmp->rchild;
  }
}

free(S.base);
return 0;
}

int InitStack(SqStack *S) //创建一个空栈
{ S->base=(BiTree *)malloc( INIT_SIZE * sizeof(BiTree) );
if(!S->base) //空间分配失败
  return 1;
//空间分配成功
S->top=S->base;//置栈顶指针
S->stacksize=INIT_SIZE;//栈大小
return 0;
}

int Push(SqStack *S, BiTree T) //插入栈顶
{ if( (unsigned)(S->top - S->base) >= S->stacksize){//栈满，追加存储空间
  S->base=(BiTree *)realloc(S->base, (S->stacksize+INCREMENT)*sizeof(BiTree) );
  if(!S->base)//分配失败，返回1
   return 1;
  //分配成功
  S->top = S->base + S->stacksize;//置栈顶指针
  S->stacksize += INCREMENT;//栈大小
}
*S->top++ = T;//接收输入后，S->top指向栈顶元素的下一个位置

return 0;
}