《数据结构精品教学》树.ppt

2．链接存储结构 （2）广义标准方式 在标准方式的每个结点中，还增加了一个指向双亲结点的指针。 （3）二叉树方式 先将树转换为对应的二叉树形式，再用二叉链表存储。 5.5.2 树的存储结构 树转换为二叉树的方法： （1）加线：在树的所有兄弟之间加一条连线。 （2）删线： 对树中每个结点，只保留它与第一个孩子之间的连线，删除该结点与其它所有孩子结点之间的连线。 （3）旋转 以树的根结点为轴心，将子树顺时针旋转45度，使原来的右兄弟都变为结点的右孩子。 5.5.2 树的存储结构 （1）CreateGTree(GT,a) 功能：根据树的广义表形式a构造一棵树GT，即建立树的链接存储结构（标准方式）。 （2）树的遍历 功能：按照某种顺序依次访问树GT中的每个结点，并使每个结点只被访问一次。 分为三种：先根遍历、后根遍历、按层遍历 （3）FindGTree(GT,item) 功能：在树GT中查找值为item的结点，若找到则返回true，否则返回false。 递归思想。 5.5.3 树的运算 （4）PrintGTree(GT) 功能：以广义表的形式输出一棵树。递归思想。 （5）GTreeDepth(GT) 功能：求树的深度。即所有子树的最大深度+1。递归思想。 （6）ClearGTree(GT) 功能：先依次删除所有子树，然后删除根结点，最后置树为空。递归思想。 5.5.3 树的运算 复习小结： 掌握树的概念和有关术语。 理解树的性质。 掌握树的图示法和广义表表示，能熟练转换两种表示。 掌握二叉树的概念，理解二叉树的性质。 掌握二叉树的链接和顺序存储结构。 能够根据已知二叉树（通常广义表形式）写出其前序、中序、后序遍历的结果。 能够根据两种遍历序列求得二叉树。 掌握二叉树的基本运算，理解算法中的递归思想。 测试题 假定一棵树的广义表表示为A (B (C,D (E,F,G),H (I,J)))，则树中所含的结点数为( )个，树的深度为( )，树的度为( ) 。 在一棵二叉树的链表中，空指针域数等于非空指针域数加( )。 假定一棵二叉树的结点数为18，则它的最小深度为( )，最大深度为 ( )。 假定一棵二叉树广义表表示为a (b (c),d (e,f))，则对它进行前序、中序、后序遍历的结果分别为 ( )。 第五章 树 编程任务——哈夫曼树在通信编码中的应用 问题描述： 发电报时，电文中的字符都必须转换成0、1序列，例：A用000表示，B用001表示。这是编码。类似地，在接收端要解码。 同一份电文中，不同字符出现的频率不同，为了提高电文的输入和翻译效率，必须有一套简短而无歧义的字符代码。如何编码才能使传送的电报最短？ 这个问题曾经困扰了许多通信技术专家，直到人们对树结构有了认识之后，才有效的解决了该问题。它的实际意义在于：使整个电文的长度大大缩短，从而迅速提高了通信的效率。 有且只有一个根； 每个分枝又可以看作是一个树。 树的特点： ……………………… 在树的每个生长点处用结点来表示，可得： 根上有枝，枝上有叶。一个根上有多个分枝，每条枝上又有多个更小的枝，最后是叶。 5.1.1 树的定义 1）树的递归定义 在一棵非空树(n0,n为树的结点数)中，有且仅有一个根结点。 其余的结点可分为若干棵互不相交的子树。每棵子树也是一个树结构。 引言：前面我们学习的线性表是线性结构。接着要学习两种非线性数据结构——树和图。树型结构简称为树。 ……………………… 2）树的二元组定义 tree=(K,R) K=树中所有结点的集合＝{……} R＝各结点间的关系＝{r} 对于一棵非空树，r应满足以下条件： 有且仅有一个结点无前驱，该结点被称为根结点。 除根结点外，其余每个结点有且仅有一个前驱。 每个结点（包括根）可以有任意多个（含0个）后继。 ……………………… 树的应用 定义层次关系：如家族树，表示家庭结构的关系和辈分。如单位组织结构、计算机目录结构。 有序树：表明子树间的某种顺序关系。如书的目录结构。 用树来表示算术表达式：如书上例5-4 判定树： 思考：日常生活中树结构的例子。 if（条件1） if（条件2） if（条件3） Y Y Y N N N 叶结点：度为0（没有后继结点）的点。 分支结点：度0（至少有一个后继结点）的点。 问：哪些叶结点、分支结点？ 结点的孩子：结点的直接后继。 问：B的孩子？ 结点的双亲：结点的直接前驱。 问：D、E、F的双亲？ 兄弟：同一个双亲的孩子 祖先：根到该结点的