二叉树的建立及几种简单的遍历方法.doc

#include stdio.h#include stdlib.h#define STACK_INIT_SIZE 100 /栈存储空间初始分配量#define STACKINCREMENT 10 /存储空间分配增量/-二叉树的存储结构表示-/typedef struct BiTNodeint data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;/-顺序栈的存储结构表示-/typedef structBiTree *top;BiTree *base;int stacksize;SqStack; /*/构造一个空栈sSqStack *InitStack();/创建一颗二叉树 BiTree CreatBiTree();/判断栈空 int StackEmpty(SqStack *S);/插入元素e为新的栈顶元素 void Push(SqStack *S,BiTree p);/若栈不为空，则删除s栈顶的元素e，将e插入到链表L中 void Pop(SqStack *S,BiTree *q);/非递归先序遍历二叉树 void PreOrderTraverse(BiTree L);/非递归中序遍历二叉树 void InOrderTraverse(BiTree L);/非递归后序遍历二叉树 void PostOrderTraverse(BiTree L);/递归后序遍历二叉树 void PostOrder(BiTree bt);/递归中序遍历二叉树 void InOrder(BiTree bt);/递归先序遍历二叉树 void PreOrder(BiTree bt);/*int main()BiTree bt;int n,k;printf(Creat Tree and the end with . n);bt=CreatBiTree(); /创建二叉树doprintf(1.PreOrderTraverse 2.InOrderTraverse 3.PostOrderTraverse 4.PostOrder 5.InOrder 6.PreOrden);printf(please input a num to n:);scanf(%d,&n);switch(n)case 1:PreOrderTraverse(bt);printf(n);break; /先序遍历非递归算法case 2:InOrderTraverse(bt);printf(n);break; /中序非递归遍历算法case 3:PostOrderTraverse(bt);printf(n); break; /后序非递归遍历算法case 4:PostOrder(bt);printf(n);break; /后序递归遍历算法case 5: InOrder(bt);printf(n);break; /中序递归遍历算法case 6: PreOrder(bt);printf(n);break; /先序递归遍历算法printf(if you want to continue,please input a num0 to k:);scanf(%d,&k);while(k0);return 0;SqStack *InitStack() /构造一个空栈SSqStack *S;S=(SqStack *)malloc(sizeof(SqStack);S-base=(BiTree *)malloc(STACK_INIT_SIZE*sizeof (BiTree);S-top=S-base;S-stacksize =STACK_INIT_SIZE;return S;BiTree CreatBiTree() /先序方式递归方式建立一个二叉树char k;BiTree T;k=getchar();if(k=.)T=NULL;elseT=(BiTNode *)malloc(sizeof(BiTNode);T-data=k;T-lchild=CreatBiTree();T-rchild=CreatBiTree();return T; void Push(SqStack *S,BiTree p) /插入二叉树p的结点地址为栈顶的新元素if(S-top-S-base=S-stacksize)S-base=(BiTree *)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(BiTree);S-top=S-base+S-stacksize;S-stacksize+=STACKINCREMENT;*S-top=p;S-top+;void Pop(SqStack *S,BiTree *q) /二叉树q的结点地址出栈返回，做为新二叉树的当前地址if(S-base=S-top)exit(0);S-top-;*q=*S-top;int StackEmpty(SqStack *S) / 若栈S为空栈，则返回1，否则返回0 if(S-top = S-base) return 1; else return 0; void PreOrderTraverse(BiTree L) /非先序遍历二叉树BiTree T;SqStack *S;S=InitStack();T=L;while(!StackEmpty(S)|T!=NULL)if(T!=NULL)printf(%c,T-data);Push(S,T); T=T-lchild; /根指针进栈，遍历左子树else /根指针退栈，访问根结点，遍历右子树Pop(S,&T);T=T-rchild;void InOrderTraverse(BiTree L) /非先序遍历二叉树BiTree T;SqStack *S;S=InitStack();T=L;while(!StackEmpty(S)|T!=NULL)if(T!=NULL)Push(S,T); T=T-lchild; /根指针进栈，遍历左子树else /根指针退栈，访问根结点，遍历右子树Pop(S,&T);printf(%c,T-data);T=T-rchild;void PostOrderTraverse(BiTree L)/非后序遍历二叉树BiTree T;SqStack *S;S=InitStack();T=L;while(!StackEmpty(S)|T!=NULL)if(T!=NULL)Push(S,T); T=T-lchild; /根指针进栈，遍历左子树else /根指针退栈，访问根结点，遍历右子树Pop(S,&T);printf(%c,T-data);T=T-rchild;void PostOrder(BiTree bt)if(bt=NULL)return;PostOrder(bt-lchild);PostOrder(bt-rchild);printf(%c,bt-data);void InOrder(BiTree bt)if(bt=NULL)return;InOr