二叉树的二叉链表存储表示

非递归的部分思想是参考这个链接的：http://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html

非递归后序遍历暂时还没有调试成功。

common.h

#ifndef_COMMON_H_
#define_COMMON_H_

#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE  -1
#define OVERFLOW    -2

typedef int Status;  

//Status Equal(int a, int b);

#endif

SqStack.h

//关于栈的文件(包括SqStack.h和SqStack.c)基本是从之前的学习文件中复制过来的,并做了一些改动。
//参考博文“顺序栈的表示和实现”，链接：http://blog.csdn.net/yahstudio/article/details/23599731

#ifndef_SQSTACK_H_
#define_SQSTACK_H_

#include "BiTree.h"

#defineSTACK_INIT_SIZE1000
#defineSTACKINCREMENT1000

//typedef intSElemType;//这是之前的
typedef BiTNodeSElemType;

typedef struct
{
SElemType *base;//在栈构造之前和销毁之后，base的值为NULL
SElemType *top;//栈顶指针
int stacksize;//当前已分配的存储空间，以元素为单位
}SqStack;

StatusInitStack(SqStack *S);
//构造一个空栈S

Status StackScanf(SqStack *S);
//向指定的stack输入数据

Status StackDisp(SqStack *S);
//显示指定的stack

int StackLength(SqStack *S);
//返回指定stack的元素个数，即栈的长度

Status GetTop(SqStack *S,SElemType *e);
//若栈不空，则将S的栈顶元素传递给*e，并返回OK;否则返回ERROR

Status GetTop1(SqStack *S,SElemType **e);
//这是为了适应BiTree中的有关函数而在GetTop的基础上修改的。

Status Push(SqStack *S,SElemType e);
//插入数据e为新的栈顶元素

Status Pop(SqStack *S,SElemType *e);
//若栈不空，则删除指定栈的栈顶元素，并用e返回其值，并返回OK；否则返回ERROR。

Status Pop1(SqStack *S,SElemType **e);
//这是为了适应BiTree中的有关函数而在Pop的基础上修改的。

Status DestroyStack(SqStack *S);
//销毁指定栈

Status ClearStack(SqStack *S);
//清空指定栈

Status StackEmpty(SqStack *S);
//判断指定栈是否为空，若为空栈，则返回TRUE，否则返回FALSE.

#endif

BiTree.h

#ifndef_BITREE_H_
#define _BITREE_H_

typedefcharTElemType;
typedef struct BiTNode
{
TElemTypedata;
struct  BiTNode  *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;

Status PrintElement(TElemType e);

//创建二叉树
Status CreateBiTree(BiTree *T);

//先序遍历二叉树(递归实现)，对每个数据元素调用函数Visit
Status PreOrderTraverse(BiTree T, Status (* Visit)(TElemType e));

//中序遍历二叉树(递归实现)，对每个数据元素调用函数Visit
Status InOrderTraverse(BiTree T, Status (* Visit)(TElemType e));

//后序遍历二叉树(递归实现)，对每个数据元素调用函数Visit
Status PostOrderTraverse(BiTree T, Status (* Visit)(TElemType e));

//(课本上的算法6.2，不可用)中序遍历二叉树(非递归实现)，对每个数据元素调用函数Visit
Status InOrder_book1(BiTree T, Status (* Visit)(TElemType e));

//(课本上的算法6.3，可用)中序遍历二叉树(非递归实现)，对每个数据元素调用函数Visit
Status InOrder_book2(BiTree T, Status (* Visit)(TElemType e));

//中序遍历二叉树(非递归实现)，对每个数据元素调用函数Visit
Status InOrder(BiTree T, Status (* Visit)(TElemType e));

//先序遍历二叉树(非递归实现)，对每个数据元素调用函数Visit
Status PreOrder(BiTree T, Status (* Visit)(TElemType e));

#endif

SqStack.c

//关于栈的文件(包括SqStack.h和SqStack.c)基本是从之前的学习文件中复制过来的,并做了一些改动。
//参考博文“顺序栈的表示和实现”，链接：http://blog.csdn.net/yahstudio/article/details/23599731

#include "stdio.h"
#include "stdlib.h"
#include "common.h"
#include "SqStack.h"

/*
输入参数：*S待处理的栈地址
返回参数：OVERFLOW存储分配失败
   OK成功
函数功能：初始化栈，构造一个空栈。
*/
Status InitStack(SqStack *S)
{
S->base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S->base)
exit(OVERFLOW);//存储分配失败

S->top = S->base;//使栈顶指针等于栈底指针
S->stacksize = STACK_INIT_SIZE;//初始化栈当前可用的最大容量
return OK;
}

