二叉树的递归、非递归的先序、中序、后序遍历以及层次遍历和求叶子节点数.doc

#include #include #include #define STACK_INT_SIZE 100 /存储空间初始分配量#define STACKINCREMENT 10 /存储空间分配增量#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define OVERFLOW -2typedef char TElemType;typedef int Status;typedef char SElemType;/二叉树的二叉链表存储表示typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; /左右孩子指针BiTNode, *BiTree; /用于存储二叉树结点的栈typedef struct BiTree *base; BiTree *top; int stacksize; /当前已分配的存储空间SqStack;/定义链式队列结点typedef struct QNode BiTree Queuedata; struct QNode * next;QNode,* QueuePtr;/定义链式队列typedef struct QueuePtr front; / QueuePtr rear;LinkQueue;/创建存储二叉树结点的空栈Status InitStack(SqStack &S) S.base = (BiTree *) malloc(sizeof(BiTree); if(!S.base) exit(OVERFLOW); S.top = S.base; S.stacksize = STACK_INT_SIZE; return OK;/存储二叉树结点的栈的取栈顶元素Status GetTop(SqStack &S, BiTree &e) /若栈不空，则用e返回S的栈顶元素 if(S.top = S.base) return ERROR; e = *(S.top-1); return OK;/存储二叉树结点的栈的入栈操作Status Push(SqStack &S, BiTree e) /插入元素e为栈顶元素 if(S.top - S.base = S.stacksize) /若栈满，则追加存储空间 S.base = (BiTree *) realloc(S.base, (S.stacksize + STACKINCREMENT)*sizeof(BiTree); if(!S.base) return ERROR; S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.top = e; S.top+; return OK;/用于存储二叉树结点的栈出栈操作Status Pop(SqStack &S,BiTree &e) /删除S的栈顶元素，并用e返回 if(S.base = S.top) return ERROR; S.top-; e = *S.top; return OK;/判断存储二叉树结点的栈是否为空 Status StackEmpty(SqStack S) / 若栈S为空栈，则返回TRUE，否则返回FALSE if(S.top = S.base) return TRUE; else return FALSE; /先序顺序创建一颗二叉树Status PreOrderCreateBiTree(BiTree &T) /按先序次序输入二叉树中结点的值 /构造二叉链表表示的二叉树T char ch; scanf(%c,&ch); if(ch = 0) T = NULL; else /if(!(T = (BiTree ) malloc(sizeof(BiTree) exit(OVERFLOW);/作用和下一语句的作用相同，注意两者的区别 if(!(T = (BiTNode* ) malloc(sizeof(BiTNode) exit(OVERFLOW); T-data = ch; /生成根结点 PreOrderCreateBiTree(T-lchild); /构造左子树 PreOrderCreateBiTree(T-rchild); /构造右子树 return OK; /CreateBiTree/递归先序遍历二叉树void PreOrder ( BiTree bt ) if ( bt ) printf(%c,bt-data); /先访问根节点 PreOrder ( bt-lchild );/遍历左子树 PreOrder ( bt-rchild ); /遍历右子树 /递归中序遍历二叉树void Inorder ( BiTree bt ) if ( bt ) Inorder ( bt-lchild ); /遍历左子树 printf(%c,bt-data);/访问根节点 Inorder ( bt-rchild );/遍历右子树 /递归后序遍历二叉树void LastOrder ( BiTree bt ) if ( bt ) LastOrder( bt-lchild );/遍历左子树 LastOrder( bt-rchild );/遍历右子树 printf(%c,bt-data);/访问根节点 /非递归先序遍历二叉树 方法一：Status PreOrderTraverse(BiTree T) SqStack s; BiTree P=T; InitStack(s); while ( P!=NULL | !StackEmpty(s) if (P!=NULL) printf(%c,P-data); Push(s,P); /访问完之后将根节点入栈 P=P-lchild; else Pop(s,P); P=P-rchild; return OK;/非递归先序遍历二叉树 方法二：Status PreOrderTraverse2(BiTree T) SqStack s; BiTree P=T; InitStack(s); Push(s,P); /先将根节点入栈 while ( !StackEmpty(s) Pop(s,P); if (P!=NULL) printf(%c,P-data);/访问根节点 Push(s,P-rchild);/ 先进栈，后访问，所以这里先让右子树进栈 Push(s,P-lchild); return OK;/非递归中序遍历二叉树Status InOrderTraverse(BiTree T) /中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit,也就是printf()函数 SqStack S; InitStack(S); BiTree p; p = T; /*/ while(p | !StackEmpty(S) if(p) Push(S,p); p = p-lchild; /根指针进栈，遍历左子树 else /根指针退栈，访问根结点，遍历右子树 Pop(S,p); printf(%c,p-data); p = p-rchild; /while /*和上面的while开始的操作完全等同，可以视为方法二： Push(S,p); while (!StackEmpty(S) while (GetTop(S,p) & p) Push(S,p-lchild); Pop(S,p); if (!StackEmpty(S) Pop(S,p); printf(%c,p-data); Push(S,p-rchild); */ return OK; /InOrderTraverse/*/非递归后序遍历二叉树 ：Status LastOrderTraverse(BiTree T) /后序遍历时，分别从左子树和右子树共两次返回根结点， /只有从右子树返回时才访问根结点，所以增加一个栈标记到达结点的次序。SqStack s,tag;/定义两个栈，一个是存储二叉树结点的栈，一个是存储标志位的栈 /stack2 tag ; BiTree f,m,n,P=T; /m，n是标志位。f是中间变量，用于检测标志位是m还是n的m=(BiTNode*)malloc(sizeof(BiTNode); /注意：此处必须先创建结点，然后再赋值 m-data=1; m-lchild=NULL; m-rchild=NULL; n=(BiTNode*)malloc(sizeof(BiTNode);/注意：此处必须先创建结点，然后再赋值 n-data=2; n-lchild=NULL; n-rchild=NULL; InitStack(s);/此栈用来存放结点 InitStack(tag);/此栈用来存放标志位，从左子树返回根节点时为1，从右子树返回根节点时为2 while (P |!StackEmpty(s) if (P) Push(s,P); Push(tag,m);/第一次入栈操作 P=P-lchild; else Pop(s,P); Pop(tag,f); if (f=m) / 从左子树返回，二次入栈，然后p转右子树 Push(s,P); Push( tag, n);/第二次入栈 P=P-rchild; else / 从右子树返回(二次出栈)，访问根结点，p转上层 printf(%c,P-data); P=NULL; / 必须的，使下一步继续退栈 return OK;/初始化一个带头结点的队列Status InitQueue(LinkQueue &Q) Q.front=(QNode*)malloc(sizeof(QNode); if (!Q.front) exit(OVERFLOW); Q.rear=Q.front; Q.front-next=NULL; return OK;/入队列Status EnQueue(LinkQueue &Q,BiTree e) QueuePtr s=(QueuePtr)malloc(sizeof(QNode); if (!s) exit(OVERFLOW); s-Queuedata=e; s-next=NULL; Q.rear-next=s; Q.rear=s; return OK;/出队int DelQueue(LinkQueue &Q, BiTree &e) char data1; QueuePtr s; s=Q.front-next;/注意：该队列为带头结点，所以刚开始出队列时，应该去front的next e=s-Queuedata;/获取对头记录的数据域，类型为BiTree data1=e-data;/获取BiTree类型的数据域，类型为char Q.front-next=s-next; if(Q.rear=s)/队列中只有一个元素 Q.rear=Q.front; free(s); return TRUE;/队列的判断空操作Status QueueEmpty(LinkQueue Q) /队列带头结点，所以需要判断Q.front-next if (Q.front-next=NULL) return OK; else return ERROR; /按层次遍历Status HierarchyBiTree(BiTree bt) LinkQueue Q; / 保存当前节点的左右孩子的队列 InitQueue(Q); / 初始化队列 BiTree p = bt; / 临时保存树根Root到指针p中 if (bt = NULL) return ERROR; /树为空则返回 EnQueue(Q,p); /先将根节点入队列 while (!QueueEmpty(Q) / 若队列不空，则层序遍历 DelQueue(Q, p); / 出队列 printf(%C,p-data);/ 访问当前节点 if (p-lchild) EnQueue(Q, p-lchild); / 若存在左孩子，左孩子进队列 if (p-rchild) EnQueue(Q, p-rchild); / 若存在右孩子，右孩子进队列 /DelQueue(Q,p); / 释放队列空间return OK;/求叶子节点个数int sum=0;/此处一定要定义为全局变量，因为递归调用退出函数的时候局部变量会销毁int SumLefts(BiTree bt) if (bt!=NULL) if (bt-lchild=NULL & bt-rchild=NULL) /printf(%4c,bt-data); sum+; sum=SumLefts(bt-lchild); sum=SumLefts(bt-rchild); return(sum);void main() /注意创建二叉树时，用先序顺序创建 printf(请输入先序建立二叉树所需要的数据(例如ABD0000)：); BiTree t; PreOrderCreateBiTree(t); /利用先序顺序创建二叉树 printf(先序遍历输出为：); /PreOrder(t);/先序递归遍历 PreOrderTraverse(t);/先序非递归遍历 printf(n); printf(中序