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

《二叉树的递归、非递归的先序、中序、后序遍历以及层次遍历和求叶子节点数》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、#include#include#include#defineSTACK_INT_SIZE100//存储空间初始分配量#defineSTACKINCREMENT10//存储空间分配增量#defineOK1#defineERROR0#defineTRUE1#defineFALSE0#defineOVERFLOW-2typedefcharTElemType;typedefintStatus;typedefcharSElemType;//二叉树的二叉链表存储表示typedefstruct

2、BiTNode{TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;//用于存储二叉树结点的栈typedefstruct{BiTree*base;BiTree*top;intstacksize;//当前已分配的存储空间}SqStack;//定义链式队列结点typedefstructQNode{BiTreeQueuedata;structQNode*next;}QNode,*QueuePtr;//定义链式队列typedefstruct{QueuePtrfro

3、nt;//QueuePtrrear;}LinkQueue;//创建存储二叉树结点的空栈StatusInitStack(SqStack&S){S.base=(BiTree*)malloc(sizeof(BiTree));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INT_SIZE;returnOK;}//存储二叉树结点的栈的取栈顶元素StatusGetTop(SqStack&S,BiTree&e){//若栈不空，则用e返回S的栈顶元素if(S.top==S.base)re

4、turnERROR;e=*(S.top-1);returnOK;}//存储二叉树结点的栈的入栈操作StatusPush(SqStack&S,BiTreee){//插入元素e为栈顶元素if(S.top-S.base>=S.stacksize){//若栈满，则追加存储空间S.base=(BiTree*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTree));if(!S.base)returnERROR;S.top=S.base+S.stacksize;S.stacksize+=S

5、TACKINCREMENT;}*S.top=e;S.top++;returnOK;}//用于存储二叉树结点的栈出栈操作StatusPop(SqStack&S,BiTree&e){//删除S的栈顶元素，并用e返回if(S.base==S.top)returnERROR;S.top--;e=*S.top;returnOK;}//判断存储二叉树结点的栈是否为空StatusStackEmpty(SqStackS){//若栈S为空栈，则返回TRUE，否则返回FALSEif(S.top==S.base)returnTRUE;elsereturnFAL

6、SE;}//先序顺序创建一颗二叉树StatusPreOrderCreateBiTree(BiTree&T){//按先序次序输入二叉树中结点的值//构造二叉链表表示的二叉树Tcharch;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->da

7、ta=ch;//生成根结点PreOrderCreateBiTree(T->lchild);//构造左子树PreOrderCreateBiTree(T->rchild);//构造右子树}returnOK;}//CreateBiTree//递归先序遍历二叉树voidPreOrder(BiTreebt){if(bt){printf("%c",bt->data);//先访问根节点PreOrder(bt->lchild);//遍历左子树PreOrder(bt->rchild);//遍历右子树}}//递归中序遍历二叉树voidInorder(BiTr

8、eebt){if(bt){Inorder(bt->lchild);//遍历左子树printf("%c",bt->data);//访问根节点Inorder(bt->rchild);//遍历右子树