二叉树的建立、遍历、各种算法.doc

基于二叉树的二叉链表存储结构实现以下操作:1、 用先序遍历创建二叉树2、 对二叉树进行非递归遍历（先序、中序、后序）3、 求二叉树所有结点和叶子结点个数4、 求二叉树的深度5、 #includestdio.h#includemalloc.h#includemath.h#includestdlib.h#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0/#define OVERFLOW #define NULL 0typedef int Status;typedef char TElemType;typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiTNode, *BiTree;typedef BiTree SElemType;/tepedef BiNode SElemType;/#define MAX_TREE_SIZE 100/typedef TElemtype SqBiTreeMAX_TREE_SIZE ;/SqBiTree bt;typedef structSElemType *base;SElemType *top;int stacksize;SqStack;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10Status 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;Status GetTop(SqStack S,SElemType &e)if(S.top=S.base) return ERROR;e=*(S.top-1);return OK;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;Status StackEmpty(SqStack S)if(S.top=S.base)return TRUE;else return FALSE;Status CreateBiTree(BiTree &T)/按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，/构造二叉链表表示的二叉树T。char ch;scanf(%c,&ch);if(ch=)T=NULL;elseif(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data=ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);return OK;/CreateBiTreeStatus PreoderTraverse(BiTree T)/二叉树先序遍历非递归算法SqStack S;BiTree p;InitStack(S); p=T;while(p|!StackEmpty(S)if(p)printf(%ct,p-data);p=p-lchild;Push(S,p-rchild);elsePop(S,p);return OK;/ PostoderTraverseStatus InoderTraverse(BiTree T)/二叉树中序遍历非递归算法SqStack S;BiTree p;InitStack(S); p=T;while(p|!StackEmpty(S)if(p)Push(S,p);p=p-lchild;elsePop(S,p);printf(%ct,p-data);p=p-rchild;return OK;/InoderTraverse/Algorithm:先沿着左指针走到二叉树中最左下的结点，将沿途经过的根节点指针进/栈，若右子树为空，则弹栈并访问根节点，否则，跳到右子树上。/Status PostoderTraverse(BiTree T)/ 二叉树的后序遍历非递归算法 SqStack S; BiTree p,q; char flag;/标记访问过的节点 InitStack(S); p=T; q=(BiTree)malloc(sizeof(BiTNode); while (p|!StackEmpty(S) if(p!=q) while(p) /当子树p不为空时 进栈 Push(S,p); if(p-lchild)p=p-lchild; /不为空 后移指向左子树 else p=p-rchild; /为空指向 右子树 if (StackEmpty(S)break; GetTop(S,q); if(q-rchild=p) /判断是 遍历过 右子树 如遍历过右子树 说明该遍历根子树 p=(BiTree)malloc(sizeof(BiTNode); Pop(S,p); printf(%c,p-data); p=q; flag = p-data; /记录 遍历过的子树 else p=q-rchild; if (flag = p-data)/如果根节点的右子树刚刚访问完成，那么记录根节点。 p=(BiTree)malloc(sizeof(BiTNode); Pop(S,p); printf(%c,p-data); p=q; flag = p-data; return OK;int size(BiTree T)if(!T)return 0;else return 1+size(T-lchild)+size(T-rchild);/计算二叉树结点数目int num=0;void Leaf(BiTree T)if(T)if(T-lchild=NULL&T-rchild=NULL)num+;Leaf(T-lchild);Leaf(T-rchild);/计算二叉树中的叶子数目int Depth(BiTree T)int h,lh,rh;if(T=NULL)h=0;elselh=Depth(T-lchild);rh=Depth(T-rchild);if(lhrh)h=lh+1;else h=rh+1;return h;/计算二叉树的深度void main()BiTree T;int xz=1;int sd;while(xz)printf(建立二叉树并求指定结点路径 n);printf(= n);printf(1.建立二叉树的存储结构 n); printf(2.二叉树的基本操作 n);printf(0.退出系统 n);printf(= n);printf(请选择：(0-2) n);scanf(%d,&xz);getchar();switch(xz)/输入：ABCDEGF 输出：CBEGDFAcase 1:printf(输入二叉树的先序序列结点值： n);CreateBiTree(T);printf(二叉树的链式存储结构建立完成！ n);printf(n);break; case 2:printf(该二叉树的先序遍历序列是： n);PreoderTraverse(T);printf(n); printf(该二叉树的中序遍历序列是： n);InoderTraverse(T);printf(n);printf(该二