二叉樹的一些操作

1、#include #include #include #define OVERFLOW 0#define OK 1#define NULL 0#define Max 100typedef int Status ;typedef char TElemType;typedef struct BiTNode / 結(jié)點(diǎn)結(jié)構(gòu)TElemType data;struct BiTNode *lchild, *rchild;/ 左右孩子指針 BiTNode, *BiTree;Status CreateBiTree (BiTree &T)char ch; scanf(%c,&ch) ;if(ch=#)T=NULL

2、;elseif(!(T=(BiTNode *)malloc(sizeof(BiTNode)exit(OVERFLOW);/生成根結(jié)點(diǎn)/構(gòu)造左子樹/生成根結(jié)點(diǎn)/構(gòu)造左子樹/構(gòu)造右子樹CreateBiTree( T-lchild);CreateBiTree( T-rchild);return OK; / CreateBiTreevoid Preorder (BiTree T) / 先序遍歷二叉樹if (T) printf(%c,T-data); / 訪問結(jié)點(diǎn)Preorder(T-lchild); / 遍歷左子樹Preorder(T-rchild);/ 遍歷右子樹typedef structBiTr

3、ee stackMax;int top; SqStack;void Initstack(SqStack *s) / s=(SqStack *)malloc(Max*sizeof(elemtype); s-top=-1;int EmptyStack(SqStack s)if (s.top=-1) return 1;else return 0;void push(SqStack *s,BiTree e)(*s).top+;(*s).stack(*s).top=e;BiTree pop(SqStack *s)BiTree x;x=s-stacks-top;s-top-;return x;Status

4、 InorderTraverse(BiTree T)BiTree p;SqStack S;Initstack(&S);p=T;while(p|!EmptyStack(S)while (p)push(&S,p);p=p-lchild;if(!EmptyStack(S)p=pop(&S);printf(%c,p-data);p=p-rchild;return OK;void Postreorder (BiTree T) / 后序遍歷二叉樹if (T) Postreorder(T-lchild);/ 遍歷左子樹Postreorder(T-rchild);/ 遍歷右子樹printf(%c,T-data

5、); / 訪問結(jié)點(diǎn)void CountLeaf (BiTree T, int& count)if ( T ) if (!T-lchild)& (!T-rchild)count+; / 對葉子結(jié)點(diǎn)計(jì)數(shù)CountLeaf( T-lchild, count);CountLeaf( T-rchild, count); / if / CountLeafint Depth (BiTree T ) / 返回二叉樹的深度int depthval,depthLeft,depthRight;if ( !T )depthval = 0;elsedepthLeft = Depth( T-lchild );depthR

6、ight= Depth( T-rchild );depthval = 1 + (depthLeft depthRight ?depthLeft : depthRight); return depthval;int main()int count=0;BiTree q;printf(”請輸入樹，若無孩子結(jié)點(diǎn)用#代替:n);CreateBiTree(q);printf(先序遍歷結(jié)果為：n);Preorder(q);printf(n);printf(沖序遍歷結(jié)果為:n”);InorderTraverse(q);printf(n);printf(”后序遍歷結(jié)果為：n);Postreorder(q);printf(n);CountLeaf(q,count);printf( 葉子節(jié)點(diǎn)個(gè)