资源描述：
《第五章java数据结构树和二叉树ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五章树和二叉树5.1树的有关概念5.2二叉树5.3二叉树的遍历5.4遍历的应用5.5线索二叉树5.6树和森林5.7哈夫曼树及应用1第六章树和二叉树本章学习要点：①熟练掌握二叉树的结构特点，了解相应的证明方法；②熟悉二叉树的各种存储结构的特点及使用范围；熟练掌握各种序遍历的递归和非递归算法，了解遍历过程中“栈”的状态，并能灵活运用遍历算法实现二叉树的其它各种运算；④了解线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握在中序线索化树上找给定结点的前驱和后继的方法；⑤熟悉树的各种存储结构及其特点；⑥学会编写实现树的各种运算的算法；⑦了解最优
2、树的特性，掌握建立最优树和哈夫曼编码的方法26.1树的有关概念5.1树的有关概念1.树的概念2.树的应用3.树的表示树的有关术语5树的基本操作35.1树的有关概念1．树的概念树（Tree）是n（n0）个结点的有限集合，在任一棵非空树(n>0)中： （1）有且仅有一个称为根的结点。 （2）其余结点可分为m（m0）个互不相交的集合，而且这些集合中的每一集合都本身又是一棵树，称为根的子树。树是递归结构，在树的定义中又用到了树的概念JIACBDHGFEKLM从逻辑结构看：1）树中只有根结点没有前趋； 2）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多
3、个后继； 4）除根外的其他结点，都存在唯一条从根到该结点的路径；5）树是一种分枝结构（除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。45.1树的有关概念例：下面的图是一棵树T={A,B,C,D,E,F,G,H,I,J，K，L，M}A是根，其余结点可以划分为3个互不相交的集合：T1={B,E,F，K，L},T2={C,G},T3={D,H,I,J，M}这些集合中的每一集合都本身又是一棵树，它们是A的子树。例如对于T1，B是根，其余结点可以划分为2个互不相交的集合：T11={E，K，L}，T12={F}，T11,T12是B的子树
4、。JIACBDHGFEKLM55.1树的有关概念2．树的应用 1）树可表示具有分枝结构关系的对象例1．家族族谱设某家庭有13个成员A、B、C、D、E、F、G、H、I、J，K，L，M他们之间的关系可下图所示的树表示：例2．单位行政机构的组织关系：JIACBDHGFEKLM65.1树的有关概念2）树是常用的数据组织形式有些应用中数据元素之间并不存在分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。例3计算机的文件系统 不论是DOS文件系统还是window文件系统，所有的文件是用树的形式来组织的。文件夹1文件夹n文件1文件2文件夹11文件夹12文件11
5、文件12C75.1树的有关概念3树的表示 1）图示表示2）二元组表示 3）嵌套集合表示4）凹入表示法（类似书的目录） 5）广义表表示（A（B（E（K,L）,F）,C（G）,D（H（M）,I,J）)）广义表表示ABEKLFCGDHMJI凹入表示法AEDHJIKLMFGC嵌套集合表示B85.1树的有关概念树的基本术语树的结点：包含一个数据元素及若干指向子树的分支；孩子结点(child)：结点的子树的根称为该结点的孩子；双亲结点(parent)：B结点是A结点的孩子，则A结点是B结点的双亲；兄弟结点(sibling)：同一双亲的孩子结点；堂兄结点(cousin)：其双
6、亲在同一层上的结点；祖先结点:从根到该结点的所经分支上的所有结点子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙JIACBDHGFEKLM95.1树的有关概念树的基本术语结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推树的深度：树中结点的最大层数，也称为树的高度结点的度：结点具有的子树个数树的度：树中最大的结点度叶子结点：也叫终端结点，是度为0的结点分枝结点：也叫非终端结点，是度不为0的结点有序树：子树有序的树，如：家族树；最左边的子树的根成为第一个孩子,最右边的称为最后一个孩子无序树：不考虑子树的顺序；森林；互不相交的树的集合；森林和树之间的
7、联系是：一棵树去掉根，其子树构成一个森林；一个森林增加一个根结点成为树。JIACBDHGFEKLM105.1树的有关概念5树的基本操作树的应用很广，应用不同基本操作也不同。下面列举了树的一些基本操作：1）initate(T)：T树的初始化，置T为空树。包括建树。2）root(T)：求T树的根。3）parent(T,x):求T树中x结点的双亲结点。4）Child(T,x,i)：求T树中x结点的第i个孩子结点。5）right_Sibling(T,x)：求T树中x结点的右兄弟6）insert_Child(y,i,x)：将根为x的子树置为y结点的第i个孩子7）del_c
8、hild(x,i)：删除
