树和二叉树-浙江海洋学院东海科技学院.ppt

第6章 树 第6章 树 6.1 树的概念及操作 6.2 二叉树 6.2.1 二叉树的概念及操作 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 二叉树的遍历 6.4 线索二叉树 6.5 树和森林 6.5.1 树的存储结构 6.5.2 森林、树、二叉树的相互转换 6.5.3 树和森林的遍历 6.6 哈夫曼树及其应用 6.6.1 最优二叉树(哈夫曼树) 6.6.2 哈夫曼编码 *6.7算法设计举例 主要内容 知识点 树和二叉树定义 二叉树的性质，存储结构 二叉树的遍历及遍历算法的应用 ** 线索二叉树 二叉树和树及森林的关系 Huffman树与Huffman编码 重点难点 二叉树的性质及应用 二叉树的遍历算法及应用 ** 线索二叉树的算法 Huffman树的构造方法 树的算法 树例与特征 社会的组织结构 家族的族谱 计算机中的目录组织 树的定义 树(Tree)是n(n=0)个结点的有限集。n=0时称为空树。 （注：有人定义树不能为空） 有且仅有一个称为根的结点（Root）； n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,…,Tm,其中每个集合又是一棵树，称为子树(SubTree) 树的定义 树的递归定义的各子树T1,T2,…,Tm的相对次序是重要的，即树是有序的。 树定义(图示) 树的抽象数据类型的定义 ADT Tree{ 数据对象 D：D是具有相同特性的数据元素的集合。 数据关系 R：若D为空集，则称为空树； 若D仅含有一个数据元素，则R为空集，否则R={H}，H是如下定义的二元关系： （1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； （2）若D-{root}??,则存在D-{root}的一个划分D1，D2,…,Dm（m0）,对任意j?k(1?j,k?m)有Dj?Dk=?,且对任意的i(1? i ?m ),存在唯一数据元素xi? Di ,root,xi?H; （3）对应于D-{root}的划分，H-{root,x1,…root,xm}有唯一的一个划分H1, H2,…,Hm(m0),对任意j?k(1?j,k?m)有Hj?Hk=?,且对任意i(1? i ?m )，Hi是Di上的二元关系，（Di，{Hi}）是一棵符合本定义的树，称为根root的子树。 （转下页） 树的抽象数据类型(续) 树的其它表示方式 树的概念 结点：一个数据元素及若干指向其子树的分支； 结点的度：结点拥有的子树的数目。 树的度：树内各结点的度的最大值； 叶子（终端结点）：度为0的结点； 分支结点（非终端结点）：度不为0的结点；除根结点外，也称内部结点； 孩子，双亲，兄弟，堂兄：结点的子树的根称为该结点的孩子；该结点称为孩子的双亲；同一个双亲的孩子之间互称兄弟；其父结点是兄弟的结点互称堂兄。 概念 祖先：从根结点到该结点所经分支上的所有结点。 子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。 层次：结点在树结构中的层（一般定义根为1层）。 深度：树中结点的最大层次称为树的深度。 有序树：结点的子树在树中的位置固定，不能互换，称有序树。 无序树：子树在树中的位置可以互换。 森林：m(m≥0)棵互不相交的树的集合。 概念示例 结点 结点的度(Degree) 叶子（Leaf)或终端结点 分支结点或非终端结点 树的度 层次(Level) 树的深度(Depth) 孩子（child) 双亲（Parent) 兄弟(Sibling) 祖先 子孙 自测题 1 二叉树的概念 二叉树(Binary Tree)：或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的左子树和右子树所组成的非空树，左子树和右子树同样也都是二叉树 特征： 每个结点最多只有两棵子树 子树有左右之分，其次序不能任意颠倒，只有一棵子树时也必须分清是左、右子树。 二叉树的抽象数据类型 ADT BinTree{ 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D=?，则R=?，称二叉树为空二叉树； 若D??，则R={H}，H是如下二元关系： （1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； （2）若D-{root}??,则存在D-{root}={D1,Dr},且 D1?Dr??； （3）若D1??，则D1中存在唯一的元素x1,root, x1?H,且存在D1上的关系H1?H；若Dr??,则Dr中存在唯一的元素xr, root, xr?H, 且存在Dr上的关系Hr?H