二叉树的各种算法

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、结点*/BiTNode *p;/*利用函数名返回结果*/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(请先序输入二叉树(如:ab三个空格表示a为根结点,b为左子树的二叉树)n); #elseprintf(请先序输入二叉树(如:1 2 0 0 0表示1为根结点,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 二叉树叶子结点数); printf(n 5 二叉树结点数);printf(n 6 二叉树查找 x 结点); printf(n 0退出);printf(n);printf(n);printf(输入你要选择的数据:”)； scanf(%d,&i);switch(i)case 1: printf(先序遍历结果为:)； Prorder1(bt,visit)； break；case 2: printf(后序遍历结果为:”)； Prorder2(bt,visit)； break；case 3: printf(中序遍历结果为:)； Prorder3(bt,visit)； break；case 4: j=SumLefts(bt,sum)；printf(”树的叶子结点数为d:,j);break；case 5: j=SumTree(bt)；printf(”树的结点数为%d:,j);break；case 6: printf(输入要查