/*
输入参数：*S待处理的栈地址
返回参数：OK操作成功
   OVERFLOWstack满
   还可以根据实际情况定义相应的返回值
函数功能：向指定的stack输入数据，约定若输入0则结束，并将0存储stack。
注意：在stack的存储空间够用的情况下，调用该函数得到的栈顶元素都为0，若想栈顶元素不为0可以调用Push()函数。
*/
/*
Status StackScanf(SqStack *S)
{
SElemType *cap_max;
cap_max = S->base + S->stacksize - 1;//减1的原因是：留一个存储单元给栈顶指针，即当stack的存储单元用完时，使栈顶指针指向存储空间的最后一个存储单元。
scanf("%d",S->top);
S->top++;
while(*(S->top-1))
{
scanf("%d",S->top);
S->top++;
if(S->top >= cap_max)
{
printf("The stack is full.");//实际应用时当然还可以在这里继续为原stack扩充容量。
return OVERFLOW;
}
}
return OK;
}
*/

/*
输入参数：*S待显示的栈地址
返回参数：OK操作成功
   还可以根据实际情况定义相应的返回值
函数功能：显示指定的stack
注意：程序中调用的StackDisp()函数并未按照后进先出这一规定显示stack的，当然完全可以将其改为按后进先出的规定来显示stack的，不过我估计在实际应用中StackDisp()函数未必排得上用场。
*/
Status StackDisp(SqStack *S)
{
SElemType *bottom = S->base;
printf("\n*************** output start ***************\n");
while(bottom<S->top)
{
printf("%d  ",*bottom);
bottom++;
}
printf("\n*************** output end ***************\n");
return OK;
}

/*
输入参数：*S待处理的栈地址
返回参数：*S所指向的stack的长度，即该stack中的元素个数
函数功能：返回指定stack的元素个数，即栈的长度
*/
int StackLength(SqStack *S)
{
//可根据需要在这里添加判断S是否满足一些条件，如判断*S指向的stack是否存在等，因为栈是否存在和栈是否空有时还是有区别的。
//if(!(S->top||S->top))//判断栈是否存在，这个当然要在销毁栈时将栈顶指针和栈底指针都清为0才能在此有所判断。
//return -1;
return(S->top - S->base);
}

/*
输入参数：*S待处理的栈地址
   *e用于存储栈顶元素
返回参数：ERROR该栈为空
   OK操作成功
函数功能：若栈不空，则将S的栈顶元素传递给*e，并返回OK;否则返回ERROR.
*/
Status GetTop(SqStack *S,SElemType *e)
{
if(!StackLength(S))
return ERROR;
else
{
*e = *(S->top - 1);
}
return OK;
}

/*
说明：这个函数是在GetTop的基础上改的。
它们的区别仅仅是第二个形参，GetTop的第二个形参是一级指针，但这只能改变实参为变量的内容，
当实参为一级指针时，应当定义二级指针形式的形参来改变其内容。
时间有限，这里只是简要的描述一下额外写GetTop1的原因，具体原因可以参见博文“关于变量、1/2级指针等形式的形参传递”。
*/
Status GetTop1(SqStack *S,SElemType **e)
{
if(!StackLength(S))
return ERROR;
else
{
*e = (S->top - 1);
}
return OK;
}

