树和二叉树.pdf

第六章 树和二叉树第六章 树和二叉树教学内容：教学内容：树的基本概念；二叉树的性质和存树的基本概念；二叉树的性质和存 储结构；遍历二叉树和线索二叉树储结构；遍历二叉树和线索二叉树; 树的存储结构和遍历；哈夫曼树及树的存储结构和遍历；哈夫曼树及 其应用；其应用；要求学生要求学生 掌握：掌握：1、二叉树的结构特点；、二叉树的结构特点； 2、二叉树各种存储结构的特点及适用范、二叉树各种存储结构的特点及适用范 围；围； 3、按各种次序遍历二叉树的递归和非递归、按各种次序遍历二叉树的递归和非递归 算法；算法； 4、二叉树的线索化，在中序线索树上找给、二叉树的线索化，在中序线索树上找给 定结点的前驱和后继的方法；定结点的前驱和后继的方法； 5、树的各种存储结构及其特点；、树的各种存储结构及其特点； 6、编写树的各种运算的算法；、编写树的各种运算的算法； 7、建立最优二叉树和哈夫曼编码的方法建立最优二叉树和哈夫曼编码的方法教学重点教学重点 及难点：及难点：按各种次序遍历二叉树的递归和非按各种次序遍历二叉树的递归和非 递归算法递归算法本章章节本章章节§ 6.1 树的类型定义树的类型定义 § 6.2 二叉树的类型定义二叉树的类型定义 § 6.3 二叉树的存储结构二叉树的存储结构 § 6.4 二叉树的遍历二叉树的遍历 § 6.5 树和森林树和森林 § 6.6 树和森林的遍历树和森林的遍历 § 6.7 哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码6.1 树的类型定义树的类型定义§ 树是由树是由 n (n ≥ 0) 个结点的有限集合。

如果个结点的有限集合如果 n = 0，称为空树；如果，称为空树；如果 n > 0，则，则 § 有且仅有一个特定的称之为根有且仅有一个特定的称之为根(Root)的结的结 点，它只有直接后继，但没有直接前驱；点，它只有直接后继，但没有直接前驱； § 当当n > 1，除根以外的其它结点划分为，除根以外的其它结点划分为 m (m >0) 个互不相交的有限集个互不相交的有限集 T1, T2 ,…, Tm，， 其中每个集合本身又是一棵树，并且称为根其中每个集合本身又是一棵树，并且称为根 的子树的子树(SubTree)同理，每一棵子树又可同理，每一棵子树又可 以分为若干个互不相交的有限集以分为若干个互不相交的有限集……ACGT2DHIT3JMBELKT1F现实世界现实世界中，中，能用能用树的结构树的结构表示表示的的例例子：子：学学校校的的行政关系、书行政关系、书的的层次层次结构结构、人、人类的类的家族血缘关家族血缘关 系等系等ACGBDEFKLHMIJ例如例如A只有根结点的树只有根结点的树有有13个结点的树个结点的树其中：其中：A是根；其是根；其余余结点分结点分成三成三个互不相交的子集，个互不相交的子集， T1={B,E,F,K,L}；； T2={C,G}；； T3={D,H,I,J,M}, T1,T2,T3都都是根是根A的子树，且本身的子树，且本身也也是一棵树是一棵树6.1 树的类型定义树的类型定义§ 有有向向树：树： Ø(１１) 有确定的根；有确定的根； Ø(２２) 树根和子树根之间为有向关系。

