考研二叉树不会有编程的！！ 不过会有题目的！！ 好好学啊！！

二叉树

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