二叉树 递归 非递归 遍历 C语言 可直接运行/************************* 声明区 *************************/#include<stdio.h>#include<stdlib.h>#define OK true#define Nil ' '#define OVERFLOW false#define FALSE false#define ERROR false#define TRUE truetypedef bool Status;typedef char TElemType; #define STACK_INIT_SIZE 10 // 存储空间初始分配量#define STACKINCREMENT 2 // 存储空间分配增量int Length=0;/************************* 结构体类型部分 *************************///n个结点的二叉链表有n + 1个空链域（空的孩子指针域）typedef struct BiTNode{ TElemType data; BiTNode *lchild, *rchild; }BiTNode,*BiTree;typedef BiTree SElemType; //栈中操作的是指向树节点的指针 /********************** 结构类型部分 **********************/typedef struct SqStack{ SElemType *base; SElemType *top; int stacksize; }SqStack; /********************** 构造一个空栈S **********************/Status InitStack(SqStack &S){ if (!(S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof (SElemType)))) exit(OVERFLOW); S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK;}/********************** 返回栈顶元素 **********************/Status GetTop(SqStack S, SElemType &e){ if (S.top > S.base) { e = *(S.top - 1); return OK; } else return ERROR;}/********************** 插入新的栈顶元素 **********************/Status Push(SqStack &S, SElemType e){ if (S.top - S.base >= 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; return OK;}/********************** 删除栈顶元素 **********************/Status Pop(SqStack &S, SElemType &e){ if (S.top == S.base) return ERROR; e = *--S.top; return OK;}/************************* 建立二叉树并输入数值 *************************/void CreateBiTree(BiTree &T){ // 注意此处的 递归函数的终止条件是一棵二叉树完全构建好 ，当二叉树没有构建完成时，递归没有完成 TElemType ch; scanf("%c", &ch); if (ch == Nil) // 空 T = NULL; else { T = (BiTree) malloc(sizeof (BiTNode)); if (!T) exit(OVERFLOW); T->data = ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); }}/************************* 输出元素函数 *************************/Status PrintElement(TElemType e) { printf("%c\t",e); return OK;}/********************** 判断栈是否是空的 **********************/Status StackEmpty(SqStack S){ if (S.top == S.base) return TRUE; else return FALSE;}/********************** 输出栈元素 **********************/void OutList(SqStack S){ S.top=S.base; for(int i=0;i<Length;i++) { printf("%d\t",*(S.top)++); } printf("\n"); }/************************* 递归中序遍历*************************/Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){ if(!T) return ERROR; else { InOrderTraverse(T->lchild,Visit);Visit(T->data);InOrderTraverse(T->rchild,Visit); } return OK;}/************************* 非递归中序遍历一 *************************/Status InOrderTraverse1(BiTree T,Status(*Visit)(TElemType e)){ SqStack S; BiTree p; InitStack(S); Push(S,T); while(!StackEmpty(S)) { while(GetTop(S,p)&&p) Push(S,p->lchild); Pop(S,p); if(!StackEmpty(S)){ Pop(S,p); if(!PrintElement(p->data)) return ERROR; Push(S,p->rchild); } } return OK;}/************************* 非递归中序遍历二 *************************/Status InOrderTraverse2(BiTree T,Status(*Visit)(TElemType e)){ SqStack S; BiTree p; InitStack(S); p = T; while(p||!StackEmpty(S)) { if(p) { Push(S,p); p = p->lchild; } else { Pop(S,p); if(!Visit(p->data)) return ERROR; p = p->rchild; } } return OK;}/************************* 主函数部分 *************************/int main(int args[]){ /**************** 函数声明区 ******************/ void CreateBiTree(BiTree &T); Status PrintElement(TElemType); Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)); /**************** 函数执行区 ******************/ //测试用例 输入ABC##DE#G##F###，其中#用空格代替 BiTree A; CreateBiTree(A); InOrderTraverse(A,PrintElement); printf("\n"); InOrderTraverse1(A,PrintElement); printf("\n"); InOrderTraverse(A,PrintElement); return 0;}
