数据结构第章树与二叉树 ppt 课件.ppt 1、第 5 章树和二叉树〔TreeBinaryTree〕特点：非线性结构，一个直接前驱，但可能有多个直接后继。〔一对多或 1:n〕5.1 树的概述 5.2 二叉树定义和性质 5.3 遍历二叉树 5.4 线索二叉树 5.5 树和森林 5.6 哈夫曼及其应用 15.1 树的基本概念 1.树的定义 2.若干术语 3.规律结构 4.存储结构 5.树的运算 21.树的定义注 1：树的定义具有递归性，即“树中还有树”。由一个或多个(n≥0)结点组成的有限集合 T，有且仅有一个结点称为根〔root〕，当 n1 时，其余的结点分为 m(m≥0)个互不相交的有限集合 T1,T2，…，Tm。 2、每个集合本身又是棵树，被称作这个根的子树。3 树的表示法主要有 5种：图形表示法嵌套集合表示法广义表表示法凹入表示法左孩子－右兄弟表示法 4 图形表示法：老师学生其他人员 2024 级 2024 级 2024 级 2024 级……华科大武昌分校电信系计算机系自控系……叶子根子树 5 嵌套集合表示法 6 广义表表示法(A(B(E(K,L),F),C(G),D(H(M),I,J))根作为由子树森林组成的表的名字写在表的左边 datalink1link2...linkn 麻烦问题：应当开设多少个链域?7 凹入表示法(又称名目表示法)8 左孩子－右兄弟表示法 ABCDEFGHIJ 3、KLM 数据左孩子右兄弟 92.若干术语——即树的数据元素——结点挂接的子树数结点结点的度结点的层次终端结点分支结点树的度树的深度(或高度)——从根到该结点的层数〔根结点算第一层〕——即度为 0 的结点，即叶子——即度不为 0 的结点〔也称为非终端结点〕——全部结点度中的最大值〔Max{各结点的度}〕——指全部结点中最大的层数〔Max{各结点的层次}〕问：右上图中的结点数＝；树的度＝；树的深度＝1334〔有几个直接后继就是几度，亦称“次数”〕ABCGEIDHFJFLK103.树的规律结构一对多〔1:n〕，有多个直接后继〔如家谱树、名目树等等〕 4、，但只有一个根结点，且子树之间互不相交。4.树的存储结构商量 1：树是非线性结构，该怎样存储？特点：——仍旧有顺序存储、链式存储等方式。115.2 二叉树为何要重点讨论每结点最多只有两个“叉”的树？二叉树的结构最简洁，规律性最强；可以证明，全部树都能转为唯一对应的二叉树，不失一般性。1.二叉树的定义 2.二叉树的性质 3.二叉树的存储结构〔二叉树的运算见5.3 节〕121.二叉树的定义定义：是 n〔n≥0〕个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树...
