《数据结构课件：第6章 树和二叉树》由会员分享，可在线阅读，更多相关《数据结构课件：第6章 树和二叉树（113页珍藏版）》请在金锄头文库上搜索。
1、第 2 页6.1 树的定义与基本术语树(Tree)是n个结点的有限集合，在任意一棵非空树中：（1）有且仅有一个称为根(Root)的结点。（2）其余结点可分为若干个互不相交的集合，且这些集合中的每一集合本身又是一棵树，称为根的子树(SubTree)。树是递归结构，树的定义是递归定义。JIACBDHGFE第 3 页6.1 树的定义与基本术语例：右面的图是一棵树T。 T = A，B，C，D，E，F，G，H，I，J A是根，其余结点可以划分为3个互不相交的集合： T1= B,E,F T2= C,G T3= D,H,I,J 这些集合中的每一集合本身又都是一棵树，它们是根 A 的子树。 对于T1，B是根，
2、其余结点可以划分为两个互不相交的集合： T11= E T12= F T11，T12是B的子树。JIACBDHGFE第 4 页6.1 树的定义与基本术语2）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继；4）除根之外的其它结点，都存在唯一一条从根到该结点的路径；5）树是一种分支结构（除了一个称为根的结点之外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。l从逻辑结构看:1）树中只有根结点没有前趋；JIACBDHGFE第 5 页6.1 树的定义与基本术语l树的应用家族树血统树(二叉树)第 6 页6.1 树的定义与基本术语l树的应用 常用的数据组织形式计算机的文件
3、系统。 不论是DOS文件系统还是window文件系统，所有的文件都是用树的形式进行组织。文件夹1 文件夹n 文件1 文件2文件夹2 1 文件夹22 文件21 文件22C第 7 页6.1 树的定义与基本术语l树的应用DNSNameSpace.“.”.comeducnedubittshuapku cs ee ss中国教育和科研网北理校园网第 8 页6.1 树的定义与基本术语l树的表示1）图示表示2）二元组表示3）文氏图表示4）广义表表示5）凹入表示法（类似书的目录）JIACBDHGFE第 9 页6.1 树的定义与基本术语D=A，B，C，D，E，F，G，H，I，JR=,l树的表示2）二元组表示JIA
4、CBDHGFE第 10 页6.1 树的定义与基本术语l树的表示3）文氏图表示ABCDEFGHIJMKLABCDEFGHIJMKL第 11 页6.1 树的定义与基本术语 假设树的根为root，子树为T1,T2,Tn，与该树对应的广义表为L，则：L=(原子(子表1,子表2, , 子表n)，其中原子对应root，子表 i(1i1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。第 17 页6.1 树的定义与基本术语l树的基本操作1) InitTree ( &T ); 构造空树 T。2) DestroyTree ( &T )
5、; 销毁树 T。3) CreateTree ( &T, definition ); 按 definition 构造树 T。4) ClearTree ( &T ); 将树 T 清空。5) TreeEmpty ( T ); 若树 T 为空，返回 TURE，否则返回 FALSE。6) TreeDepth ( T ); 返回树 T 的深度。第 18 页6.1 树的定义与基本术语l树的基本操作7) Root ( T ); 返回 T 的根结点。8) Value ( T, &cur_e ); 返回 T 树中 cur_e 结点的值。9) Assign ( T, cur_e, value ); 将 T 树中结点
6、 cur_e 的值赋值为value。10) Parent ( T, cur_e ); 返回 T 树 cur_e 结点的双亲。11) LeftChild ( T, cur_e ); 返回 T 树 cur_e 结点的最左孩子。第 19 页6.1 树的定义与基本术语l树的基本操作12) RightSibling ( T, cur_e ); 返回 T 树 cur_e 结点的右兄弟。13) InsertChild ( &T, &p, i, c ); 将 c 插入到树 T 中 p 所指向的第 i 棵子树中。14) DeleteChild ( &T, &p, i ); 删除树 T 中 p 所指向的第 i 棵
7、子树。15) TraverseTree ( T, Visit( ) ); 按某种次序对 T 树的每个结点调用函数Visit()一次且至多一次。也称为按照某种次序对树进行遍历。第 20 页6.1 树的定义与基本术语线性结构树型结构第一个数据元素 (无前驱) 根结点 (无前驱)最后一个数据元素 (无后继)多个叶子结点 (无后继)其它数据元素(一个前驱、 一个后继)其它数据元素(一个前驱、 多个后继)第 21 页6.2 二叉树l定义一棵二叉树是结点的一个有限集合，该集合或者一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为为空，或者是由一个根结点加上两棵分别称为左子树
8、左子树和和右子树右子树的、的、互不相交互不相交的二叉树组成。的二叉树组成。l l形式定义形式定义数据关系数据关系 R R 满足：满足： 若若 D D，则，则R R，称为是空二叉树。，称为是空二叉树。 若若 DD，则，则R R H H ，H H是如下二元关系：是如下二元关系：(1) (1) 在在D D中存在惟一的称为中存在惟一的称为根根的数据元素的数据元素rootroot，它在，它在关系关系H H下无前驱；下无前驱；(2) (2) 若若 D-rootD-root，则存在，则存在 D-rootD-root D Dl l,D,Dr r ，且，且D Dl lDDr r= =。第 22 页6.2 二叉树
9、l定义一棵二叉树是结点的一个有限集合，该集合或者一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为为空，或者是由一个根结点加上两棵分别称为左子树左子树和和右子树右子树的、的、互不相交互不相交的二叉树组成。的二叉树组成。ABCDEFGHK根结点左子树右子树第 23 页6.2 二叉树NLRLRNNN说明：说明： 1 1）二叉树中每个结点最多有两棵子树；二叉树）二叉树中每个结点最多有两棵子树；二叉树每个每个结点度小于等于结点度小于等于2 2； 2 2）左、右子树不能颠倒）左、右子树不能颠倒有序树有序树。l二叉树的五种基本形态空树只有根结点只有左子树只有右子树左右子树均
10、非空第 24 页6.2 二叉树l l二叉树二叉树 (a)、(b)是不同的二叉树(a)的左子树有四个结点，(b)的左子树有两个结点(a) A G E D B C F(b) A F G E D C B第 25 页6.2 二叉树l性质1：在二叉树的第i层上至多有2i-1 个结点(i1)。i=1 ：最多1个结点i=2 ：最多2个结点i=3 ：最多4个结点GAFEDCB第 26 页6.2 二叉树l性质1：在二叉树的第i层上至多有2i-1 个结点(i1)。用归纳法证明： 归纳基： 归纳假设： 归纳证明：i = 1 层时，只有一个根结点， 2 i-1 = 2 0 = 1；假设对所有的 j, 1j i，命题成
11、立；二叉树上每个结点至多有两棵子树，则第 i 层的结点数=2i-22=2i-1。第 27 页6.2 二叉树l性质2：深度为k的二叉树上至多含2k-1个结点(k1)。证明： 基于上一条性质，深度为 k 的二叉树上的结点数至多为：20+21+ +2k-1 = 2k-1 第 28 页6.2 二叉树l性质3：对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2的结点，则必存在关系式：n0 = n2+1证明：设 二叉树上结点总数：n = n0 + n1 + n2又 二叉树上分支总数：b = n1 + 2n2而 b = n-1 = n0 + n1 + n2 - 1由此， n0 = n2 + 1第
12、29 页6.2 二叉树l两类特殊的二叉树满二叉树：指的是深度为 k 且含有 2k-1 个结点的二叉树。完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。123456789101112131415abcdefghij第 30 页6.2 二叉树l性质4：具有n 个结点的完全二叉树的深度为 log2n +1。证明：设 完全二叉树的深度为 k 则根据第二条性质得 2k-1 n 2k 即 k-1 log2 n n，则该结点无左孩子；否则，编号为2i 的结点为其左孩子结点；(3)若2i+1n，则该结点无右孩子结点；否则，编号为2i+1 的结点为其右孩子结点。第 32 页6.
13、2 二叉树l性质5：i/2 ii+12i2i+12i+22i+3(a) i 和 i+1 结点在同一层 i+12i+22i+3i2i2i+1(b) i 和 i+1 结点不在同一层i -1i -2第 33 页6.2 二叉树l二叉树的存储结构1.二叉树的顺序结构对于完全二叉树，采用一组连续的内存单元，按编号顺序依次存储完全二叉树的结点。 1 2 3 4 5 6 7 m-1 A B C D E FAFEDCB123456第 34 页6.2 二叉树 对于一棵一般的二叉树，如果补齐构成完全二叉树所缺少的那些结点，便可以对二叉树的结点进行编号。 A F G E D C B16724538910第 35 页6
14、.2 二叉树 将二叉树原有的结点按编号存储到内存单元“相应”的位置上。 1 2 3 4 5 6 7 8 9 10 m-1 A B C D E 0 F 0 0 G A F G E D C B16724538910第 36 页6.2 二叉树对于一些“退化二叉树”，顺序存储结构存在突出缺点：比较浪费空间。DACBACBDA BCDBT8ABCDBT15第 37 页6.2 二叉树2.二叉链表二叉链表中每个结点包含三个域：数据域、左指针域、右指针域。typedef struct BiTNode ElemType data; struct BiTNode * lchild, * rchild; BiTNo
15、de, * BiTree;数据域指针域指针域结点存储数据元素指向右孩子指向左孩子第 38 页6.2 二叉树二叉树的二叉链表表示AFEDCB二叉链表图示DABC E F T第 39 页6.2 二叉树3.三叉链表三叉链表中每个结点包含四个域：数据域、双亲指针域、左指针域、右指针域。结点结构：parent lchild data rchildtypedef struct BiTNode ElemType data; struct BiTNode * lchild, * rchild; struct BiTNode * parent; BiTNode,*BiTree;第 40 页6.2 二叉树二叉树的
16、三叉链表表示rootADEBCFCEFDAB第 41 页6.2 二叉树4.静态二叉链表采用数组区间存贮的链表。孩子结点在数组中的位置。用-1表示无左孩子或右孩子0123456Lchild data rchildroot = 0AFEDCB2 A 13 C -15 B -1-1 E -1-1 F -1-1 D 4第 42 页6.2 二叉树4.静态二叉链表typedefstructBPTNode/结点结构TElemTypedata;intlchild,rchild;BNodetypedefstructBTree/树结构BNodenodesMAX_TREE_SIZE;intnum_node;/结点数目introot;/根结点的位置BTree;第 43 页6.2 二叉树5.双亲链表结点LRTag data parentGAFEDCB B 2 C 2 A -1 D 0 E 0 F 1 G 4 0123456 data parentLRLRLL第 44 页6.2 二叉树5.双亲链表typedefstructBPTNode/结点结构TElemTypedata;intparent;/指向双亲的指针ch
