数据结构第章树与二叉树 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{各结点的层次}〕问：右上图中的结点数＝；树的度＝
