《数据结构(第二版) 教学课件 ppt 作者 郑泳 方风波 第六章 树》由会员分享，可在线阅读，更多相关《数据结构(第二版) 教学课件 ppt 作者 郑泳 方风波 第六章 树（27页珍藏版）》请在金锄头文库上搜索。
1、第六章 树,知识教学目标,树和二叉树的概念、存储结构及相互转换的方法 二叉树性质的应用 二叉树遍历算法的应用 哈夫曼树的生成及编码,能力培养目标,树和二叉树的概念、存储结构及相互转换的方法 二叉树的定义、性质和存储结构 二叉树的遍历方法及算法 树与二叉树的相互转换 二叉树遍历算法的应用 二叉树的非递归遍历算法 线索二叉树的生成、存储及遍历 二叉树的递归编程应用,6.1 树的概念,6.1.1 树的定义 树（tree）是n（n0）个结点的有限集合T，当n=0时称为空树，在一棵非空树（n0）中满足如下两个条件： 1）有且仅有一个特定的称为根（root）的结点； 2）当n1时，其余结点可分为m（m 0
2、）个互不相交的有限集合T1 ，T2，Tm，其中每个集合又是一棵树，并称其为根的子树（subtree）。,除树形表示外，通常还有三种表示法,6.1.2 树的基本术语 1) 结点的度 2) 树的度 3) 分支结点 4) 叶子结点 5) 子结点 6) 双亲结点（父结点） 7)祖先结点、子孙结点 8) 兄弟结点、堂兄弟结点 9) 结点层数 10) 树的深度（高度） 11) 有序树 12) 无序树 13) 森林,6.1.3 树的基本操作 1) SetNull（T） 2) Root（T）或Root(x) 3) Parent（T，x） 4) Child（T，x，i） 5) Create（x，F） 6) Ad
3、dChild（y，i，x） 7) DelChild（x，i） 8) Traverse（T）,6.2 二叉树,6.2.1二叉树的定义 递归定义：二叉树是n(n 0)个结点有限集，当n=0时称为空树；当 n0 时，有而且仅有一个结点为根结点，其余结点构成2个互不相交的子集T1，T2，其中每一个子集又是一棵二叉树，分别称做为根结点的左子树和右子树。,6.2.2 二叉树的性质,【性质1】 在二叉树的第i层上至多有2i-1个结点(i1)。 【性质2】 深度为k的二叉树至多有2k-1个结点（k1）。 【性质3】 对任意一棵二叉树T，若终端结点数为n0，而其度数为2的结点数为n2，则n0= n2+1。,【性
4、质4】 具有n个结点的完全二叉树的深度为+1。其中表示不大于log2n的最大整数。 【性质5】 对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点有： 1) 如i=1，则序号为i的结点是根结点，无双亲结点；如i1，则序号为i的结点的双亲结点序号为。 2) 如2in，则序号为i的结点无左孩子；如2in，则序号为i的结点的左孩子结点的序号为2i。 3) 如2i1n，则序号为i的结点无右孩子；如2i1n，则序号为i的结点的右孩子结点的序号为2i1。,6.2.3 二叉树的存储结构,1. 顺序存储结构,二叉树顺序存储的类型定义类
5、似于顺序表，如下表示： #define MaxSize 101 /假定最大容量为101 typedef char DataType; typedef struct DataType dataMaxSize; /data0存放二叉树结点的个数，data1存放根结点 int n; /存放最后一个结点的下标，表当前的长度为n+1 SeqTree;,2.链式存储结构,二叉链表和三叉链表的结点表示,6.3 遍历二叉树,6.3.1 二叉树遍历方法 1) 先序遍历（DLR）操作过程： 若二叉树为空，则空操作；否则： 访问根结点；按先序遍历左子树；按先序遍历右子树。 2) 中序遍历（LDR）操作过程： 若二叉
6、树为空，则空操作；否则： 按中序遍历左子树；访问根结点；按中序遍历右子树。 3) 后序遍历（LRD）操作过程： 若二叉树为空，则空操作；否则： 按后序遍历左子树；按后序遍历右子树；访问根结点。,6.3.2 二叉树遍历的递归算法,【算法6.1】 先序遍历递归算法。 void Prev(NODE *root) if(root!=NULL) printf(“%d”,root-data); /输出结点 Prev(root-Lchild); /先序遍历左子树 Prev(root-Rchild); /先序遍历右子树 ,【算法6.2】 中序遍历递归算法。 void Mid(NODE *root) if(ro
7、ot!=NULL) Mid(root-Lchild); /中序遍历左子树 printf(“%d”,root-data); /输出结点 Mid(root-Rchild); /中序遍历右子树 ,【算法6.3】 后序遍历递归算法。 void Pos(NODE *root) if(root!=NULL) Pos(root-Lchild); /后序遍历左子树 Pos(root-Rchild); /后序遍历右子树 printf(“%d”,root-data); /输出结点 ,6.6 树和森林,6.6.1 树的存储结构 1双亲表示法 #define MAX_TREE_SIZE 100 typedef str
8、uct DataType data; int parent; Node; Node treeMAX_TREE_SIZE;,2. 孩子表示法 struct CTreeNode ElemType data; /结点值域 struct CTreeNode * tk; /结点指针域t0tk1，k为事先定义的常量 ,3孩子兄弟表示法 struct node DataType data; Struct node *firstchild, *nextsibling; ;,6.6.2 树、森林和二叉树的转换 一般树转化为二叉树的规则为： 1) 在所有兄弟之间加一连线。 2) 对每个结点，除了保留与其长子的连线
9、外，去掉该结点与其它孩子的连线。 3) 以树的根结点为轴心，将整棵树顺时针转动45度，使之结构层次分明。,森林转化成二叉树的规则是： 1) 若森林为空，则对应的二叉树为空； 2) 若森林非空，将森林中所有的树按照规则转化为二叉树； 3) 设置一个虚拟根结点，该结点的子树从左到右依次为森林中从左到右的树，即将所有的二叉树连接到虚拟根结点上； 4) 将这棵树按照规则转化为二叉树（实际仅需一层操作，即原各棵树的根结点按照兄弟结点的规则进行转化，在此过程中各根结点带上原子树一起移动）； 5) 去掉虚拟根结点，则二叉树的根结点为原第一棵树的根结点。,二叉树转化成森林的规则是： 1) 若二叉树为空，则对应
10、的森林为空； 2) 若二叉树非空，则对应的森林中第一棵树的根结点为二叉树的根结点，根结点的子树森林是由二叉树的左子树转化而成的森林；森林中除第一棵树之外其余树组成的森林是由二叉树的右子树转化而成的森林。,6.7 哈夫曼树及哈夫曼编码,1. 基本术语 1) 结点的权：在许多应用中，常常将树中的结点赋上一个有着某种实际意义的实数，称此实数为该结点的权。 2) 结点的带权路径长度：从树的根结点到某一结点之间的路径长度与该结点上权的乘积称为带权路径长度。 3) 树的带权路径长度：树中所有叶子结点的带权路径长度之和。 4) 哈夫曼树（Huffman Tree）：又称为最优二叉树。它是由n个带权树叶结点所
11、构成低的所有二叉树中带权路径长度wpl最小的二叉树。,2. 哈夫曼树的构造,1) 给定n个权值w1， w2，wn，对应n个结点，构成具有n棵二叉树的森林F=T1，T2，Tn，其中每棵二叉树Ti（1in）都只有一个权值为wi的根结点，其左右子树均为空。 2) 在森林F中选出两棵根结点的权值最小的树作为一棵新树的左、右子树，且置新树的根结点的权值为其左、右子树上根结点的权值之和。 3) 从F中删除构成新树的那两棵树，同时把新树加入F中。 4) 重复2)和3)，直到F中只含有一棵树为止，此树就是哈夫曼树。,3. 哈夫曼编码,在对哈夫曼树上的树叶结点进行编码时，有如下约定： 在这棵哈夫曼树中，所有左分
12、支表示字符“0”，右分支表示字符“1”，从根结点到树叶结点的路径上分支字符组成的字符串就称为该树叶结点的哈夫曼编码。,6.8 本章小结,树形结构是一种非常重要的层次型的一对多的非线性结构，在其中，除了根结点外，每个结点只有一个直接前趋但可以有多个直接后继。 树是一种重要的树形结构，它的存储结构可以采用双亲表示法、孩子表示法和孩子兄弟表示法来表示。 二叉树是一种特殊的树形结构，它的特点是每个结点最多只有两棵子树，并且二叉树的子树有左右之分，其次序不能任意颠倒。 二叉树的遍历是指按一定的规则和次序访问树中的每个结点，且每个结点只能被访问一次。主要有先序遍历、中序遍历和后序遍历三种方法。 哈夫曼树在现代通信中有较高的使用价值，应掌握它的构建方法及哈夫曼编码的应用。,
