第六章树和二叉树 基本概念 二叉树 二叉树的遍历和线索树 树 赫夫曼树 只有根结点的树 一般树 数据结构 层次 C 树和二叉树 G( 4(K)(L
1 第六章 树和二叉树 基本概念 二叉树 二叉树的遍历和线索树 树 赫夫曼树 数 据 结 构 之 树 和 二 叉 树 2 只有根结点的树 一般树 层次 1 2 3 4 A B C D E F G K L H I J M A
61树的基本概念 树的基本概念 结 1.树:是n(n>=0)个结点的有限集 n=0称空树。 在任一非空树(n>0)中 (1)有且仅有一个称为根的结点; 树 (2)其余结点可分为m(m>=0)个互不相交的 和有限集T1,T2,…,Tm,其中,每个集 合本身又是一棵树,并且称为根的子树 树2.结点的度:树的结点所拥有的子树数; 3.树的度:是树内各结点的度的最大值 4度为0的结点称为叶结点或终端结点 5.孩子结点、双亲结点、兄弟结点、堂兄弟 数 据 结点、祖先结点、子孙结点 物6结点的层次从根开始,根为第一层,根的 孩子为第二层;若某结点在第L层,则其 子树的根就在第L+1层。 7.树的深度或高度:树中结点的最大层次 树8有序树:如果将树中结点的各子树看成是 从左至右有次序的;反之,则是无序树 树9.森林:是m棵互不相交的树的集合
2 数 据 结 构 之 树 和 二 叉 树 3 6.1 树的基本概念 ¾ 树的基本概念 1. 树：是n(n>=0)个结点的有限集。 n=0 称空树。 在任一非空树(n>0)中: (1) 有且仅有一个称为根的结点； (2) 其余结点可分为m(m>=0)个互不相交的 有限集T1，T2，……，Tm，其中，每个集 合本身又是一棵树，并且称为根的子树。 2. 结点的度：树的结点所拥有的子树数； 3. 树的度：是树内各结点的度的最大值； 4. 度为0的结点称为叶结点或终端结点 数 据 结 构 之 树 和 二 叉 树 4 5. 孩子结点、双亲结点、兄弟结点、堂兄弟 结点、祖先结点、子孙结点…… 6. 结点的层次从根开始，根为第一层，根的 孩子为第二层；若某结点在第L层，则其 子树的根就在第L+1层。 7. 树的深度或高度：树中结点的最大层次。 8. 有序树：如果将树中结点的各子树看成是 从左至右有次序的；反之，则是无序树。 9. 森林：是m棵互不相交的树的集合
数据结构 例:9个根结点的树:A是根,其他结点为三 个互不相交的有限集,T1={B,E,F,G,I} T2={C},T3={D,H},T13都是根A的子树,而本 身又都是一棵树 树和二叉树 ⑥D 树的表示法 数据结构 分支图表示法 嵌套集合表示法 树和二叉树 广义表表示法 (A(B(D).C)
3 数 据 结 构 之 树 和 二 叉 树 5 例：9个根结点的树：A是根，其他结点为三 个互不相交的有限集，T1= {B, E, F, G, I}, T2 ={C},T3 ={D,H},T1-3都是根A的子树，而本 身又都是一棵树。 A B C D E F G H I 数 据 结 构 之 树 和 二 叉 树 6 ¾ 树的表示法 ¾ 分支图表示法 ¾ 嵌套集合表示法 ¾ 广义表表示法 (A(B(D),C)) A B C D A B C D
树的基本操作 初始化操作 INITIATE(T):创建一棵空树。 据结构 求根函数R00T(T):求树T的根;R0OT(X:求 结点x所在树的根。 求双亲函数 PARENT(T,x):在树T中求x的双亲 求第个孩子函数 CHILD(T,x,i):在树T中求 树和二叉树 结点x的第i个孩子。 求兄弟函数: > LSIBLING(T,x):在T中求x的左兄弟 RSIBLING(T,x):在树T中求x的右兄弟 数据结构 建树函数 CRT-TREE(x,F):建立以结点x为 根,森林F为子树的树。 插入子树操作INS- CHILD(y,i,x):将x作为 y的第i棵子树 删除子树操作 DEL-CHILD(x,i):删除x的第 i棵子树。 树和二叉树 遍历树操作 TRAVERSE(T):按顺序访问树T 中各个结点 >置空树操作 CLEAR(T):将树T置为空树
4 数 据 结 构 之 树 和 二 叉 树 7 ¾ 树的基本操作 ¾ 初始化操作INITIATE(T)：创建一棵空树。 ¾ 求根函数ROOT(T)：求树T的根；ROOT(X)：求 结点x所在树的根。 ¾ 求双亲函数PARENT(T,x)：在树T中求x的双亲。 ¾ 求第i个孩子函数CHILD(T,x,i)：在树T中求 结点x的第i个孩子。 ¾ 求兄弟函数： ¾LSIBLING(T,x):在T中求x的左兄弟 ¾RSIBLING(T,x):在树T中求x的右兄弟 数 据 结 构 之 树 和 二 叉 树 8 ¾ 建树函数CRT-TREE(x,F)：建立以结点x为 根，森林F为子树的树。 ¾ 插入子树操作INS-CHILD(y,i,x)：将x作为 y的第i棵子树。 ¾ 删除子树操作DEL-CHILD(x,i)：删除x的第 i棵子树。 ¾ 遍历树操作TRAVERSE(T)：按顺序访问树T 中各个结点。 ¾ 置空树操作CLEAR(T)：将树T置为空树
6.2二叉树 数>二叉树的概念 1、特点:每个结点至多只有两棵子树,左右子树次 构序不能改变。 2、满二叉树:一个深度为k,且有21个结点的二 叉树。特点:树中没有度为1的结点。 3、完全二叉树:当树中每个结点都与相同深度的满 树二叉树中编号从1至n的结点一一对应。 和二叉树 自060606 据例:有5种类型的二叉树如下 构 只有左子树 只一个根结点 树和二叉树 只有右子树 左右子树都有 10
5 数 据 结 构 之 树 和 二 叉 树 9 6. 2 二叉树 ¾ 二叉树的概念 1、特点：每个结点至多只有两棵子树，左右子树次 序不能改变。 2、满二叉树：一个深度为k，且有2 -1个结点的二 叉树。特点：树中没有度为1的结点。 3、完全二叉树：当树中每个结点都与相同深度的满 二叉树中编号从1至n的结点一一对应。 一 般 二 叉 树 满 二 叉 树 完 全 二 叉 树 k 数 据 结 构 之 树 和 二 叉 树 10 例：有5种类型的二叉树如下 A A B A B A B C 空 只一个根结点 只有左子树 只有右子树 左右子树都有
二叉树的性质 数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;}