二叉树的性质 数1、在二叉树的第i层上至多有2个结点(i>=1 据结构之树和二叉树 2、深度为k的二叉树至多有2-1个结点(k>=1 3、对任何一棵二叉树T,如果其终端结点数为 n,度为2的结点数为m,则n=n2+1。 4、具有n个结点的完全二叉树的深度为 log2n+ 5、如果对一棵有n个结点的完全二叉树的结 点按层序编号(每层从左到右),则对任 结点i有 |(1)可求得其双亲结点的序号为/2」(>1)i=1 时为二叉树的根结点无双亲结点; k2(2如果存在的话,可求得其左右孩子结点的 序号:Rchd(i)=2i+1, Lchild(i)=2 树和二叉树 6 12
6 数 据 结 构 之 树 和 二 叉 树 11 ¾ 二叉树的性质 1、在二叉树的第 i 层上至多有2 个结点(i>=1); 2、深度为k的二叉树至多有2 -1个结点(k>=1); 3、对任何一棵二叉树T，如果其终端结点数为 n0，度为2的结点数为n2，则n0=n2+1。 4、具有n个结点的完全二叉树的深度为: log2 n +1 k i-1 数 据 结 构 之 树 和 二 叉 树 12 5、如果对一棵有n个结点的完全二叉树的结 点按层序编号（每层从左到右），则对任 一结点i有 (1)可求得其双亲结点的序号为 i / 2 (i>1),i=1 时为二叉树的根结点,无双亲结点； (2)如果存在的话，可求得其左右孩子结点的 序号:Rchild(i)=2i+1;Lchild(i)=2i;
二叉树的存储结构 数1、顺序存储结构:用一组连续的 菇存储单元B(1:n存储二又树的 构数据元素。按完全二叉树的规 则对二叉树中的结点进行编号,(B 树号为的的败据元@0 素存放在Bt订中,若编号为 的结点为空,则Btj=0 G 123456789 ABICODEIFI0OIG 二叉树顺序存储的算法描述 初始化二叉树 据# define max size100 I* typedef int TElemType; typedef TElem Type SqbT[Max Size+1: void initBt( Sqbt b{设置空树 树和二叉树 Int 1: 及for(i=1 g i<=Max Size; i++) bt[i|=0:
7 数 据 结 构 之 树 和 二 叉 树 13 ¾ 二叉树的存储结构 1、顺序存储结构：用一组连续的 存储单元Bt(1:n)存储二叉树的 数据元素。按完全二叉树的规 则对二叉树中的结点进行编号， 相应的空位也编上号，将二叉 树中编号为i的结点的数据元 素存放在Bt[i]中，若编号为j 的结点为空，则Bt[j]=0. 1 2 3 4 5 6 7 8 9 10 A B C 0 D E F 0 0 G 数 据 结 构 之 树 和 二 叉 树 14 ¾ 二叉树顺序存储的算法描述 ¾ 初始化二叉树 #define Max_Size 100 typedef int TElemType; typedef TElemType SqBT[Max_Size+1]; void InitBT(SqBT bt){//设置空树 int i; for(i=1;i<=Max_Size;i++) bt[i]=0; }
>插入一个元素的算法 数 void Insert(( Sqbt bt){ 结 int k, done=l; TElemType e; 构 while(done){ printf("In Number, dataIn) scanf(%d, %d", &k, &e); if(k<=Max Size & bt[k/2d i 树和二叉树 bt[k=e; done=0; se printf("nltERROR, input again. ) 15 创建二叉树的算法 数据结构 void CreatebT(Sqbt bt)( int nik: TElemType e; printf(" in Please Input n=; scanf(%d", &n); bt(0=1; 树和二叉树 printf("In Number, data\n); for(i=l; i<=n; i++) Insert(bt); 16
8 数 据 结 构 之 树 和 二 叉 树 15 ¾ 插入一个元素的算法 void Insert(SqBT bt){ int k ,done=1; TElemType e; while (done) { printf("\n Number,data\n"); scanf("%d,%d",&k,&e); if(k<=Max_Size && bt[k/2]) { bt[k]=e; done=0; } else printf("\n\tERROR, input again."); } } 数 据 结 构 之 树 和 二 叉 树 16 ¾ 创建二叉树的算法 void CreateBT(SqBT bt) { int n,i,k; TElemType e; printf("\n Please Input n="); scanf("%d",&n); bt[0]=1; printf("\n Number,data\n"); for(i=1;i<=n;i++) Insert(bt); }
>前序遍历顺序二叉树算法 #s void PrebT(SqBT bt, int i) if(i>=Max Size bti return; printf("%3d",bt); PreBT(bt, 2*1); 树和二叉树 PreBle(bt,2*i计+1); 中序打印二叉树的树形算法 数据结构 void InBT(SqBT bt, int i, int k)f int j; if(i> Max Size! bti) return InbT(bt, 2*i+1, k+10) for(j=0; j<k:j++) printf(); 树和二叉树 printf(%3d\n",bt[iD); In bT(bt, 21, k+10);
9 数 据 结 构 之 树 和 二 叉 树 17 ¾ 前序遍历顺序二叉树算法 void PreBT(SqBT bt,int i){ if(i>=Max_Size||!bt[i]) return; printf("%3d ",bt[i]); PreBT(bt,2*i); PreBT(bt,2*i+1); } 数 据 结 构 之 树 和 二 叉 树 18 ¾ 中序打印二叉树的树形算法 void InBT(SqBT bt,int i,int k){ int j; if(i>Max_Size||!bt[i]) return; InBT(bt,2*i+1,k+10); for(j=0;j<k;j++) printf(" "); printf("%3d\n",bt[i]); InBT(bt,2*i,k+10); }
>后序遍历顺序二叉树算法 据结构 void PostbT(Sqbt bt, int it if(i>Max Size:bti return; PostBT(bt, 2*1) PostEl(bt,2i计+1) 和prin"%3d",bti >两棵顺序二叉树的比较算法 >形状和元素值完全相同 # Status EqualS(SqBT bt, SqBT btl) for(i-l; i<=Max_Size; i++) if(bt:=buliD return FALSe 之 return TRUE;} 形状相同 *t Status SampleSq(SqBT bt, SqBT btl)( =for(=1;K<=Max Size &&((bt[i&&btllil)l:(bt[illbtlliD); i++); if(i<Max Size) return FALSE; 20 return TRUE
10 数 据 结 构 之 树 和 二 叉 树 19 ¾ 后序遍历顺序二叉树算法 void PostBT(SqBT bt,int i){ if(i>Max_Size||!bt[i]) return; PostBT(bt,2*i); PostBT(bt,2*i+1); printf("%3d ",bt[i]); } 数 据 结 构 之 树 和 二 叉 树 20 ¾ 两棵顺序二叉树的比较算法 ¾形状和元素值完全相同 Status EqualSq(SqBT bt, SqBT bt1){ for(i=1;i<=Max_Size;i++) if(bt[i]!=bt1[i]) return FALSE; return TRUE;} ¾形状相同 Status SampleSq(SqBT bt, SqBT bt1){ for(i=1;i<=Max_Size &&((bt[i]&&bt1[i])||!(bt[i]||bt1[i]));i++); if(i<Max_Size) return FALSE; return TRUE;}