数据结构-第6章-数和二叉树.pptxVIP

1数据结构：

树

2第一章绪论第二章线性表第三章栈和队列第四章串第五章数组和广义表目录

3第六章树和二叉树第七章图第八章动态存储管理第九章查找第十章内部排序目录

第六章树和二叉树41、树的定义和基本术语3.遍历二叉树和线索二叉树4.数和森林 2.二叉树定义及存储5.哈夫曼数及其应用

家族谱系图祖父，伯父，祖父，父亲，祖父，叔父，伯父，堂兄，伯父，堂姐，父亲，你，叔父，堂弟，堂兄，侄儿关系表示法一对多关系

6.1树的定义和基本术语6.1树的定义和基本术语徐海学院计算机系

树型结构是一类重要的非线性结构树是以分支关系定义的层次结构树的应用人类社会的族谱社会组织结构在编译程序中的语法树在数据库系统中，可用树来组织信息

8树是由n（n≥0）个结点组成的有限集合A（b）仅含有根结点的树ABCDIHGFEJKLM（c）含有多个结点的树（a）空树?T1T2T3若n=0，称为空树；有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱；递归定义子树

10ABCDIHGFEJKLM结点：包含一个元素及若干指向其子树的分支，大写字母表示度：一个结点包含子树的数目，称为该结点的度A:3,B:2,F:0叶子：度为0的结点，称为叶子结点或树叶，也叫终端结点(J,K,L…)。

11ABCDIHGFEJKLM孩子结点：若结点X有子树，则子树的根结点为X的孩子结点A:B,C,D双亲结点：若结点A有子女B，则A为B的双亲结点。祖先结点：从根结点到该结点所经过分枝上的所有结点为该结点的祖先，M的祖先结点为：H,D,A

12ABCDIHGFEJKLM子孙结点：某一结点的子女及子女的子女都为该结点子孙。A:C,G…兄弟结点：具有同一个双亲的结点，称为兄弟结点。E，F分枝结点：除叶子结点外的所有结点，为分枝结点，也叫非终端结点.C

13ABCDIHGFEJKLM层数：根结点的层数为1，其它结点的层数为从根结点到该结点所经过的分支数目再加1。树的高度（深度）：树中结点所处的最大层数称为树的高度。

14有序树若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。无序树若一棵树中所有子树的次序无关紧要，则称为无序树。森林（树林）若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。删去一棵非空树的根结点，树就变成身森林；反之,若增加一个根结点,让森林中每一棵树的根结点都变成它的子女,森林就成为一棵树

线性结构树结构有头：存在唯一的没有前驱的首元素存在唯一的没有前驱的

根结点有尾：存在唯一的没有后继的尾元素存在多个没有后继的

叶子有前有后：其余元素均存在唯一的前驱元素和唯一的后继元素其余结点均存在唯一的

前驱(双亲)结点和多

个后继(孩子)结点

ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先

列出下图所示树的叶结点、分支结点和每个结点的层次。

6.2二叉树6.2二叉树徐海学院计算机系

什么是二叉树？19二叉树每个结点最多有两个孩子度=2有序树（分左右）?(a)(b)LR(e)L(c)R(d)

ABCDEGHF一个三层的二叉树最多有几个节点、最少有几个节点。

有一棵树的括号表示为A(B,C(E,F(G)),D)，回答下面的问题：1这棵树的根结点是多少2这棵树的叶子结点是什么3结点C的度是多少4这棵树的度是多少5这棵树的深度是多少6结点C的孩子结点是哪些7结点C的双亲结点是谁8

若一棵度为4的树中度为1、2、3、4的结点个数分别为4、3、2、2，则该树叶子结点的个数是多少？总结点个数是多少？

性质1在二叉树的第i层上至多有2i-1?个结点(i≥1)。ABCDEGHF归纳法证明

性质2深度为k的二叉树中至多含有2k-1个结点，(k≥1)。ABCDEGHF

性质3对任意一棵二叉树，如果叶子结点个数为n0，度为2的结点个数为n2，则有n0=n2+1。ABCDEGHFn=n0+n1+n21n=n1+2n2+12n0=n2+1

满二叉树ABCDEFGHIJKLMNO特点所有的分支结