树根和子树根之间为有向关系§ 有有序序树：树： Ø子树之间存在确定的次序关系子树之间存在确定的次序关系 § 无序无序树：树： Ø子树之间不存在确定的次序关系子树之间不存在确定的次序关系6.1 树的类型定义树的类型定义线性结构线性结构树型结构树型结构第一个第一个数据元素数据元素 (无无前驱前驱)根结点根结点 (无无前驱前驱)最最后一个后一个数据元素数据元素 (无无后继后继)多多个个叶叶子结点子结点 (无无后继后继)其它其它数据元素数据元素 (一个前驱一个前驱、、 一个后继一个后继)其它其它数据元素数据元素 (一个前驱一个前驱、、 多多个后继个后继)对比对比树型结构树型结构和和线性结构线性结构的结构特点的结构特点6.1 树的类型定义树的类型定义树的树的结点结点：包含一个数据元素：包含一个数据元素 及若干个指向其子及若干个指向其子 树的分支；树的分支； 结点的结点的度度：一个结点拥有的子树数目：一个结点拥有的子树数目(分支数分支数)；； 树的树的度度：一棵树上所有结点度的最大值；：一棵树上所有结点度的最大值； 叶叶子结点子结点（终端结点）：度为零的结点；（终端结点）：度为零的结点； 分分支支结点结点（非终端结点） ：度大于零的结点；（非终端结点） ：度大于零的结点； (从根到结点的从根到结点的)路径路径：：由从根到该结点所经分支和由从根到该结点所经分支和 结点构成；结点构成；基本术语基本术语DHIJM6.1 树的类型定义树的类型定义孩孩子结点子结点：结点的子树的根称为该结点的孩子结：结点的子树的根称为该结点的孩子结 点；点； 双亲双亲结点结点：相应地，该结点称为孩子的双亲结点；：相应地，该结点称为孩子的双亲结点； 兄弟兄弟：具有同一父结点的子结点互称兄弟；：具有同一父结点的子结点互称兄弟； 堂兄弟堂兄弟：其双亲在同一层的结点互为堂兄弟；：其双亲在同一层的结点互为堂兄弟； 祖先祖先结点结点：从根到该结点所经分支上的所有结点；：从根到该结点所经分支上的所有结点； 子子孙孙结点结点：以某结点为根的子树中任一结点都称为：以某结点为根的子树中任一结点都称为 该结点的子孙；该结点的子孙；ABCDEFGHIJMKL6.1 树的类型定义树的类型定义结点的结点的层次层次：从根结点到该结点所经过的路径长度：从根结点到该结点所经过的路径长度 加加1；；树的树的深度深度：树中叶子结点具有的最大层次数；：树中叶子结点具有的最大层次数；ABCDEFGHIJMKL6.1 树的类型定义树的类型定义1层层2层层4层层3层层height = 4ACGBDEFKLHMIJ6.1 树的类型定义树的类型定义有有序序树树：如果将树中结点的各子树看成：如果将树中结点的各子树看成从左至右从左至右是是 有次序的（即不能互换），则称该树为有序树；有次序的（即不能互换），则称该树为有序树；第一个第一个孩孩子子：在有序树中，：在有序树中，最左最左边边的的子树子树的的根根称为称为 第一个孩子；第一个孩子；最最后一个后一个孩孩子子：：最右最右边边 的的子树子树的的根根称为最后一个称为最后一个 孩子；孩子；ABCDEFGHIJMKL6.1 树的类型定义树的类型定义森林森林：是：是m(m ≥≥0)棵棵互不相交互不相交的树的集合。