/*
输入参数：*S待处理的栈地址
   e待插入的数据
返回参数：OVERFLOWstack满
   OK操作成功
函数功能：插入数据e为新的栈顶元素
*/
Status Push(SqStack *S,SElemType e)
{
if(StackLength(S) >= S->stacksize)
{
S->base = (SElemType *)realloc(S->base,(S->stacksize + STACKINCREMENT)*sizeof(SElemType));
if(!S->base)
exit(OVERFLOW);
S->top = S->base + S->stacksize;
S->stacksize += STACKINCREMENT;
}
*S->top = e;
S->top++;
return OK;
}

/*
输入参数：*S待处理的栈地址
   *e待返回的栈顶元素
返回参数：ERROR操作失败
   OK操作成功
函数功能：若栈不空，则删除指定栈的栈顶元素，并用e返回其值，并返回OK；否则返回ERROR。
*/
Status Pop(SqStack *S,SElemType *e)
{
if(StackLength(S) <= 0)
return ERROR;
*e = * --S->top;
return OK;
}

/*
定义Pop1的原因 与 定义GetTop1类似。（二级指针形式的形参）
*/
Status Pop1(SqStack *S,SElemType **e)
{
if(StackLength(S) <= 0)
return ERROR;
*e = --S->top;
return OK;
}

/*
输入参数：*S待销毁的栈地址
返回参数：OK操作成功
   还可根据需要加入别的返回值
函数功能：销毁指定栈
*/
Status DestroyStack(SqStack *S)
{
free(S->base);
S->base = NULL;
S->top = NULL;
S->stacksize = 0;
return OK;
}

/*
输入参数：待清空的栈地址
返回参数：OK操作成功
函数功能：清空指定栈
*/
Status ClearStack(SqStack *S)
{
S->top = S->base;
return OK;
}

/*
输入参数：*S待处理的栈地址
返回参数：FALSE指定的栈非空
   OK指定的栈为空
函数功能：判断指定栈是否为空，若为空栈，则返回TRUE，否则返回FALSE.
*/
Status StackEmpty(SqStack *S)
{
//if(!(S->top||S->top))//判断栈是否存在，这个当然要在销毁栈时将栈顶指针和栈底指针都清为0才能在此有所判断。
//return -1;
if(S->top - S->base)
{return FALSE;}
return TRUE;
}

BiTree.c

#include "common.h"
#include "BiTree.h"
#include "SqStack.h"
#include "stdio.h"
#include "stdlib.h"

Status PrintElement(TElemType e)
{
printf("%c ",e);
return OK;
}

/*
输入参数：*T待创建的二叉树
函数功能：创建二叉树(递归实现)
说明：1. 若在main()中定义int类型变量val，则可以定义形参为一级指针形式的函数(如fun(int *dat))，通过调用函数fun(&val)来改变变量val的值。
   2. 若在main()中定义int类型的一级指针变量*val，则可以在main()中初始化该指针，使其指向确定的int类型的变量或内存，例如"int a, *val = &a;"或者"int *val = (int *)malloc(sizeof(int));"都是可以的，在这之后便可以在函数fun(int *dat)中来操作(赋值)该指针变量了，调用形式为fun(val)。
      (此时没有必要在fun中调用malloc函数使指针变量val指向新的内存，因为这根本就办不到，此时在fun中的malloc函数只会改变形参dat中的内容，而不会改变val中的内容。)
   3. 若在main()中定义int类型的一级指针变量*val，但不想在main()中初始化该指针，而是想在其他的函数中初始化该指针，则应当定义形参为二级指针形式的函数(如fun(int **dat))，通过在fun函数中来初始化该指针变量(在fun中通过malloc函数初始化该指针变量)，调用形式为fun(&val)，在初始化完之后便可以操作(赋值)该变量了。
在此说明上述3点，是因为刚开始学习二叉树的二叉链表时遇到问题不能够解决，后来才得知应当定义二级指针形式的形参CreateBiTree(BiTree *T)。
关于此可参考博文“关于变量、1/2级指针等形式的形参传递”。
*/
Status CreateBiTree(BiTree *T)
{
    char ch;
    scanf("%c",&ch);
    if(ch == ' ')
        *T = NULL;
    else
    {
        if(!(*T = (BiTree)malloc(sizeof(BiTNode))))
            exit(OVERFLOW);
        (*T)->data = ch;
        CreateBiTree(&(*T)->lchild);    //构造左子树
        CreateBiTree(&(*T)->rchild);    //构造右子树
    }
    return OK;
}

