二叉樹的各種算法

1、#include#include #define MAX 50 #define MAS 20 #define CHAR 1 #if CHARtypedef char TElemType;TElemType Nil= ;#define form %c#elsetypedef int TElemType;TElemType Nil=0;#define form %d #endif typedef struct node TElemType data;struct node *left;struct node *right; struct node *parent; BiTNode,*BiTree;

2、BiTNode *InitBiTree(BiTNode *bt)bt=NULL;return bt;BiTNode *CreateBiTree(BiTNode *bt)TElemType ch;scanf(form,&ch);if(ch=Nil) bt=NULL;elsebt=(BiTNode *)malloc(sizeof(BiTNode); if(!bt) exit(0);bt-data=ch; bt-parent=NULL; bt-left=CreateBiTree(bt-left); if(bt-left) bt-left-parent=bt; bt-right=CreateBiTre

3、e(bt-right); if(bt-right) bt-right-parent=bt;return bt;void PrintTree(BiTNode *bt,int i) if(bt!=NULL)PrintTree(bt-right,i+5);#if CHAR if(bt-data!=Nil) printf(%*cn,i,bt-data);#elseif(bt-data!=Nil) printf(%*dn,i,bt-data);#endifPrintTree(bt-left,i+5);i=i-5;void Prorderl(BiTNode *bt,void(*visit)(TElemTy

4、pe)/*先序遍歷 */ if(bt!=NULL)visit(bt-data);Prorderl(bt-left,visit); Prorderl(bt-right,visit);void Prorder2(BiTNode *bt,void(*visit)(TElemType)/*中 序遍歷 */ BiTNode *p,*stackMAS;int top;top=0; p=bt;while(top!=0|p!=NULL)while(p!=NULL)stacktop=p; top+;p=p-left;if(top!=0)p=stacktop-l;top-;visit(p-data); p=p-r

5、ight;void Prorder3(BiTNode *bt,void(*visit)(TElemType)/*后序遍歷 */ BiTNode *p,*stackMAS;int top;top=0;stacktop=bt; top+;while(top0)p=stacktop-1; top-;while(p!=NULL)visit(p-data);stacktop=p-right;top+;p=p-left;void visit(TElemType e)printf(form ,e);int SumLefts(BiTNode *bt,int sum)if (bt!=NULL)if (bt-le

6、ft=NULL & bt-right=NULL) printf(%4c,bt-data); sum+;sum=SumLefts(bt-left,sum); sum=SumLefts(bt-right,sum);return(sum);int SumTree(BiTNode *bt) static int sum=0;if(bt!=NULL) printf(%4c,bt-data);sum+; sum=SumTree(bt-left); sum=SumTree(bt-right); return(sum);BiTNode *Findchar(BiTNode *bt,char ch)/*二叉樹查找

7、結(jié)點(diǎn)*/BiTNode *p;/*利用函數(shù)名返回結(jié)果*/if(bt!=NULL)if(bt-data=ch) p=bt;p=Findchar(bt-left,ch);p=Findchar(bt-right,ch);if(p!=NULL) return(p);else return(NULL);void main() int j,i,a,sum=0;BiTree bt; bt=InitBiTree(bt);#if CHARprintf(請(qǐng)先序輸入二叉樹(如:ab三個(gè)空格表示a為根結(jié)點(diǎn),b為左子樹的二叉樹)n); #elseprintf(請(qǐng)先序輸入二叉樹(如:1 2 0 0 0表示1為根結(jié)點(diǎn),2為

8、左子樹的二叉樹)n); #endifbt=CreateBiTree(bt);printf(輸入建立的二叉樹!n);PrintTree(bt,5);doprintf();printf(n 主菜單);printf(n 1二叉樹先序遍歷);printf(n 2二叉樹中序遍歷);printf(n 3 二叉樹后序遍歷); printf(n 4 二叉樹葉子結(jié)點(diǎn)數(shù)); printf(n 5 二叉樹結(jié)點(diǎn)數(shù));printf(n 6 二叉樹查找 x 結(jié)點(diǎn)); printf(n 0退出);printf(n);printf(n);printf(輸入你要選擇的數(shù)據(jù):”)； scanf(%d,&i);switch(i)case 1: printf(先序遍歷結(jié)果為:)； Prorder1(bt,visit)； break；case 2: printf(后序遍歷結(jié)果為:”)； Prorder2(bt,visit)； break；case 3: printf(中序遍歷結(jié)果為:)； Prorder3(bt,visit)； break；case 4: j=SumLefts(bt,sum)；printf(”樹的葉子結(jié)點(diǎn)數(shù)為d:,j);break；case 5: j=SumTree(bt)；printf(”樹的結(jié)點(diǎn)數(shù)為%d:,j);break；case 6: printf(輸入要查