《二叉树的递归建立、递归与非递归遍历,就高、求叶子节点等》由会员分享，可在线阅读，更多相关《二叉树的递归建立、递归与非递归遍历,就高、求叶子节点等（4页珍藏版）》请在金锄头文库上搜索。
1、#include#include#include#define MAX_TREE_SIZE 100#define elemtype char#define STACK_INIT_SIZE 100#define STACK_INCREMENT 10/*二叉树定义*/typedef struct Telemtype data;struct T *lchild,*rchild;Bitree,*Qtree;/*栈的结构*/typedef structQtree *base;Qtree *top;int stacksize;Stack,* qstack;int Init(qstack S)/*构造空栈
2、*/S-base=(Qtree *)malloc(STACK_INIT_SIZE*sizeof(Qtree);if(!S-base)exit(1);S-top=S-base;S-stacksize=STACK_INIT_SIZE;return 1;int Stackempty(Stack S)/*判断栈空 */if(S.top=S.base)return 1;elsereturn 0;int Push(qstack S,Qtree e)/*插入元素 */if(S-top-S-base=S-stacksize)/*栈满*/return 0;else *S-top+=e;return 0;int
3、GetTop(Stack S,Qtree *e)/*得到栈顶元素*/if(S.top=S.base)return 0;*e=*(S.top-1);return 1;int Pop(qstack S,Qtree *e)/*弹出栈顶元素*/if(S-top=S-base)return 0;else*e=*-S-top;return 1;Qtree CreateTree()/*递归先序建树*/Qtree T;char ch;printf(please inputn);scanf(%c,&ch);fflush(stdin);/*清空缓存*/if(ch=#)return NULL;T=(Qtree)ma
4、lloc(sizeof(Bitree);T-data=ch;T-lchild=CreateTree();T-rchild=CreateTree();return T;int preOrderTraverse(Qtree T)/*先序递归遍历*/char e;if(!T)return 0;printf(%c ,T-data);preOrderTraverse(T-lchild);preOrderTraverse(T-rchild);return 1;int High(Qtree T)/*求树高 */if(!T)return 0;return(Max(High(T-lchild),High(T-r
5、child)+1);int Node(Qtree T)/*求所有节点*/if(!T)return 0;return(Leeaf(T-lchild)+Leeaf(T-rchild)+1);int Leeaf(Qtree T)/*求叶子节点*/if(T-lchild=NULL &T-rchild=NULL)return 1;return(Leeaf(T-lchild)+Leeaf(T-rchild);int Max(int a,int b)if(ab)return a;elsereturn b;void NRinorder(Qtree T)/*非递归中序遍历*/Qtree p;Stack S;In
6、it(&S); Push(&S,T);/* printf(#); */while(!Stackempty(S)/* printf(#); */while(GetTop(S,&p)&p)/* printf(%c# ,p-data); */Push(&S,p-lchild);Pop(&S,&p);if(!Stackempty(S)Pop(&S,&p);printf(%c ,p-data);Push(&S,p-rchild); int Visit(elemtype e)printf(%c ,e);void main()Qtree T;T=CreateTree();preOrderTraverse(T);printf(nthis trees high is %dn,High(T);NRinorder(T);printf(nthis thee has %d leeafn,Leeaf(T);getch();
