Download presentation
Presentation is loading. Please wait.
1
数据结构 第六章 树与二叉树 深圳大学计算机系 蔡茂国
2
第６章 树与二叉树 第一节 树的概念与基本术语 一、树的定义(Tree) 树是有n(n≥0)个结点的有限集合。 如果 n=0，称为空树；
第６章 树与二叉树 第一节 树的概念与基本术语 一、树的定义(Tree) 树是有n(n≥0)个结点的有限集合。 如果 n=0，称为空树； 如果 n>0,称为非空树,对于非空树,有且仅有一个特定的称为根(Root)的节点(无直接前驱) 如果 n>1，则除根以外的其它结点划分为 m (m>0)个互不相交的有限集 T1, T2 ,…, Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。 每个结点都有唯一的直接前驱，但可能有多个后继 2
3
第６章 树与二叉树 第一节 树的概念与基本术语 一、树的定义(举例) A C G B D E F K L H M I J
第６章 树与二叉树 第一节 树的概念与基本术语 一、树的定义(举例) A C G B D E F K L H M I J A 只有根结点的树 有13个结点的树 其中：A是根；其余结点分成三个互不相交的子集， T1={B,E,F,K,L}； T2={C,G}； T3={D,H,I,J,M}, T1,T2,T3都是根A的子树，且本身也是一棵树 3
4
第６章 树与二叉树 第一节 树的概念与基本术语 二、树的基本术语 结点：包含一个数据元素及若干指向其子树的分支 结点的度：结点拥有的子树数
第６章 树与二叉树 第一节 树的概念与基本术语 二、树的基本术语 结点：包含一个数据元素及若干指向其子树的分支 结点的度：结点拥有的子树数 叶结点：度为0的结点[没有子树的结点] 分支结点：度不为0 的结点[包括根结点]， 也称为非终端结点。 除根外称为内部结点 1层 2层 4层 3层 Height = 4 A C G B D E F K L H M I J 4
5
第６章 树与二叉树 第一节 树的概念与基本术语 二、树的基本术语 孩子：结点的子树的根[直接后继，可能有多个]
第６章 树与二叉树 第一节 树的概念与基本术语 二、树的基本术语 孩子：结点的子树的根[直接后继，可能有多个] 双亲：孩子的直接前驱[最多只能有一个] 兄弟：同一双亲的孩子 子孙：以某结点为根的 树中的所有结点 祖先：从根到该结点 所经分支上的所有结点 1层 2层 4层 3层 Height = 4 A C G B D E F K L H M I J 5
![第６章 树与二叉树 第一节 树的概念与基本术语 二、树的基本术语 孩子：结点的子树的根[直接后继，可能有多个]](http://slidesplayer.com/slide/11606849/62/images/5/%E7%AC%AC%EF%BC%96%E7%AB%A0+%E6%A0%91%E4%B8%8E%E4%BA%8C%E5%8F%89%E6%A0%91+%E7%AC%AC%E4%B8%80%E8%8A%82+%E6%A0%91%E7%9A%84%E6%A6%82%E5%BF%B5%E4%B8%8E%E5%9F%BA%E6%9C%AC%E6%9C%AF%E8%AF%AD+%E4%BA%8C%E3%80%81%E6%A0%91%E7%9A%84%E5%9F%BA%E6%9C%AC%E6%9C%AF%E8%AF%AD+%E5%AD%A9%E5%AD%90%EF%BC%9A%E7%BB%93%E7%82%B9%E7%9A%84%E5%AD%90%E6%A0%91%E7%9A%84%E6%A0%B9%5B%E7%9B%B4%E6%8E%A5%E5%90%8E%E7%BB%A7%EF%BC%8C%E5%8F%AF%E8%83%BD%E6%9C%89%E5%A4%9A%E4%B8%AA%5D.jpg "第６章 树与二叉树. 第一节 树的概念与基本术语. 二、树的基本术语. 孩子：结点的子树的根[直接后继，可能有多个] 双亲：孩子的直接前驱[最多只能有一个] 兄弟：同一双亲的孩子. 子孙：以某结点为根的. 树中的所有结点. 祖先：从根到该结点. 所经分支上的所有结点. 1层. 2层. 4层. 3层. Height. = 4. A. C. G. B. D. E. F. K. L. H. M. I. J. 5.")
6
第６章 树与二叉树 第一节 树的概念与基本术语 二、树的基本术语 层次：根结点为第一层，其孩子为第二层，依此类推 深度：树中结点的最大层次
第６章 树与二叉树 第一节 树的概念与基本术语 二、树的基本术语 层次：根结点为第一层，其孩子为第二层，依此类推 深度：树中结点的最大层次 森林：互不相交的树的集合。 对树中每个结点而言， 其子树的集合即为森林 1层 2层 4层 3层 Height = 4 A C G B D E F K L H M I J 6
7
第６章 树与二叉树 第二节 二叉树 一、二叉树(Binary Tree) 每个结点最多有２棵子树 二叉树的子树有左右之分 L R
第６章 树与二叉树 第二节 二叉树 一、二叉树(Binary Tree) 每个结点最多有２棵子树 二叉树的子树有左右之分 L R 空树 只有根 只有左子树 只有右子树 有左右子树 7
8
第６章 树与二叉树 第二节 二叉树 二、二叉树性质１ 在二叉树的第i层上至多有2i-1个结点 证明：
第６章 树与二叉树 第二节 二叉树 二、二叉树性质１ 在二叉树的第i层上至多有2i-1个结点 证明： 1.i=1, 只有一个根节点，因此2i-1=20=1 2.设第i-1层上，以上性质成立，即第i-1层至多有2(i-1)-1结点。由二叉树的定义可知，任何结点的度小于2，因此，第i层上的结点数最多为第i-1层上的两倍，即2*2i-2=2i-1 8
9
第６章 树与二叉树 第二节 二叉树 三、二叉树性质２ 深度为k的二叉树至多有2k-1个结点 证明：
第６章 树与二叉树 第二节 二叉树 三、二叉树性质２ 深度为k的二叉树至多有2k-1个结点 证明： 1.由性质１，已知第i层上结点数最多为2i-1 k 2. ∑ 2i-1 = 2k-1 i=1 9
10
第６章 树与二叉树 第二节 二叉树 四、二叉树性质３ 如果二叉树终端结点数为n0，度为2的结点数为n2，则n0=n2+1 证明：
第６章 树与二叉树 第二节 二叉树 四、二叉树性质３ 如果二叉树终端结点数为n0，度为2的结点数为n2，则n0=n2+1 证明： 1.设n1为度为1的结点，则总结点数n= n0+n1+n2 2.设B为二叉树的分支数，除根结点外，每个结点有且只有一个分支，因此n=B+1 3.每个分支皆由度为1或2的结点发出，B=n1+2n2 4.n=B+1=(n1+2n2)+1 = n0+n1+n2，因此 n0=n2+1 10
11
第６章 树与二叉树 第二节 二叉树 五、满二叉树 一个深度为k且有2k-1个结点的二叉树 每层上的结点数都是最大数 可以自上而下、
第６章 树与二叉树 第二节 二叉树 五、满二叉树 一个深度为k且有2k-1个结点的二叉树 每层上的结点数都是最大数 可以自上而下、 自左至右连续编号 6 2 1 7 5 4 3 8 9 10 11 13 14 15 12 11
12
第６章 树与二叉树 第二节 二叉树 六、完全二叉树 当且仅当每一个结点都与深度相同的满二叉树中编号从1到n的结点一一对应的二叉树
第６章 树与二叉树 第二节 二叉树 六、完全二叉树 当且仅当每一个结点都与深度相同的满二叉树中编号从1到n的结点一一对应的二叉树 叶子结点只在最大两层上出现 左子树深度与右子树 深度相等或大１ 6 2 1 7 5 4 3 8 9 10 11 12 12
13
第６章 树与二叉树 第二节 二叉树 六、完全二叉树(性质４) 具有n个结点的完全二叉树,其深度为log2n +1
第６章 树与二叉树 第二节 二叉树 六、完全二叉树(性质４) 具有n个结点的完全二叉树,其深度为log2n +1 设k为深度，由二叉树性质２，已知 2k-1-1 < n ≤ 2k-1 即 2k-1 ≤ n < 2k 即 k = log2n +1 6 2 1 7 5 4 3 8 9 10 11 12 13
14
第６章 树与二叉树 第二节 二叉树 六、完全二叉树(性质５) 在完全二叉树中，结点i的双亲为i/2 结点i的左孩子LCHILD(i)=2i
第６章 树与二叉树 第二节 二叉树 六、完全二叉树(性质５) 在完全二叉树中，结点i的双亲为i/2 结点i的左孩子LCHILD(i)=2i 结点i的右孩子RCHILD(i)=2i+1 6 2 1 7 5 4 3 8 9 10 11 12 2i+2 i 2i+3 2i+1 2i i+1 i/2 14
15
第６章 树与二叉树 第二节 二叉树 七、二叉树的顺序存储结构 1 2 3 4 5 6 7 8 910
第６章 树与二叉树 第二节 二叉树 七、二叉树的顺序存储结构 用一组连续的存储单元依次自上而下,自左至右存储结点 1 2 4 8 9 10 5 6 7 3 9 1 2 3 6 4 7 8 10 5 完全二叉树的顺序表示 一般二叉树的顺序表示 15
16
第６章 树与二叉树 第二节 二叉树 七、二叉树的链式存储结构 1.二叉链表 采用数据域加上左、右孩子指针 data lChild
第６章 树与二叉树 第二节 二叉树 七、二叉树的链式存储结构 1.二叉链表 采用数据域加上左、右孩子指针 data lChild rChild lChild data rChild 16
17
第６章 树与二叉树 第二节 二叉树 七、二叉树的链式存储结构 1.二叉链表[定义] 二叉链表结点由一个数据域和两个指针域组成
第６章 树与二叉树 第二节 二叉树 七、二叉树的链式存储结构 1.二叉链表[定义] 二叉链表结点由一个数据域和两个指针域组成 typedef struct BiTNode { TElemType data; struct BiTNode *lChild, *rChild; } BiTNode, *BiTree; lChild data rChild 17
![第６章 树与二叉树 第二节 二叉树 七、二叉树的链式存储结构 1.二叉链表[定义] 二叉链表结点由一个数据域和两个指针域组成](http://slidesplayer.com/slide/11606849/62/images/17/%E7%AC%AC%EF%BC%96%E7%AB%A0+%E6%A0%91%E4%B8%8E%E4%BA%8C%E5%8F%89%E6%A0%91+%E7%AC%AC%E4%BA%8C%E8%8A%82+%E4%BA%8C%E5%8F%89%E6%A0%91+%E4%B8%83%E3%80%81%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%93%BE%E5%BC%8F%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84+1.%E4%BA%8C%E5%8F%89%E9%93%BE%E8%A1%A8%5B%E5%AE%9A%E4%B9%89%5D+%E4%BA%8C%E5%8F%89%E9%93%BE%E8%A1%A8%E7%BB%93%E7%82%B9%E7%94%B1%E4%B8%80%E4%B8%AA%E6%95%B0%E6%8D%AE%E5%9F%9F%E5%92%8C%E4%B8%A4%E4%B8%AA%E6%8C%87%E9%92%88%E5%9F%9F%E7%BB%84%E6%88%90.jpg "第６章 树与二叉树. 第二节 二叉树. 七、二叉树的链式存储结构. 1.二叉链表[定义] 二叉链表结点由一个数据域和两个指针域组成. typedef struct BiTNode { TElemType data; struct BiTNode *lChild, *rChild; } BiTNode, *BiTree; lChild data rChild. 17.")
18
第６章 树与二叉树 第二节 二叉树 七、二叉树的链式存储结构 1.二叉链表(举例) 二叉树（左）及其二叉链表（右） 18 A B C D F
第６章 树与二叉树 第二节 二叉树 七、二叉树的链式存储结构 1.二叉链表(举例) 二叉树（左）及其二叉链表（右） A B C D F E root A B C D F E root 18
19
lChild data parent rChild
第６章 树与二叉树 第二节 二叉树 七、二叉树的链式存储结构 ２.三叉链表 采用数据域加上左、右孩子指针及双亲指针 parent data lChild rChild lChild data parent rChild 19
20
第６章 树与二叉树 第二节 二叉树 七、二叉树的链式存储结构 ２.三叉链表(举例) 二叉树（左）及其三叉链表（右） A B C D F E
第６章 树与二叉树 第二节 二叉树 七、二叉树的链式存储结构 ２.三叉链表(举例) 二叉树（左）及其三叉链表（右） A B C D F E root A B C D F E root 20
21
第６章 树与二叉树 第三节 遍历二叉树 一、遍历二叉树 树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次
第６章 树与二叉树 第三节 遍历二叉树 一、遍历二叉树 树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次 一个二叉树由根节点与左子树和右子树组成 设访问根结点用D表示，遍历左、右子树用L、R表示 Ｄ L R 21
22
第６章 树与二叉树 第三节 遍历二叉树 一、遍历二叉树 如果规定先左子树后右子树，则共有三种组合 1.DLR [先序遍历]
第６章 树与二叉树 第三节 遍历二叉树 一、遍历二叉树 如果规定先左子树后右子树，则共有三种组合 1.DLR [先序遍历] 2.LDR [中序遍历] 3.LRD [后序遍历] Ｄ L R 22
![第６章 树与二叉树 第三节 遍历二叉树 一、遍历二叉树 如果规定先左子树后右子树，则共有三种组合 1.DLR [先序遍历]](http://slidesplayer.com/slide/11606849/62/images/22/%E7%AC%AC%EF%BC%96%E7%AB%A0+%E6%A0%91%E4%B8%8E%E4%BA%8C%E5%8F%89%E6%A0%91+%E7%AC%AC%E4%B8%89%E8%8A%82+%E9%81%8D%E5%8E%86%E4%BA%8C%E5%8F%89%E6%A0%91+%E4%B8%80%E3%80%81%E9%81%8D%E5%8E%86%E4%BA%8C%E5%8F%89%E6%A0%91+%E5%A6%82%E6%9E%9C%E8%A7%84%E5%AE%9A%E5%85%88%E5%B7%A6%E5%AD%90%E6%A0%91%E5%90%8E%E5%8F%B3%E5%AD%90%E6%A0%91%EF%BC%8C%E5%88%99%E5%85%B1%E6%9C%89%E4%B8%89%E7%A7%8D%E7%BB%84%E5%90%88+1.DLR+%5B%E5%85%88%E5%BA%8F%E9%81%8D%E5%8E%86%5D.jpg "第６章 树与二叉树. 第三节 遍历二叉树. 一、遍历二叉树. 如果规定先左子树后右子树，则共有三种组合. 1.DLR [先序遍历] 2.LDR [中序遍历] 3.LRD [后序遍历] Ｄ. L. R. 22.")
23
第６章 树与二叉树 第三节 遍历二叉树 二、先序遍历二叉树 算法： 1.若二叉树为空，则返回；否则： 2.访问根节点(D)
第６章 树与二叉树 第三节 遍历二叉树 二、先序遍历二叉树 算法： 1.若二叉树为空，则返回；否则： 2.访问根节点(D) 3.先序遍历左子树(L) 4.先序遍历右子树(R) Ｄ L R 23
24
第６章 树与二叉树 第三节 遍历二叉树 二、先序遍历二叉树 算法(举例)： 输出结果：ABDEGCF 1.若二叉树为空，则返回；否则：
第６章 树与二叉树 第三节 遍历二叉树 二、先序遍历二叉树 算法(举例)： 1.若二叉树为空，则返回；否则： 2.访问根节点(D) 3.先序遍历左子树(L) 4.先序遍历右子树(R) 输出结果：ABDEGCF (第一个输出节点必为根节点) A D B F C G E 24
25
第６章 树与二叉树 第三节 遍历二叉树 二、先序遍历二叉树 算法(C语言实现)：
第６章 树与二叉树 第三节 遍历二叉树 二、先序遍历二叉树 算法(C语言实现)： void PreOrderTraverse ( BinTree T ) { if (T) { cout << T->data; PreOrderTraverse ( T->lChild ); PreOrderTraverse ( T->rChild ); } 25
26
第６章 树与二叉树 第三节 遍历二叉树 三、中序遍历二叉树 算法： 1.若二叉树为空，则返回；否则： 2.中序遍历左子树(L)
第６章 树与二叉树 第三节 遍历二叉树 三、中序遍历二叉树 算法： 1.若二叉树为空，则返回；否则： 2.中序遍历左子树(L) 3.访问根节点(D) 4.中序遍历右子树(R) Ｄ L R 26
27
第６章 树与二叉树 第三节 遍历二叉树 三、中序遍历二叉树 算法(举例)： 输出结果：DBGEAFC 1.若二叉树为空，则返回；否则：
第６章 树与二叉树 第三节 遍历二叉树 三、中序遍历二叉树 算法(举例)： 1.若二叉树为空，则返回；否则： 2.中序遍历左子树(L) 3.访问根节点(D) 4.中序遍历右子树(R) 输出结果：DBGEAFC （先于根节点A输出的节点为左子树的节点 后于根节点A输出的节点为右子树的节点） A D B F C G E 27
28
第６章 树与二叉树 第三节 遍历二叉树 三、中序遍历二叉树 算法(C语言实现)：
第６章 树与二叉树 第三节 遍历二叉树 三、中序遍历二叉树 算法(C语言实现)： void InOrderTraverse ( BinTree T ) { if (T) { InOrderTraverse ( T->lChild ); cout << T->data; InOrderTraverse ( T->rChild ); } 28
29
第６章 树与二叉树 第三节 遍历二叉树 四、后序遍历二叉树 算法： 1.若二叉树为空，则返回；否则： 2.后序遍历左子树(L)
第６章 树与二叉树 第三节 遍历二叉树 四、后序遍历二叉树 算法： 1.若二叉树为空，则返回；否则： 2.后序遍历左子树(L) 3.后序遍历右子树(R) 4.访问根节点(D) Ｄ L R 29
30
第６章 树与二叉树 第三节 遍历二叉树 四、后序遍历二叉树 算法(举例)： 输出结果：DGEBFCA 1.若二叉树为空，则返回；否则：
第６章 树与二叉树 第三节 遍历二叉树 四、后序遍历二叉树 算法(举例)： 1.若二叉树为空，则返回；否则： 2.后序遍历左子树(L) 3.后序遍历右子树(R) 4.访问根节点(D) 输出结果：DGEBFCA (最后一个输出节点必为根节点) A D B F C G E 30
31
第６章 树与二叉树 第三节 遍历二叉树 四、后序遍历二叉树 算法(C语言实现)：
第６章 树与二叉树 第三节 遍历二叉树 四、后序遍历二叉树 算法(C语言实现)： void PostOrderTraverse ( BinTree T ) { if (T) { PostOrderTraverse ( T->lChild ); PostOrderTraverse ( T->rChild ); cout << T->data; } 31
32
第６章 树与二叉树 第三节 遍历二叉树 五、根据遍历序列求二叉树[参见pp154] 根据遍历的特性已知：
第６章 树与二叉树 第三节 遍历二叉树 五、根据遍历序列求二叉树[参见pp154] 根据遍历的特性已知： 1.先序遍历中，第一个输出节点必为根节点 2.中序遍历中，先于根节点D输出的节点为左 子树的节点，后于根节点D输出的节点为右 子树的节点 3.后序遍历中，最后一个输出节点必为根节点 Ｄ L R 32
![第６章 树与二叉树 第三节 遍历二叉树 五、根据遍历序列求二叉树[参见pp154] 根据遍历的特性已知：](http://slidesplayer.com/slide/11606849/62/images/32/%E7%AC%AC%EF%BC%96%E7%AB%A0+%E6%A0%91%E4%B8%8E%E4%BA%8C%E5%8F%89%E6%A0%91+%E7%AC%AC%E4%B8%89%E8%8A%82+%E9%81%8D%E5%8E%86%E4%BA%8C%E5%8F%89%E6%A0%91+%E4%BA%94%E3%80%81%E6%A0%B9%E6%8D%AE%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E6%B1%82%E4%BA%8C%E5%8F%89%E6%A0%91%5B%E5%8F%82%E8%A7%81pp154%5D+%E6%A0%B9%E6%8D%AE%E9%81%8D%E5%8E%86%E7%9A%84%E7%89%B9%E6%80%A7%E5%B7%B2%E7%9F%A5%EF%BC%9A.jpg "第６章 树与二叉树. 第三节 遍历二叉树. 五、根据遍历序列求二叉树[参见pp154] 根据遍历的特性已知： 1.先序遍历中，第一个输出节点必为根节点. 2.中序遍历中，先于根节点D输出的节点为左 子树的节点，后于根节点D输出的节点为右 子树的节点. 3.后序遍历中，最后一个输出节点必为根节点. Ｄ. L. R. 32.")
33
第６章 树与二叉树 第三节 遍历二叉树 五、根据先、中序遍历求序列二叉树
第６章 树与二叉树 第三节 遍历二叉树 五、根据先、中序遍历求序列二叉树 如果已知一棵二叉树的先序遍历和中序遍历序列，则可以惟一确定这棵二叉树 算法： 1.在先序遍历序列中，第一个节点为根节点D 2.在中序遍历序列中，根节点D左边的节点归为左子树，根节点D右边的节点归为右子树 3.对每个子树反复使用1,2两步，直到确定二叉树 33
34
第６章 树与二叉树 第三节 遍历二叉树 五、根据先、中序遍历求序列二叉树
第６章 树与二叉树 第三节 遍历二叉树 五、根据先、中序遍历求序列二叉树 已知一棵二叉树的先序遍历序列为：ABDEGCF，中序遍历序列为：DBGEAFC，请画出这棵二叉树 根据先序遍历序列，可知根节点为A；再根据中序遍历序列可知，左子树由DBGE组成，右子树由FC组成 A 左子树 右子树 B C D E F G 34
35
第６章 树与二叉树 第三节 遍历二叉树 五、根据先、中序遍历求序列二叉树
第６章 树与二叉树 第三节 遍历二叉树 五、根据先、中序遍历求序列二叉树 从整棵二叉树的先序遍历序列ABDEGCF可知，左子树的先序遍历序列为BDEG，右子树的先序遍历为CF 从整棵二叉树的中序遍历序列DBGEAFC右知，左子树的中序遍历为DBGE，右子树的中序遍历为FC 对左、右子树分别进行（上一页的）处理 35
36
第６章 树与二叉树 第三节 遍历二叉树 五、根据后、中序遍历求序列二叉树
第６章 树与二叉树 第三节 遍历二叉树 五、根据后、中序遍历求序列二叉树 如果已知一棵二叉树的先序遍历和中序遍历序列，则可以惟一确定这棵二叉树 算法： 1.在后序遍历序列中，最后一个节点为根节点D 2.在中序遍历序列中，根节点D左边的节点归为左子树，根节点D右边的节点归为右子树 3.对每个子树反复使用1,2两步，直到确定二叉树 36
37
第６章 树与二叉树 第三节 遍历二叉树 五、根据后、中序遍历求序列二叉树
第６章 树与二叉树 第三节 遍历二叉树 五、根据后、中序遍历求序列二叉树 已知一棵二叉树的后序遍历序列为：DGEBFCA，中序遍历序列为：DBGEAFC，请画出这棵二叉树 根据后序遍历序列，可知根节点为A；再根据中序遍历序列可知，左子树由DBGE组成，右子树由FC组成 A 左子树 右子树 B C D E F G 37
38
第６章 树与二叉树 第三节 遍历二叉树 五、根据后、中序遍历求序列二叉树
第６章 树与二叉树 第三节 遍历二叉树 五、根据后、中序遍历求序列二叉树 从整棵二叉树的后序遍历序列DGEBFCA可知，左子树的后序遍历序列为DGEB，右子树的后序遍历为FC 从整棵二叉树的中序遍历序列DBGEAFC右知，左子树的中序遍历为DBGE，右子树的中序遍历为FC 对左、右子树分别进行（上一页的）处理 38
39
第６章 树与二叉树 第四节 线索二叉树 一、增加新指针 最简单的方法是在每个结点中，增加前驱(fwd) 和后继(bkwd)指针
第６章 树与二叉树 第四节 线索二叉树 一、增加新指针 最简单的方法是在每个结点中，增加前驱(fwd) 和后继(bkwd)指针 在做二叉树遍历（前、中、后序），将每个结 点的前驱和后继信息添入fwd和bkwd域中 fwd lChild data rChild bkwd 39
40
第６章 树与二叉树 第四节 线索二叉树 二、利用空指针 在有n个结点的二叉树中，必定存在n+1个空链 域
第６章 树与二叉树 第四节 线索二叉树 二、利用空指针 在有n个结点的二叉树中，必定存在n+1个空链 域 因为每个结点有两个链域（左、右孩子指针）， 因此共有2n个链域 除根结点外，每个结点都有且仅有一个分支相 连，即n-1个链域被使用 40
41
第６章 树与二叉树 第四节 线索二叉树 二、利用空指针 在结点中增加两个标记位（LTag, RTag)
第６章 树与二叉树 第四节 线索二叉树 二、利用空指针 在结点中增加两个标记位（LTag, RTag) LTag=0, lChild域指示结点的左孩子 LTag=1, lChild域指示结点的前驱结点 RTag=0, lChild域指示结点的右孩子 RTag=1, lChild域指示结点的后继结点 LTag lChild data rChild RTag 41
42
第６章 树与二叉树 第五节 树与森林 一、树的存储结构 1.双亲表示法 采用一组连续的存储空间 由于每个结点只有一个双亲，只需要一个指针 A
第６章 树与二叉树 第五节 树与森林 一、树的存储结构 1.双亲表示法 采用一组连续的存储空间 由于每个结点只有一个双亲，只需要一个指针 A E B G D F C A B C D E F G -1 1 3 42
43
第６章 树与二叉树 第五节 树与森林 一、树的存储结构 2.孩子表示法[多重链表] 可以采用多重链表，即每个结点有多个指针
第６章 树与二叉树 第五节 树与森林 一、树的存储结构 2.孩子表示法[多重链表] 可以采用多重链表，即每个结点有多个指针 最大缺点是空链域太多 [(d-1)n+1个] data child1 child2 child3 childd A E B G D F C 43
![第６章 树与二叉树 第五节 树与森林 一、树的存储结构 2.孩子表示法[多重链表] 可以采用多重链表，即每个结点有多个指针](http://slidesplayer.com/slide/11606849/62/images/43/%E7%AC%AC%EF%BC%96%E7%AB%A0+%E6%A0%91%E4%B8%8E%E4%BA%8C%E5%8F%89%E6%A0%91+%E7%AC%AC%E4%BA%94%E8%8A%82+%E6%A0%91%E4%B8%8E%E6%A3%AE%E6%9E%97+%E4%B8%80%E3%80%81%E6%A0%91%E7%9A%84%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84+2.%E5%AD%A9%E5%AD%90%E8%A1%A8%E7%A4%BA%E6%B3%95%5B%E5%A4%9A%E9%87%8D%E9%93%BE%E8%A1%A8%5D+%E5%8F%AF%E4%BB%A5%E9%87%87%E7%94%A8%E5%A4%9A%E9%87%8D%E9%93%BE%E8%A1%A8%EF%BC%8C%E5%8D%B3%E6%AF%8F%E4%B8%AA%E7%BB%93%E7%82%B9%E6%9C%89%E5%A4%9A%E4%B8%AA%E6%8C%87%E9%92%88.jpg "第６章 树与二叉树. 第五节 树与森林. 一、树的存储结构. 2.孩子表示法[多重链表] 可以采用多重链表，即每个结点有多个指针. 最大缺点是空链域太多. [(d-1)n+1个] data. child1. child2. child3. childd. A. E. B. G. D. F. C. 43.")
44
第６章 树与二叉树 第五节 树与森林 一、树的存储结构 2.孩子表示法[单链表] 将每个结点的孩子排列起来，用单链表表示
第６章 树与二叉树 第五节 树与森林 一、树的存储结构 2.孩子表示法[单链表] 将每个结点的孩子排列起来，用单链表表示 将每个结点排列成一个线性表 Root 1 2 3 4 5 6 A B C D E F G 1 2 3 ^ A E B G D F C 4 5 ^ 6 ^ 44
![第６章 树与二叉树 第五节 树与森林 一、树的存储结构 2.孩子表示法[单链表] 将每个结点的孩子排列起来，用单链表表示](http://slidesplayer.com/slide/11606849/62/images/44/%E7%AC%AC%EF%BC%96%E7%AB%A0+%E6%A0%91%E4%B8%8E%E4%BA%8C%E5%8F%89%E6%A0%91+%E7%AC%AC%E4%BA%94%E8%8A%82+%E6%A0%91%E4%B8%8E%E6%A3%AE%E6%9E%97+%E4%B8%80%E3%80%81%E6%A0%91%E7%9A%84%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84+2.%E5%AD%A9%E5%AD%90%E8%A1%A8%E7%A4%BA%E6%B3%95%5B%E5%8D%95%E9%93%BE%E8%A1%A8%5D+%E5%B0%86%E6%AF%8F%E4%B8%AA%E7%BB%93%E7%82%B9%E7%9A%84%E5%AD%A9%E5%AD%90%E6%8E%92%E5%88%97%E8%B5%B7%E6%9D%A5%EF%BC%8C%E7%94%A8%E5%8D%95%E9%93%BE%E8%A1%A8%E8%A1%A8%E7%A4%BA.jpg "第６章 树与二叉树. 第五节 树与森林. 一、树的存储结构. 2.孩子表示法[单链表] 将每个结点的孩子排列起来，用单链表表示. 将每个结点排列成一个线性表. Root A. B. C. D. E. F. G ^ A. E. B. G. D. F. C ^ 6. ^ 44.")
45
第６章 树与二叉树 第五节 树与森林 一、树的存储结构 3.孩子兄弟表示法 采用二叉链表 左边指针指向第一个孩子，右边指针指向兄弟
第６章 树与二叉树 第五节 树与森林 一、树的存储结构 3.孩子兄弟表示法 采用二叉链表 左边指针指向第一个孩子，右边指针指向兄弟 data firstChild nextSibling B C D G F E A A E B G D F C 45
46
第６章 树与二叉树 第五节 树与森林 二、树与二叉树的对应关系 树与二叉树都可以采用二叉链表作存储结构
第６章 树与二叉树 第五节 树与森林 二、树与二叉树的对应关系 树与二叉树都可以采用二叉链表作存储结构 任意给定一棵树，可以找到一个唯一的二叉树(没有右子树) A B G D F C E A E B G D F C B C D G F E A 树 对应的二叉树 46
47
第６章 树与二叉树 第五节 树与森林 三、森林与二叉树的对应关系
第６章 树与二叉树 第五节 树与森林 三、森林与二叉树的对应关系 如果把森林中的第二棵树的根结点看作是第一棵树的根结点的兄弟，则可找到一个唯一的二叉树与之对应 A B C E D H I K F G J T T T3 A F H B C D G I J E K 三棵树的森林 对应的二叉树 47
48
第６章 树与二叉树 第五节 树与森林 四、树的遍历 对树的遍历主要有两种： 1. 先根（次序）遍历 2. 后根（次序）遍历 A E B G
第６章 树与二叉树 第五节 树与森林 四、树的遍历 对树的遍历主要有两种： 1. 先根（次序）遍历 2. 后根（次序）遍历 A E B G D F C 48
49
第６章 树与二叉树 第五节 树与森林 四、树的遍历 1. 先根（次序）遍历 当树非空时 访问根结点 依次先根遍历根的各棵子树
第６章 树与二叉树 第五节 树与森林 四、树的遍历 1. 先根（次序）遍历 当树非空时 访问根结点 依次先根遍历根的各棵子树 输出结果：ABEFCDG A E B G D F C 49
50
第６章 树与二叉树 第五节 树与森林 四、树的遍历 2. 后根（次序）遍历 当树非空时 依次后根遍历根的各棵子树 访问根结点
第６章 树与二叉树 第五节 树与森林 四、树的遍历 2. 后根（次序）遍历 当树非空时 依次后根遍历根的各棵子树 访问根结点 输出结果：EFBCGDA A E B G D F C 50
51
第６章 树与二叉树 第五节 树与森林 四、树的遍历 3. 与二叉树遍历的关系 当采用孩子兄弟表示法表示树时：
第６章 树与二叉树 第五节 树与森林 四、树的遍历 3. 与二叉树遍历的关系 当采用孩子兄弟表示法表示树时： 树的先根遍历，与树对应的二叉树的先根遍历完全相同 树的后根遍历，与树对应的二叉树的中根遍历完全相同 51
52
第６章 树与二叉树 第六节 赫夫曼树及其应用 一、最优二叉树 路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径
第６章 树与二叉树 第六节 赫夫曼树及其应用 一、最优二叉树 路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径 路径长度：路径上的分支数目 树的路径长度：从树根到 每个结点的路径长度之和 右树路径长度为： 2*1 + 3*2 + 1*3 = 11 A D B F C G E 52
53
第６章 树与二叉树 第六节 赫夫曼树及其应用 一、最优二叉树 带权路径长度：从结点到树根之间的路径长度与结点上权的乘积
第６章 树与二叉树 第六节 赫夫曼树及其应用 一、最优二叉树 带权路径长度：从结点到树根之间的路径长度与结点上权的乘积 树的带权路径长度(WPL)：树中所有叶子结点的带权路径长度之和 WPL = 2*5+3*3+2*4=27 A D B F C G E 5 ３ ４ 53
54
第６章 树与二叉树 第六节 赫夫曼树及其应用 一、最优二叉树
第６章 树与二叉树 第六节 赫夫曼树及其应用 一、最优二叉树 最优二叉树：假设二叉树有n个叶子，其每个叶子结点带权wi，则带权路径长度WPL最小的二叉树称为最优二叉树 赫夫曼(Huffman)树就是一棵最优二叉树 WPL = 1*5+2*3+2*4=19 A D B C E 5 ３ ４ 54
55
第６章 树与二叉树 第六节 赫夫曼树及其应用 二、Huffman树(构造) 在Huffman树中，权值最大的结点离根最近
第６章 树与二叉树 第六节 赫夫曼树及其应用 二、Huffman树(构造) 在Huffman树中，权值最大的结点离根最近 权值最小的结点离根最远 A D B C E 5 ３ ４ 55
56
第６章 树与二叉树 第六节 赫夫曼树及其应用 二、Huffman树(算法)
第６章 树与二叉树 第六节 赫夫曼树及其应用 二、Huffman树(算法) 1.根据给定的n个权值(w1, w2, …, wn)构成n棵二叉树的集合F={T1, T2, …, Tn}，其中每棵二叉树Ti中只有一个带树为Ti的根结点 2.在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置其根结点的权值为其左右子树权值之和 3.在F中删除这两棵树，同时将新得到的二叉树加入F中 4.重复2, 3，直到F只含一棵树为止 56
57
第６章 树与二叉树 第六节 赫夫曼树及其应用 二、Huffman树(举例) 57 F : {7} {5} {2} {4}
第６章 树与二叉树 第六节 赫夫曼树及其应用 二、Huffman树(举例) F : {7} {5} {2} {4} F : {7} {5} {6} F : {7} {11} 7 5 2 4 初始 合并{2} {4} 6 F : {18} 11 合并{5} {6} 合并{7} {11} 18 57
58
第６章 树与二叉树 第六节 赫夫曼树及其应用 三、Huffman编码
第６章 树与二叉树 第六节 赫夫曼树及其应用 三、Huffman编码 设给出一段报文：GOOD_GOOD_GOOD_GOOOOOOOO_OFF 字符集合是 { O, G, _, D, F}，各个字符出现的频度(次数)是 W＝{ 15, 4, 4, 3, 2}。 若给每个字符以等长编码 O: 000 G: 001 _: D: F: 100 则总编码长度为 ( ) * 3 = 84. 58
59
第６章 树与二叉树 第六节 赫夫曼树及其应用 三、Huffman编码 若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。
第６章 树与二叉树 第六节 赫夫曼树及其应用 三、Huffman编码 若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。 各字符{ O, G, _, D, F }出现概率为 { 15/28, 4/28, 4/28, 3/28, 2/28 },化整为 { 15, 4, 4, 3, 2 } 59
60
第６章 树与二叉树 第六节 赫夫曼树及其应用 三、Huffman编码 各字符出现概率[取整数]为{15, 4, 4, 3, 2}
第６章 树与二叉树 第六节 赫夫曼树及其应用 三、Huffman编码 各字符出现概率[取整数]为{15, 4, 4, 3, 2} 如果规定，Huffman树的左子树小于右子树，则可构成右图所示Huffman树 4 15 2 3 G _ F D O 60
![第６章 树与二叉树 第六节 赫夫曼树及其应用 三、Huffman编码 各字符出现概率[取整数]为{15, 4, 4, 3, 2}](http://slidesplayer.com/slide/11606849/62/images/60/%E7%AC%AC%EF%BC%96%E7%AB%A0+%E6%A0%91%E4%B8%8E%E4%BA%8C%E5%8F%89%E6%A0%91+%E7%AC%AC%E5%85%AD%E8%8A%82+%E8%B5%AB%E5%A4%AB%E6%9B%BC%E6%A0%91%E5%8F%8A%E5%85%B6%E5%BA%94%E7%94%A8+%E4%B8%89%E3%80%81Huffman%E7%BC%96%E7%A0%81+%E5%90%84%E5%AD%97%E7%AC%A6%E5%87%BA%E7%8E%B0%E6%A6%82%E7%8E%87%5B%E5%8F%96%E6%95%B4%E6%95%B0%5D%E4%B8%BA%7B15%2C+4%2C+4%2C+3%2C+2%7D.jpg "第６章 树与二叉树. 第六节 赫夫曼树及其应用. 三、Huffman编码. 各字符出现概率[取整数]为{15, 4, 4, 3, 2} 如果规定，Huffman树的左子树小于右子树，则可构成右图所示Huffman树 G. _. F. D. O. 60.")
61
第６章 树与二叉树 第六节 赫夫曼树及其应用 三、Huffman编码 令左孩子分支为编码‘0’，右孩子分支为编码‘1’
第６章 树与二叉树 第六节 赫夫曼树及其应用 三、Huffman编码 令左孩子分支为编码‘0’，右孩子分支为编码‘1’ 将根结点到叶子结点路径上的分支编码，组合起来，作为该字符的Huffman码，则可得到： O:1 _:011 G:010 D:001 F:000 4 15 2 3 1 G _ F D O 61
62
第６章 树与二叉树 第六节 赫夫曼树及其应用 三、Huffman编码 则总编码长度为
第６章 树与二叉树 第六节 赫夫曼树及其应用 三、Huffman编码 则总编码长度为 15*1+( )*3 = 54 < 84 Huffman是一种前缀编码，解码时不会混淆 如GOOD编码为： 4 15 2 3 1 G _ F D O 62
Similar presentations
