二叉树算法总结.ppt

4、建立二叉树的存储结构 不同的定义方法相应有不同的存储结构的建立算法 二叉树算法总结： 遍历算法（前序、中序、后序、层次） 求结点个数（ n0、n1、n2 ） 复制二叉树 交换二叉树的左右子树 求树的高度、宽度 …… int count(BiTree T) { int l,r; if(!T) return 0; else if(!T-lchild!T-rchild) return 1; else { l=count(T-lchild); r=count(T-rchild); return(l+r+1); } } int count(BiTree T) { int l,r; if(!T) return 0; else if(!T-lchild!T-rchild) return 1; else { l=count(T-lchild); r=count(T-rchild); return(l+r); } } int count (BiTree T) {// int l,r; if(!T) return 0; else if(!T-lchildT-rchild|| T-lchild!T-rchild) return 1; else{ l=count (T-lchild); r=count (T-rchild); return(l+r);} } int count(BiTree T) { int l,r,n=0; if(!T) return 0; else if(!T-lchildT-rchild|| T-lchild!T-rchild) n=1; l=count(T-lchild); r=count(T-rchild); return(l+r+n); } int c=0; void count (BiTree T) { if(T) { count (T-lchild); count (T-rchild); if(!T-lchildT-rchild|| T-lchild!T-rchild) c++;} } void PreInOd(char preod[],char inod[],int i,int j,int k,int h,BiTree *t) { (*t) =(BiTNode*)malloc(sizeof(BiTNode)); (*t)-data=preod[i]; int m=k; while (inod[m]!=preod[i]) m++; if (m==k) (*t)-lchild=NULL; else PreInOd(preod,inod,i+1,i+m-k,k,m-1,(*t)-lchild); if (m==h) (*t)-rchild=NULL; else PreInOd(preod,inod,i+m-k+1,j,m+1,h,(*t)-rchild); } void disp(BiTree T) { if(T) { printf(%c,T-data); if(T-lchild||T-rchild) { printf((); disp(T-lchild); if(T-lchildT-rchild) printf(,); disp(T-rchild); printf()); } } } * * 二叉树的遍历 先（根）序的遍历算法 中（根）序的遍历算法 后（根）序的遍历算法 层次遍历 1、先序遍历 若二叉树为空，则空操作；否则 （1）访问根结点 （2）先序遍历左子树 （3）先序遍历右子树 A G C B E D H I J F K L A B D H I E J K C F L G 二叉树的先序遍历算法 Status PreOrderTraverse ( BiTree T ) { if ( T ) { Visit ( T-data ) ; PreOrderTraverse (T-lchild ); PreOrderTraverse (T-rchild );