对树的树的集合对树 中每个结点而言，其子树的集合即为森林中每个结点而言，其子树的集合即为森林任何一棵非空树是一个二元组任何一棵非空树是一个二元组 Tree = （（root，，F））其中：其中：root 被称为根结点被称为根结点 F 被称为子树森林被称为子树森林ArootBCDEFGHIJMKLF6.1 树的类型定义树的类型定义数据对象数据对象 D：D是具有相同特性的数据元素的集合是具有相同特性的数据元素的集合若若D为空集，则称为空树 为空集，则称为空树 否则否则: (1) 在在D中存在唯一的称为中存在唯一的称为根根的数据元素的数据元素root；； (2) 当当n>1时，其余结点可分为时，其余结点可分为m (m>0)个互不个互不 相交的有限集相交的有限集T1, T2, …, Tm，其中每一棵子集本身，其中每一棵子集本身 又是一棵符合本定义的树，称为根又是一棵符合本定义的树，称为根root的的子子树树数据数据关系关系 R：抽象抽象数据数据类型树的定义类型树的定义ADT Tree{6.1 树的类型定义树的类型定义基本基本操作：操作：查找查找类类插入插入类类删删除类除类}ADT Tree6.1 树的类型定义树的类型定义Root(T)// 求求树的根结点树的根结点查查找找类：类：Value(T, cur_e)// 求当求当前结点的元素前结点的元素值值Parent(T, cur_e)//求当求当前结点的前结点的双亲双亲结点结点LeftChild(T, cur_e)//求当求当前结点的最前结点的最左孩子左孩子RightSibling(T, cur_e)//求当求当前结点的前结点的右兄弟右兄弟TreeEmpty(T)//判判定树是否为空树定树是否为空树TreeDepth(T)//求求树的树的深度深度TraverseTree( T, Visit() )//遍历遍历6.1 树的类型定义树的类型定义InitTree( //求求结点结点函函数；数； Parent(T, e); //求双亲函求双亲函数；数； LeftChild(T, e)或或RightChild(T, e); //求孩子求孩子结点结点函函数数 LeftSibling(T, e)或或RightSibling(T, e); //求兄弟函求兄弟函数数 BiTreeEmpty(T); //树树判判空空函函数；数； BiTreeDepth(T); //求求树树深度函深度函数；数； PreOrderTraverse(T, Visit()); //先先序序边边历历操作操作 InOrderTraverse(T, Visit()); //中序中序边边历历操作操作 PostOrderTraverse(T, Visit()); //后序后序边边历历操作操作 LevelOrderTraverse(T, Visit()); //层层序序边边历历操作操作查查找找类：类：6.2 二叉树的类型定义二叉树的类型定义InitBiTree(//构构造造空的二叉树；空的二叉树；Assign(T, //结点结点赋值函赋值函数数CreateBiTree(//建树建树函函数；数；InsertChild(T, p, LR, c);//插入子插入子树树操作操作；；插入类插入类6.2 二叉树的类型定义二叉树的类型定义ClearBiTree( // 将将二叉树二叉树置置为空树为空树。

DestroyBiTree( // 销毁销毁二叉树二叉树DeleteChild(T, p, LR); // 删除子删除子树树操作操作；；删除类删除类6.2 二叉树的类型定义二叉树的类型定义§ 性质性质 1 ：：在二叉树的第在二叉树的第 i 层上至多有层上至多有2i- 1 个结点i≥≥1)4. 二叉树的二叉树的重要重要特性特性：：6.2 二叉树的类型定义二叉树的类型定义归归纳纳基基：： i = 1 时，只有一个根结点，显然时，只有一个根结点，显然 2 i- 1 = 20 = 1 正确；正确；归归纳假设：纳假设： 假设对所有的假设对所有的 j，，1≤≤ j n，则该结点无左孩子，，则该结点无左孩子， 否则，编号为否则，编号为 2i 的结点为其的结点为其左孩左孩子子结点；结点； (3) 若若 2i+1>n，则该结点无右孩子结点，，则该结点无右孩子结点， 否则，编号为否则，编号为2i+1 的结点为其的结点为其右孩右孩子子结点 (4) 结点结点i 所在层次为所在层次为log2 i6.2 二叉树的类型定义二叉树的类型定义6.3 二叉树的存储结构二叉树的存储结构§ 6.3.1 二叉树的顺序存储表示二叉树的顺序存储表示 § 6.3.2 二叉树的链式存储表示二叉树的链式存储表示6.3.1 二叉树的二叉树的顺顺序序存储存储表示表示§ 用一组地址连续的存储单元依次用一组地址连续的存储单元依次自自上上而下而下、、 自自左至右左至右存储存储完全完全二叉树二叉树上的结点元素。

上的结点元素 § 对于一般二叉树，则应将其每个结点与完对于一般二叉树，则应将其每个结点与完 全二叉树上的结点相对照，存储在一维数全二叉树上的结点相对照，存储在一维数 组的相应分量中组的相应分量中完全完全二叉树二叉树一一般般二叉树二叉树 的的顺顺序序表示表示的的顺顺序序表示表示11 2 3 4 5 6 7 8 91091 2 3 4 0 5 6 7 8 0 0 910 2489 1056731 2365478910顺顺序。