/*
输入参数：T待遍历的二叉树
   Visit对数据元素操作的应用函数
函数功能：先序遍历二叉树(递归实现)，对每个数据元素调用函数Visit
*/
Status PreOrderTraverse(BiTree T, Status (* Visit)(TElemType e))
{
if(T)
{
if(Visit(T->data))
if(PreOrderTraverse(T->lchild, Visit))
if(PreOrderTraverse(T->rchild, Visit))
return OK;
return ERROR;
}
else
return OK;
}

/*
函数功能：该函数功能类似PreOrderTraverse()，只不过这里定义二级指针BiTree，本质上并没多大区别。
*/
Status PreOrderTraverse_(BiTree *T, Status (* Visit)(TElemType e))
{
if(*T)
{
if(Visit((*T)->data))
if(PreOrderTraverse_(&(*T)->lchild, Visit))
if(PreOrderTraverse_(&(*T)->rchild, Visit))
return OK;
return ERROR;
}
else
return OK;
}

/*
函数功能：中序遍历二叉树(递归实现)，对每个数据元素调用函数Visit
*/
Status InOrderTraverse(BiTree T, Status (* Visit)(TElemType e))
{
if(T)
{
if(InOrderTraverse(T->lchild, Visit))
if(Visit(T->data))
if(InOrderTraverse(T->rchild, Visit))
return OK;
return ERROR;
}
else
{
return OK;
}
}

/*
函数功能：后序遍历二叉树(递归实现)，对每个数据元素调用函数Visit
*/
Status PostOrderTraverse(BiTree T, Status (* Visit)(TElemType e))
{
if(T)
{
if(PostOrderTraverse(T->lchild, Visit))
if(PostOrderTraverse(T->rchild, Visit))
if(Visit(T->data))
return OK;
return ERROR;
}
else
return OK;
}

/*
函数功能：中序遍历二叉树(非递归实现)，对每个数据元素调用函数Visit
说明：不要用这个函数。
这是书本上的算法6.2，实现起来很不方便，或许根本就实现不了，或许它在C++中可以实现，毕竟C++支持的某些语法在C中是不支持的，如引用。
*/
Status InOrder_book1(BiTree T, Status (* Visit)(TElemType e))
{
SqStack s;
BiTree p = NULL;//若不在这里给p赋NULL值,则编译时会有警告
InitStack(&s);
Push(&s, *T);
while(!StackEmpty(&s))
{
while(GetTop(&s,p) && p)//p是在InOrder函数内定义的局部变量，应当在InOrder函数内改变其内容，但如果想要在InOrder函数内调用别的函数改变其内容(即到InOrder函数外面改变其内容)，则应当定义外部函数的形参为二级指针，如这里GetTop函数的第二个形参应当定义为二级指针。（这一点在博文中已经说过了。）
Push(&s, *p->lchild);//向左走到尽头
//另外当p->lchild=0时，那么*p->lchild根本就不能够被调用，所以这种操作是不行的。
Pop(&s,p);//这个出栈，我估计作者的本意是让最后一个空的左孩子出栈。
if(!StackEmpty(&s))
{
Pop(&s,p);//同GetTop，若想要在外部函数Pop中改变p的内容，则应当定义Pop的第二个形参为二级指针。
if(!Visit(p->data))
return ERROR;
Push(&s, *p->rchild);
}
}
return OK;
}

/*
函数功能：中序遍历二叉树(非递归实现)，对每个数据元素调用函数Visit
说明：这是书本上的算法6.3，这与我自己编写InOrder较类似。
*/
Status InOrder_book2(BiTree T, Status (* Visit)(TElemType e))
{
SqStack s;
BiTree p = T;
InitStack(&s);
while(p || !StackEmpty(&s))
{
if(p)
{
Push(&s, *p);
p = p->lchild;//根指针进栈，遍历左子树
}
else
{
Pop1(&s, &p);
if(!Visit(p->data))
return ERROR;
p = p->rchild;
}
}
return OK;
}

/*
函数功能：中序遍历二叉树(非递归实现)，对每个数据元素调用函数Visit
*/
Status InOrder(BiTree T, Status (* Visit)(TElemType e))
{
SqStack s;
BiTree p = T;
InitStack(&s);
while(p!=NULL || !StackEmpty(&s))//若当前结点p不空 或者 栈s不空，则执行循环体
{
while(p!=NULL)//若当前结点p不空
{
Push(&s, *p);//当前结点p进栈
p = p->lchild;//将p的左孩子置为当前结点p
}
if(!StackEmpty(&s))//若栈s不空
{
//GetTop1(&s, &p);//这里没必要在调用GetTop来获得栈顶元素了，因为下面的Pop1就可以得到栈顶元素了。
Pop1(&s, &p);//进行出栈操作，获得栈顶元素并将其置为当前结点p
Visit(p->data);//访问当前结点的data。
p = p->rchild;//将p的右孩子置为当前结点p
}
}
return OK;
}

/*
函数功能：先序遍历二叉树(非递归实现)，对每个数据元素调用函数Visit
*/
Status PreOrder(BiTree T, Status (* Visit)(TElemType e))
{
SqStack s;
BiTree p = T;
InitStack(&s);
while(p!=NULL || !StackEmpty(&s))
{
while(p!=NULL)//若当前结点p不空
{
Visit(p->data);
Push(&s, *p);//当前结点p进栈
p = p->lchild;//将p的左孩子置为当前结点p
}
if(!StackEmpty(&s))//若栈s不空
{
//GetTop1(&s, &p);//这里没必要在调用GetTop来获得栈顶元素了，因为下面的Pop1就可以得到栈顶元素了。
Pop1(&s, &p);//进行出栈操作，获得栈顶元素并将其置为当前结点p
//Visit(p->data);//访问当前结点的data。
p = p->rchild;//将p的右孩子置为当前结点p
}
}
return OK;
}

/*
函数功能：后序遍历二叉树(非递归实现)，对每个数据元素调用函数Visit
*/
Status PostOrder(BiTree T, Status (* Visit)(TElemType e))
{
SqStack s;
BiTree cur;
BiTree tmp;
BiTree p = T;
BiTree pre = NULL;
InitStack(&s);
Push(&s,*p);
while(!StackEmpty(&s))
{
GetTop1(&s,&cur);
//printf("%d\n",cur->lchild);
//printf("%d\n",cur->rchild);
//printf("%d\n",pre);
if(cur->lchild==NULL && cur->rchild==NULL)
{
printf("左右孩子为空");
}
if(((pre!=NULL) && ((pre==cur->lchild) || (pre==cur->rchild))))
{
printf("之前已经访问过了");
}
if((cur->lchild==NULL && cur->rchild==NULL) || (pre!=NULL && (pre==cur->lchild || pre==cur->rchild)))
{
Visit(cur->data);
Pop1(&s, &tmp);
pre = cur;

}
else
{
if(cur->rchild != NULL)
Push(&s, *cur->rchild);
if(cur->lchild != NULL)
Push(&s, *cur->lchild);
}
}
return OK;
}

main.c

//“非递归后序遍历”没有成功
#include "common.h"
#include "BiTree.h"
#include "SqStack.h"
#include "stdio.h"

int main()
{
BiTNode *PtrTree;
CreateBiTree(&PtrTree);

printf("\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
PreOrderTraverse(PtrTree, PrintElement);
printf("\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
InOrderTraverse(PtrTree, PrintElement);
printf("\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
PostOrderTraverse(PtrTree, PrintElement);
printf("\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
InOrder(PtrTree, PrintElement);
printf("\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
InOrder_book2(PtrTree, PrintElement);
printf("\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
PreOrder(PtrTree, PrintElement);

printf("\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
//PostOrder(PtrTree, PrintElement);//这个不行
return OK;
}