《数据结构第5章树和二叉树.ppt》由会员分享，可在线阅读，更多相关《数据结构第5章树和二叉树.ppt（166页珍藏版）》请在金锄头文库上搜索。
1、数据结构（数据结构（C版）版）清华大学出版社清华大学出版社树的逻辑结构树的逻辑结构树的存储结构树的存储结构二叉树的逻辑结构二叉树的逻辑结构二叉树的存储结构及实现二叉树的存储结构及实现树、森林与二叉树的转换树、森林与二叉树的转换哈夫曼树哈夫曼树第第 5 章章 树和二叉树树和二叉树本章的主要内容是本章的主要内容是数据结构（数据结构（C版）版）清华大学出版社清华大学出版社树的定义树的定义树：树：n（n0）个个结点结点的有限的有限集合集合。当。当n0时，称为时，称为空树；任意一棵非空树满足以下条件：空树；任意一棵非空树满足以下条件： 有且仅有一个特定的称为有且仅有一个特定的称为根根的结点；的结点； 当
2、当n1时时，除除根根结结点点之之外外的的其其余余结结点点被被分分成成m（m0）个个互互不不相相交交的的有有限限集集合合T1, ,T2, , , ,Tm，其其中每个集合又是一棵树，并称为这个根结点的中每个集合又是一棵树，并称为这个根结点的子树子树。5.1 树的逻辑结构树的逻辑结构树的定义是采用递归方法树的定义是采用递归方法数据结构（数据结构（C版）版）清华大学出版社清华大学出版社(a) 一棵树结构一棵树结构 (b)一个非树结构一个非树结构 (c)一个非树结构一个非树结构 5.1 树的逻辑结构树的逻辑结构树的定义树的定义ACBGFEDHIACBGFDACBGFDE数据结构（数据结构（C版）版）清华
3、大学出版社清华大学出版社树的应用举例树的应用举例文件结构文件结构5.1 树的逻辑结构树的逻辑结构My ComputerC:D:E:etcWINDOWSProgram FilesPictureMusic数据结构（数据结构（C版）版）清华大学出版社清华大学出版社树的基本术语树的基本术语结点的度：结点的度：结点所拥有的子树的个数。结点所拥有的子树的个数。树的度：树的度：树中各结点度的最大值。树中各结点度的最大值。5.1 树的逻辑结构树的逻辑结构CGBDEFKLHMIJA数据结构（数据结构（C版）版）清华大学出版社清华大学出版社5.1 树的逻辑结构树的逻辑结构叶子结点：叶子结点：度为度为0的结点，也称
4、为终端结点。的结点，也称为终端结点。分支结点：分支结点：度不为度不为0的结点，也称为非终端结点。的结点，也称为非终端结点。CGBDEFKLHMIJA树的基本术语树的基本术语数据结构（数据结构（C版）版）清华大学出版社清华大学出版社孩子、双亲：孩子、双亲：树中某结点子树的根结点称为这个结点树中某结点子树的根结点称为这个结点的的孩子结点孩子结点，这个结点称为它孩子结点的，这个结点称为它孩子结点的双亲结点双亲结点；兄弟：兄弟：具有同一个双亲的孩子结点互称为兄弟。具有同一个双亲的孩子结点互称为兄弟。 5.1 树的逻辑结构树的逻辑结构CGBDEFKLHMIJA树的基本术语树的基本术语数据结构（数据结构（
5、C版）版）清华大学出版社清华大学出版社路径：路径：如果树的结点序列如果树的结点序列n1, n2, , nk有如下关系：结有如下关系：结点点ni是是ni+1的双亲（的双亲（1=ik），则把，则把n1, n2, , nk称为称为一条由一条由n1至至nk的路径；路径上经过的边的个数称为的路径；路径上经过的边的个数称为路路径长度径长度。 CGBDEFKLHMIJA5.1 树的逻辑结构树的逻辑结构树的基本术语树的基本术语数据结构（数据结构（C版）版）清华大学出版社清华大学出版社祖先、子孙：祖先、子孙：在树中，如果有一条路径从结点在树中，如果有一条路径从结点x到结到结点点y，那么那么x就称为就称为y的祖先
6、，而的祖先，而y称为称为x的子孙。的子孙。5.1 树的逻辑结构树的逻辑结构CGBDEFKLHMIJA树的基本术语树的基本术语数据结构（数据结构（C版）版）清华大学出版社清华大学出版社结点所在层数：结点所在层数：根结点的层数为根结点的层数为1 1；对其余任何结点，；对其余任何结点，若某结点在第若某结点在第k k层，则其孩子结点在第层，则其孩子结点在第k+1k+1层。层。树的深度：树的深度：树中所有结点的最大层数，也称树中所有结点的最大层数，也称高度高度。1 1层层2层层4 4层层3层层高度高度4CGBDEFKLHMIJC5.1 树的逻辑结构树的逻辑结构树的基本术语树的基本术语数据结构（数据结构（
7、C版）版）清华大学出版社清华大学出版社CBDEFKLHJA71234568910层序编号：层序编号：将树中结点按照从上层到下层、同层从左将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从到右的次序依次给他们编以从1 1开始的连续自然数。开始的连续自然数。5.1 树的逻辑结构树的逻辑结构树的基本术语树的基本术语数据结构（数据结构（C版）版）清华大学出版社清华大学出版社有序树、无序树：有序树、无序树：如果一棵树中结点的各子树从左如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为到右是有次序的，称这棵树为有序树；反之，称为无序树。无序树。数据结构中讨论的一般都是有序
8、树数据结构中讨论的一般都是有序树 5.1 树的逻辑结构树的逻辑结构树的基本术语树的基本术语ACBGFEDACBGFED数据结构（数据结构（C版）版）清华大学出版社清华大学出版社CBDEFKLHJ森林：森林：m (m0)棵互不相交的树的集合。棵互不相交的树的集合。 5.1 树的逻辑结构树的逻辑结构树的基本术语树的基本术语A数据结构（数据结构（C版）版）清华大学出版社清华大学出版社同同构构：对对两两棵棵树树，若若通通过过对对结结点点适适当当地地重重命命名名，就就可可以以使使这这两两棵棵树树完完全全相相等等（结结点点对对应应相相等等，结结点对应关系也相等），则称这两棵树同构。点对应关系也相等），则称
9、这两棵树同构。5.1 树的逻辑结构树的逻辑结构树的基本术语树的基本术语ACBGFEDDAECFBG数据结构（数据结构（C版）版）清华大学出版社清华大学出版社树结构和线性结构的比较树结构和线性结构的比较线性结构线性结构线性结构线性结构树结构树结构树结构树结构第第一一个数据元素个数据元素根结点（只有根结点（只有一一个）个）无前驱无前驱无双亲无双亲最后最后一一个数据元素个数据元素叶子结点叶子结点(可以有可以有多多个个)无后继无后继无孩子无孩子其它数据元素其它数据元素其它结点其它结点一个前驱一个前驱,一个后一个后继继一个双亲一个双亲,多个孩子多个孩子一对一一对一一对一一对一 一对多一对多一对多一对多5
10、.1 树的逻辑结构树的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社树的抽象数据类型定义树的抽象数据类型定义ADT TreeData 树是由一个根结点和若干棵子树构成，树是由一个根结点和若干棵子树构成， 树中结点具有相同数据类型及层次关系树中结点具有相同数据类型及层次关系Operation InitTree 前置条件：树不存在前置条件：树不存在 输入：无输入：无 功能：初始化一棵树功能：初始化一棵树 输出：无输出：无 后置条件：构造一个空树后置条件：构造一个空树5.1 树的逻辑结构树的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 DestroyTree
11、 前置条件：树已存在前置条件：树已存在 输入：无输入：无 功能：销毁一棵树功能：销毁一棵树 输出：无输出：无 后置条件：释放该树占用的存储空间后置条件：释放该树占用的存储空间 Root 前置条件：树已存在前置条件：树已存在 输入：无输入：无 功能：求树的根结点功能：求树的根结点 输出：树的根结点的信息输出：树的根结点的信息 后置条件：树保持不变后置条件：树保持不变 树的抽象数据类型定义树的抽象数据类型定义5.1 树的逻辑结构树的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社Parent 前置条件：树已存在前置条件：树已存在 输入：结点输入：结点x 功能：求结点功能：求结点x
12、的双亲的双亲 输出：结点输出：结点x的双亲的信息的双亲的信息 后置条件：树保持不变后置条件：树保持不变 Depth 前置条件：树已存在前置条件：树已存在 输入：无输入：无 功能：求树的深度功能：求树的深度 输出：树的深度输出：树的深度 后置条件：树保持不变后置条件：树保持不变 树的抽象数据类型定义树的抽象数据类型定义5.1 树的逻辑结构树的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 PreOrder 前置条件：树已存在前置条件：树已存在 输入：无输入：无 功能：前序遍历树功能：前序遍历树 输出：树的前序遍历序列输出：树的前序遍历序列 后置条件：树保持不变后置条件：树保持
13、不变 PostOrder 前置条件：树已存在前置条件：树已存在 输入：无输入：无 功能：后序遍历树功能：后序遍历树 输出：树的后序遍历序列输出：树的后序遍历序列 后置条件：树保持不变后置条件：树保持不变endADT树的抽象数据类型定义树的抽象数据类型定义5.1 树的逻辑结构树的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社树的遍历操作树的遍历操作 树的遍历：树的遍历：从从根根结点出发，按照某种结点出发，按照某种次次序访问序访问树中所树中所有结点，使得每个结点被访问一次且仅被访问一次。有结点，使得每个结点被访问一次且仅被访问一次。 如何理解如何理解访问访问? ?抽象抽象操作，
14、操作，可以是对结点进行的各种处理，这里可以是对结点进行的各种处理，这里简简化为输出结点的数据。化为输出结点的数据。如何理解如何理解次序次序? ?树通常有前序（根）遍历、后序（根）遍历和层序树通常有前序（根）遍历、后序（根）遍历和层序（次）遍历三种方式。（次）遍历三种方式。5.1 树的逻辑结构树的逻辑结构树结构（非线性结构）树结构（非线性结构）线性结构。线性结构。遍历的实质遍历的实质? ?数据结构（数据结构（C版）版）清华大学出版社清华大学出版社前序遍历前序遍历 树的前序遍历操作定义为：树的前序遍历操作定义为：若若树树为为空空，则则空空操操作作返返回回；否则否则 访问根结点；访问根结点； 按照从
15、左到右的顺序前序按照从左到右的顺序前序遍历根结点的每一棵子树。遍历根结点的每一棵子树。 5.1 树的逻辑结构树的逻辑结构前序遍历序列：前序遍历序列：A B D E H I F C GACBGFEDHI数据结构（数据结构（C版）版）清华大学出版社清华大学出版社后序遍历后序遍历 树的后序遍历操作定义为：树的后序遍历操作定义为：若若树树为为空空，则则空空操操作作返返回回；否则否则 按按照照从从左左到到右右的的顺顺序序后后序序遍历根结点的每一棵子树；遍历根结点的每一棵子树； 访问根结点。访问根结点。 5.1 树的逻辑结构树的逻辑结构后序遍历序列：后序遍历序列：D H I E F B G C AACBG
16、FEDHI数据结构（数据结构（C版）版）清华大学出版社清华大学出版社层序遍历层序遍历 树的层序遍历操作定义为：树的层序遍历操作定义为：从从树树的的第第一一层层（即即根根结结点点）开开始始，自自上上而而下下逐逐层层遍遍历历，在在同同一一层层中中，按按从从左左到到右右的的顺序对结点逐个访问。顺序对结点逐个访问。 5.1 树的逻辑结构树的逻辑结构层序遍历序列：层序遍历序列：A B C D E F G H IACBGFEDHI数据结构（数据结构（C版）版）清华大学出版社清华大学出版社5.2 树的存储结构树的存储结构实现树的存储结构，关键是什么实现树的存储结构，关键是什么? ?什么是存储结构什么是存储结
17、构? ?树中结点之间的逻辑关系是什么树中结点之间的逻辑关系是什么? ?思考问题的出发点：如何表示结点的双亲和孩子思考问题的出发点：如何表示结点的双亲和孩子如何表示树中结点之间的逻辑关系。如何表示树中结点之间的逻辑关系。数据元素以及数据元素之间的数据元素以及数据元素之间的逻辑关系逻辑关系在存储器在存储器中的表示。中的表示。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社双亲表示法双亲表示法双亲表示法双亲表示法基本思想：基本思想：用一维数组来存储树的各个结点（一般用一维数组来存储树的各个结点（一般按按层序层序存储），数组中的一个元素对应树中的存储），数组中的一个元素对应树中的一个一个结点
18、，包括结点的数据信息以及该结点的双亲在数结点，包括结点的数据信息以及该结点的双亲在数组中的下标。组中的下标。 5.2 树的存储结构树的存储结构 data parentdata：存储树中结点的数据信息存储树中结点的数据信息parent：存储该结点的双亲在数组中的下标存储该结点的双亲在数组中的下标数据结构（数据结构（C版）版）清华大学出版社清华大学出版社template struct PNode T data; /数据域数据域 int parent; /指针域，双亲在数组中的下标指针域，双亲在数组中的下标 ; data parent5.2 树的存储结构树的存储结构树的双亲表示法实质上是一个静态链表
19、。树的双亲表示法实质上是一个静态链表。双亲表示法双亲表示法双亲表示法双亲表示法数据结构（数据结构（C版）版）清华大学出版社清华大学出版社下标下标 data parent012345678 A - -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 5.2 树的存储结构树的存储结构如何查找如何查找双亲双亲结点？时间性能？结点？时间性能？双亲表示法双亲表示法双亲表示法双亲表示法ACBHFEDGI数据结构（数据结构（C版）版）清华大学出版社清华大学出版社5.2 树的存储结构树的存储结构双亲表示法双亲表示法双亲表示法双亲表示法ACBHFEDGI如何查找如何查找孩子孩子结点？时间性能？
20、结点？时间性能？下标下标 data parentfirstchild 1 3 6 -1 8 -1-1-1-1012345678 A - -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社下标下标 data parent rightsib- -1 2- -1 4 5 - -17- -1- -15.2 树的存储结构树的存储结构双亲表示法双亲表示法双亲表示法双亲表示法012345678 A - -1 B 0 C 0 D 1 E 1 F 1 G 2 H 2 I 4 ACBHFEDGI如何查找如何查找兄弟兄弟结点？时间性能？结
21、点？时间性能？数据结构（数据结构（C版）版）清华大学出版社清华大学出版社链表中的每个结点包括一个数据域和多个指针域，链表中的每个结点包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。每个指针域指向该结点的一个孩子结点。 如何确定链表中的结点结构？如何确定链表中的结点结构？5.2 树的存储结构树的存储结构孩子链表表示法孩子链表表示法方案一：方案一：指针域的个数等于树的度指针域的个数等于树的度data child1 child2 childd其中：其中：data：数据域，存放该结点的数据信息；数据域，存放该结点的数据信息； child1childd：指针域，指向该结点的孩子。指针域，
22、指向该结点的孩子。 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社5.2 树的存储结构树的存储结构缺点：浪费空间缺点：浪费空间ACBHFEDGIABCDEFGHI 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社链表中的每个结点包括一个数据域和多个指针域，链表中的每个结点包括一个数据域和多个指针域，每个指针域指向该结点的一个孩子结点。每个指针域指向该结点的一个孩子结点。 如何确定链表中的结点结构？如何确定链表中的结点结构？5.2 树的存储结构树的存储结构孩子链表表示法孩子链表表示法方案二：方案二： 指针域的个数等于该结点的度指针域的个数等于该结点的度 data degre
23、e child1 child2 childd其中：其中：data：数据域，存放该结点的数据信息；数据域，存放该结点的数据信息； degree：度域，存放该结点的度；度域，存放该结点的度； child1childd：指针域，指向该结点的孩子。指针域，指向该结点的孩子。 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社5.2 树的存储结构树的存储结构缺点：结点结构不一致缺点：结点结构不一致ACBHFEDGIA 2B 3C 2E 1I 0G 0H 0F 0D 0数据结构（数据结构（C版）版）清华大学出版社清华大学出版社孩子链表表示法孩子链表表示法基本思想：基本思想：把每个结点的孩子排列把每
24、个结点的孩子排列起来，看成是一个起来，看成是一个线性表，且以单链表存储，线性表，且以单链表存储，则则n个结点共有个结点共有 n 个孩子个孩子链表链表。这。这 n 个单链表共有个单链表共有 n 个头指针，个头指针，这这 n 个头指个头指针又组成了一个线性表，针又组成了一个线性表，为了便于进行查找采用顺序为了便于进行查找采用顺序存储。最后，存储。最后，将存放将存放 n 个头指针的数组和存放个头指针的数组和存放n个结个结点的数组结合起来，构成孩子链表的点的数组结合起来，构成孩子链表的表头数组表头数组。 5.2 树的存储结构树的存储结构如何确定链表中的结点结构？如何确定链表中的结点结构？将结点的所有孩
25、子放在一起，构成线性表。将结点的所有孩子放在一起，构成线性表。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社child next孩子结点孩子结点struct CTNode int child; CTNode *next;5.2 树的存储结构树的存储结构template struct CBNode T data; CTNode *firstchild; ;孩子链表表示法孩子链表表示法data firstchild表头结点表头结点数据结构（数据结构（C版）版）清华大学出版社清华大学出版社ACBHFEDGI012345678下标下标 data firstchild A B C D E F
26、 G H I 5.2 树的存储结构树的存储结构如何查找如何查找孩子孩子结点？时间性能？结点？时间性能？12 345 7 68 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社ACBHFEDGI012345678下标下标 data firstchild A B C D E F G H I 5.2 树的存储结构树的存储结构12 345 7 68 如何查找如何查找双亲双亲结点？时间性能？结点？时间性能？数据结构（数据结构（C版）版）清华大学出版社清华大学出版社双亲孩子表示法双亲孩子表示法双亲孩子表示法双亲孩子表示法5.2 树的存储结构树的存储结构012345678 A - -1 B 0 C
27、 0 D 1 E 1 F 1 G 2 H 2 I 4 data parent firstchild12 345 7 68 ACBHFEDGI数据结构（数据结构（C版）版）清华大学出版社清华大学出版社孩子兄弟表示法孩子兄弟表示法孩子兄弟表示法孩子兄弟表示法5.2 树的存储结构树的存储结构ACBHFEDGI某结点的第一个孩子是惟一的某结点的第一个孩子是惟一的某结点的右兄弟是惟一的某结点的右兄弟是惟一的设置两个分别指向该结点的设置两个分别指向该结点的第一个孩子和右兄第一个孩子和右兄弟的指针弟的指针 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社template struct TNode
28、T data; TNode *firstchild, *rightsib;5.2 树的存储结构树的存储结构结点结构结点结构firstchild data rightsibdata：数据域，存储该结点的数据信息；数据域，存储该结点的数据信息；firstchild：指针域，指向该结点第一个孩子；指针域，指向该结点第一个孩子；rightsib：指针域，指向该结点的右兄弟结点。指针域，指向该结点的右兄弟结点。 孩子兄弟表示法孩子兄弟表示法孩子兄弟表示法孩子兄弟表示法数据结构（数据结构（C版）版）清华大学出版社清华大学出版社5.2 树的存储结构树的存储结构孩子兄弟表示法孩子兄弟表示法孩子兄弟表示法孩子兄
29、弟表示法ACBHFEDGI A B C D E F G H I如何查找如何查找兄弟兄弟结点？时间性能？结点？时间性能？数据结构（数据结构（C版）版）清华大学出版社清华大学出版社5.2 树的存储结构树的存储结构孩子兄弟表示法孩子兄弟表示法孩子兄弟表示法孩子兄弟表示法ACBHFEDGI A B C D E F G H I如何查找如何查找孩子孩子结点？时间性能？结点？时间性能？数据结构（数据结构（C版）版）清华大学出版社清华大学出版社二叉树的定义二叉树的定义二叉树的定义二叉树的定义 二叉树是二叉树是n（n0）个结点的有限集合，该集合或个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结
30、点者为空集（称为空二叉树），或者由一个根结点和两棵和两棵互不相交互不相交的、分别称为根结点的的、分别称为根结点的左子树左子树和和右子树右子树的二叉树组成。的二叉树组成。5.3 二叉树的逻辑结构二叉树的逻辑结构问题转化：将树转换为二叉树，从而利用二叉树解问题转化：将树转换为二叉树，从而利用二叉树解问题转化：将树转换为二叉树，从而利用二叉树解问题转化：将树转换为二叉树，从而利用二叉树解决树的有关问题。决树的有关问题。决树的有关问题。决树的有关问题。研究二叉树的意义？研究二叉树的意义？数据结构（数据结构（C版）版）清华大学出版社清华大学出版社二叉树的特点：二叉树的特点： 每个结点最多有两棵子树；每个
31、结点最多有两棵子树； 二叉树是有序的，其次序不二叉树是有序的，其次序不能任意颠倒能任意颠倒。 5.3 二叉树的逻辑结构二叉树的逻辑结构注意：二叉树和树是两种树结构。注意：二叉树和树是两种树结构。ABCDEFGABAB数据结构（数据结构（C版）版）清华大学出版社清华大学出版社二叉树的基本形态二叉树的基本形态空二叉树空二叉树只有一个根结点只有一个根结点左子树左子树根结点只有左子树根结点只有左子树右子树右子树根结点只有右子树根结点只有右子树左子树左子树右子树右子树根结点同时有左右子树根结点同时有左右子树5.3 二叉树的逻辑结构二叉树的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社
32、5.3 二叉树的逻辑结构二叉树的逻辑结构具有具有3 3个结点的树和具有个结点的树和具有3 3个结点的二叉树的形态个结点的二叉树的形态v二叉树和树是两种树结构。二叉树和树是两种树结构。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社特殊的二叉树特殊的二叉树斜树斜树1 . .所所有结点都只有左子有结点都只有左子树的二叉树称为树的二叉树称为左斜树左斜树；2 . .所有结点都只所有结点都只有右子有右子树的二叉树称为树的二叉树称为右斜树右斜树；3.3.左斜树和右斜树统称为左斜树和右斜树统称为斜树斜树。1. 在斜树中，每一层只有一个结点；在斜树中，每一层只有一个结点；2. .斜树的结点个数与其深
33、度相同。斜树的结点个数与其深度相同。 5.3 二叉树的逻辑结构二叉树的逻辑结构斜树的特点：斜树的特点：ABCABC数据结构（数据结构（C版）版）清华大学出版社清华大学出版社满二叉树满二叉树在一棵二叉树中，如果所在一棵二叉树中，如果所有分支结点都存在左子树有分支结点都存在左子树和右子树，并且所有叶子和右子树，并且所有叶子都在都在同一层上。同一层上。满二叉树的特点满二叉树的特点：1.叶子只能出现在最下一层；叶子只能出现在最下一层；2.只有度为只有度为0和度为和度为2的结点。的结点。5.3 二叉树的逻辑结构二叉树的逻辑结构特殊的二叉树特殊的二叉树A15234678910BCDEFGHIJKLM NO
34、1112 13 14 15数据结构（数据结构（C版）版）清华大学出版社清华大学出版社满二叉树满二叉树5.3 二叉树的逻辑结构二叉树的逻辑结构不是满二叉树，虽然不是满二叉树，虽然所有分支结点都有左所有分支结点都有左右子树，但叶子不在右子树，但叶子不在同一层上。同一层上。满二叉树在同样深度的二叉树中满二叉树在同样深度的二叉树中结点结点个数最多个数最多满二叉树在同样深度的二叉树中满二叉树在同样深度的二叉树中叶子结点叶子结点个数最多个数最多A1523467BCDEFGLM89特殊的二叉树特殊的二叉树数据结构（数据结构（C版）版）清华大学出版社清华大学出版社完全二叉树完全二叉树对一棵具有对一棵具有n个结
35、点的二个结点的二叉树按层序编号，如果编叉树按层序编号，如果编号为号为i（1in）的结点与的结点与同样深度的满二叉树中编同样深度的满二叉树中编号为号为i的结点在二叉树中的结点在二叉树中的位置完全相同。的位置完全相同。5.3 二叉树的逻辑结构二叉树的逻辑结构特殊的二叉树特殊的二叉树A15234678910BCDEFGHIJKLM NO1112 13 14 15A15234678910BCDEFGHIJ数据结构（数据结构（C版）版）清华大学出版社清华大学出版社在满二叉树中，从最后在满二叉树中，从最后一个结点开始，一个结点开始，连续连续去去掉掉任意任意个结点，即是一个结点，即是一棵完全二叉树。棵完全二
36、叉树。5.3 二叉树的逻辑结构二叉树的逻辑结构A1523467910BCDEFGHIJK11L12M13N14O158A15234678910BCDEFGHIJ不是完全二叉树，结点不是完全二叉树，结点10与满二叉树中的结点与满二叉树中的结点10不是同一个结点不是同一个结点特殊的二叉树特殊的二叉树数据结构（数据结构（C版）版）清华大学出版社清华大学出版社1. 叶子结点只能出现在最下叶子结点只能出现在最下两层，且最下层的叶子结点两层，且最下层的叶子结点都集中在二叉树的左部；都集中在二叉树的左部；2. 完全二叉树中如果有度为完全二叉树中如果有度为1的结点，只可能有一个，的结点，只可能有一个，且该结且
37、该结点只有左孩子。点只有左孩子。 3. 深度为深度为k的完全二叉树在的完全二叉树在k-1层上一定是满二叉树。层上一定是满二叉树。完全二叉树的特点完全二叉树的特点5.3 二叉树的逻辑结构二叉树的逻辑结构特殊的二叉树特殊的二叉树A15234678910BCDEFGHIJ数据结构（数据结构（C版）版）清华大学出版社清华大学出版社二叉树的基本性质二叉树的基本性质二叉树的基本性质二叉树的基本性质 性质性质5-1 二叉树的第二叉树的第i层上最多有层上最多有2i- -1个结点（个结点（i1）。）。 证明：证明：当当i=1时时，第，第1层只有一个根结点，而层只有一个根结点，而 2i-1=20 =1，结论显然成
38、立。结论显然成立。假定假定i=k（1ki）时结论成立，即第）时结论成立，即第k层上至多有层上至多有2k-1个结点，个结点， 则则 i=k+1时时，因为第，因为第k+1层上的结点是第层上的结点是第k层上结点的孩子，而二叉树中每个结点最多有层上结点的孩子，而二叉树中每个结点最多有2个个孩子，故在第孩子，故在第k+1层上最大结点个数为第层上最大结点个数为第k层上的最层上的最大结点个数的二倍，即大结点个数的二倍，即22k-12k。结论成立。结论成立。5.3 二叉树的逻辑结构二叉树的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社性质性质5-2 一棵深度为一棵深度为k的二叉树中，最多有
39、的二叉树中，最多有2k- -1个结个结点，最少有点，最少有k个结点。个结点。 证明：由性质证明：由性质1可知，深度为可知，深度为k的二叉树中结点个数最多的二叉树中结点个数最多= =2k-1；每一层至少要有一个结点，因此深度为每一层至少要有一个结点，因此深度为k的二叉树，的二叉树，至少有至少有k个结点。个结点。5.3 二叉树的逻辑结构二叉树的逻辑结构深度为深度为k且具有且具有2k-1个结点的二叉树个结点的二叉树一定是一定是满二叉树，满二叉树，深度为深度为k且具有且具有k个结点的二叉树个结点的二叉树不一定不一定是斜树。是斜树。二叉树的基本性质二叉树的基本性质二叉树的基本性质二叉树的基本性质 数据结
40、构（数据结构（C版）版）清华大学出版社清华大学出版社性质性质5-3 在一棵二叉树中，如果叶子结点数为在一棵二叉树中，如果叶子结点数为n0，度为度为2的结点数为的结点数为n2，则有则有: n0n21。 证明证明: 设设n为二叉树的结点总数，为二叉树的结点总数，n1为二叉树中度为二叉树中度为为1的结点数，则有：的结点数，则有： nn0n1n2 在二叉树中，在二叉树中，除了根结点外，其余结点都有唯一除了根结点外，其余结点都有唯一的的一个分枝进入，由于这些分枝是由度为一个分枝进入，由于这些分枝是由度为1和度为和度为2的的结点射出的，一个度为结点射出的，一个度为1的结点射出一个分枝，一的结点射出一个分枝
41、，一个度为个度为2的结点射出两个分枝，所以有：的结点射出两个分枝，所以有： nn12n21因此可以得到：因此可以得到：n0n21 。5.3 二叉树的逻辑结构二叉树的逻辑结构二叉树的基本性质二叉树的基本性质二叉树的基本性质二叉树的基本性质 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社5.3 二叉树的逻辑结构二叉树的逻辑结构在有在有n个结点的满二叉树中，有多少个叶子结点？个结点的满二叉树中，有多少个叶子结点？因为在满二叉树中没有度为因为在满二叉树中没有度为1的结点，只有度为的结点，只有度为0的的叶子结点和度为叶子结点和度为2的分支结点，所以，的分支结点，所以，n n0 + n2n0n
42、2 + 1 即叶子结点即叶子结点n0（n + 1）/2 二叉树的基本性质二叉树的基本性质二叉树的基本性质二叉树的基本性质 性质性质5-3 在一棵二叉树中，如果叶子结点数为在一棵二叉树中，如果叶子结点数为n0，度为度为2的结点数为的结点数为n2，则有则有: n0n21。 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社性质性质5-4 具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1。 5.3 二叉树的逻辑结构二叉树的逻辑结构证证明明：假假设设具具有有n个个结结点点的的完完全全二二叉叉树树的的深深度度为为k，根据完全二叉树的定义和性质根据完全二叉树的定义和
43、性质2，有下式成立，有下式成立 2k-1 n 2k 2k-1-12k-12k-1第第k-1层层第第k层层最少结点数最少结点数最多结点数最多结点数完全二叉树的基本性质完全二叉树的基本性质完全二叉树的基本性质完全二叉树的基本性质 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 5.3 二叉树的逻辑结构二叉树的逻辑结构log2n + 1log2nlog2nlog2n+1k所在区间所在区间证证明明：假假设设具具有有n个个结结点点的的完完全全二二叉叉树树的的深深度度为为k，根据完全二叉树的定义和性质根据完全二叉树的定义和性质2，有下式成立，有下式成立 2k-1 n 2k完全二叉树的基本性质完
44、全二叉树的基本性质完全二叉树的基本性质完全二叉树的基本性质 性质性质5-4 具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1。 对不等式取对数，有：对不等式取对数，有： k-1log2nk即：即： log2nklog2n+1由于由于k是整数，故必有是整数，故必有k log2n +1。 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社性质性质5-5 对一棵具有对一棵具有n个结点的完全二叉树中从个结点的完全二叉树中从1开开始按层序编号，则对于任意的序号为始按层序编号，则对于任意的序号为i（1in）的结的结点（简称为结点点（简称为结点i），），有：有： （1
45、）如果）如果i1，则结点则结点i的双亲结点的序号为的双亲结点的序号为 i/2；如果如果i1，则结点则结点i是根结点，无双亲结点。是根结点，无双亲结点。 (2)如果如果2in，则结点则结点i的左孩子的序号为的左孩子的序号为2i；如果如果2in，则结点则结点i无左孩子。无左孩子。 (3)如果如果2i1n，则结点则结点i的右孩子的序号为的右孩子的序号为2i1；如果如果2i1n，则结点则结点 i无右孩子。无右孩子。 5.3 二叉树的逻辑结构二叉树的逻辑结构完全二叉树的基本性质完全二叉树的基本性质完全二叉树的基本性质完全二叉树的基本性质 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社1891
46、0456723对一棵具有对一棵具有n个结点的完全个结点的完全二叉树中从二叉树中从1开始按层序编开始按层序编号，则号，则l 结点结点i的双亲结点为的双亲结点为 i/2；l 结点结点i的左孩子为的左孩子为2i；l 结点结点i的右孩子为的右孩子为2i1。 5.3 二叉树的逻辑结构二叉树的逻辑结构性质性质5表明，在完全二叉树中，结点的层序编号反映表明，在完全二叉树中，结点的层序编号反映了结点之间的逻辑关系。了结点之间的逻辑关系。完全二叉树的基本性质完全二叉树的基本性质完全二叉树的基本性质完全二叉树的基本性质 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社二叉树的抽象数据类型定义二叉树的抽象
47、数据类型定义二叉树的抽象数据类型定义二叉树的抽象数据类型定义ADT BiTreeData 由一个根结点和两棵互不相交的左右子树构成，由一个根结点和两棵互不相交的左右子树构成， 结点具有相同数据类型及层次关系结点具有相同数据类型及层次关系Operation InitBiTree 前置条件：无前置条件：无 输入：无输入：无 功能：初始化一棵二叉树功能：初始化一棵二叉树 输出：无输出：无 后置条件：构造一个空的二叉树后置条件：构造一个空的二叉树5.3 二叉树的逻辑结构二叉树的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 DestroyBiTree 前置条件：二叉树已存在前置条件
48、：二叉树已存在 输入：无输入：无 功能：销毁一棵二叉树功能：销毁一棵二叉树 输出：无输出：无 后置条件：释放二叉树占用的存储空间后置条件：释放二叉树占用的存储空间 InsertL 前置条件：二叉树已存在前置条件：二叉树已存在 输入：数据值输入：数据值x，指针，指针parent 功功能能：将将数数据据域域为为x的的结结点点插插入入到到二二叉叉树树中中，作作为为结结点点parent的的左左孩孩子子。如如果果结结点点parent原原来来有有左左孩孩子子，则将结点则将结点parent原来的左孩子作为结点原来的左孩子作为结点x的左孩子的左孩子 输出：无输出：无 后置条件：如果插入成功，得到一个新的二叉树
49、后置条件：如果插入成功，得到一个新的二叉树 二叉树的抽象数据类型定义二叉树的抽象数据类型定义二叉树的抽象数据类型定义二叉树的抽象数据类型定义5.3 二叉树的逻辑结构二叉树的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社DeleteL 前置条件：二叉树已存在前置条件：二叉树已存在 输入：指针输入：指针parent 功能：在二叉树中删除结点功能：在二叉树中删除结点parent的左子树的左子树 输出：无输出：无 后置条件：如果删除成功，得到一个新的二叉树后置条件：如果删除成功，得到一个新的二叉树Search 前置条件：二叉树已存在前置条件：二叉树已存在 输入：数据值输入：数据值x
50、 功能：在二叉树中查找数据元素功能：在二叉树中查找数据元素x 输出：指向该元素结点的指针输出：指向该元素结点的指针 后置条件：二叉树不变后置条件：二叉树不变 二叉树的抽象数据类型定义二叉树的抽象数据类型定义二叉树的抽象数据类型定义二叉树的抽象数据类型定义5.3 二叉树的逻辑结构二叉树的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 PreOrder 前置条件：二叉树已存在前置条件：二叉树已存在 输入：无输入：无 功能：前序遍历二叉树功能：前序遍历二叉树 输出：二叉树中结点的一个线性排列输出：二叉树中结点的一个线性排列 后置条件：二叉树不变后置条件：二叉树不变 InOrder
51、 前置条件：二叉树已存在前置条件：二叉树已存在 输入：无输入：无 功能：中序遍历二叉树功能：中序遍历二叉树 输出：二叉树中结点的一个线性排列输出：二叉树中结点的一个线性排列 后置条件：二叉树不变后置条件：二叉树不变 二叉树的抽象数据类型定义二叉树的抽象数据类型定义二叉树的抽象数据类型定义二叉树的抽象数据类型定义5.3 二叉树的逻辑结构二叉树的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 PostOrder 前置条件：二叉树已存在前置条件：二叉树已存在 输入：无输入：无 功能：后序遍历二叉树功能：后序遍历二叉树 输出：二叉树中结点的一个线性排列输出：二叉树中结点的一个线性排
52、列 后置条件：二叉树不变后置条件：二叉树不变 LeverOrder 前置条件：二叉树已存在前置条件：二叉树已存在 输入：无输入：无 功能：层序遍历二叉树功能：层序遍历二叉树 输出：二叉树中结点的一个线性排列输出：二叉树中结点的一个线性排列 后置条件：二叉树不变后置条件：二叉树不变 endADT二叉树的抽象数据类型定义二叉树的抽象数据类型定义二叉树的抽象数据类型定义二叉树的抽象数据类型定义5.3 二叉树的逻辑结构二叉树的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社二叉树的遍历操作二叉树的遍历操作二叉树的遍历操作二叉树的遍历操作 二叉树的遍历是指从根结点出发，按照某种二叉树的
53、遍历是指从根结点出发，按照某种次序次序访问二叉树中的所有结点，使得每个结点被访问一访问二叉树中的所有结点，使得每个结点被访问一次且仅被次且仅被访问访问一次。一次。二叉树遍历操作的结果？二叉树遍历操作的结果？非线性结构线性化非线性结构线性化5.3 二叉树的逻辑结构二叉树的逻辑结构抽象操作，抽象操作，可以是对结点进行的各种可以是对结点进行的各种处理，这里处理，这里简化为输出结点的数据。简化为输出结点的数据。前序遍历前序遍历中序遍历中序遍历后序遍历后序遍历层序遍历层序遍历 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社二叉树的遍历方式：二叉树的遍历方式：DLR、LDR、LRD、DRL、R
54、DL、RLD 如果限定先左后右，则二叉树遍历方式有三种：如果限定先左后右，则二叉树遍历方式有三种：前序前序：DLR中序中序：LDR后序后序：LRD层序遍历层序遍历：按二叉树的层序编号的次序访问各结点。：按二叉树的层序编号的次序访问各结点。 5.3 二叉树的逻辑结构二叉树的逻辑结构考虑二叉树的组成：考虑二叉树的组成：根结点根结点D左子树左子树L右子树右子树R二二叉叉树树数据结构（数据结构（C版）版）清华大学出版社清华大学出版社前序（根）遍历前序（根）遍历若若二二叉叉树树为为空空，则则空空操操作作返返回回；否则：否则：访问根结点；访问根结点；前序前序遍历遍历根根结点的左子树；结点的左子树；前序前序
55、遍历遍历根根结点的右子树。结点的右子树。5.3 二叉树的逻辑结构二叉树的逻辑结构前序遍历序列：前序遍历序列：A B D G C E FABCDEFG二叉树的遍历操作二叉树的遍历操作二叉树的遍历操作二叉树的遍历操作 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社中序（根）遍历中序（根）遍历若若二二叉叉树树为为空空，则则空空操操作作返返回回；否则：否则：中序中序遍历遍历根根结点的左子树；结点的左子树；访问根结点；访问根结点；中序中序遍历遍历根根结点的右子树。结点的右子树。 5.3 二叉树的逻辑结构二叉树的逻辑结构中序遍历序列：中序遍历序列：D G B A E C FABCDEFG二叉树
56、的遍历操作二叉树的遍历操作二叉树的遍历操作二叉树的遍历操作 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社后序（根）遍历后序（根）遍历若若二二叉叉树树为为空空，则则空空操操作作返返回回；否则：否则：后序后序遍历遍历根根结点的左子树；结点的左子树；后序后序遍历遍历根根结点的右子树。结点的右子树。访问根结点；访问根结点；5.3 二叉树的逻辑结构二叉树的逻辑结构后序遍历序列：后序遍历序列：G D B E F C AABCDEFG二叉树的遍历操作二叉树的遍历操作二叉树的遍历操作二叉树的遍历操作 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社层序遍历层序遍历二二叉叉树树的的层层次
57、次遍遍历历是是指指从从二二叉叉树树的的第第一一层层（即即根根结结点点）开开始始，从从上上至至下下逐逐层层遍遍历历，在在同同一一层层中中，则则按按从从左左到到右右的顺序对结点逐个访问。的顺序对结点逐个访问。 5.3 二叉树的逻辑结构二叉树的逻辑结构层序遍历序列：层序遍历序列：A B C D E F GABCDEFG二叉树的遍历操作二叉树的遍历操作二叉树的遍历操作二叉树的遍历操作 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社5.3 二叉树的逻辑结构二叉树的逻辑结构- - -/ /+ +* *abcdef二叉树遍历操作练习二叉树遍历操作练习前序遍历结果：前序遍历结果：- + a * b
58、 - c d / e f中序遍历结果：中序遍历结果：a + b * c - d - e / f后序遍历结果：后序遍历结果：a b c d - * + e f / -数据结构（数据结构（C版）版）清华大学出版社清华大学出版社5.3 二叉树的逻辑结构二叉树的逻辑结构若已知一棵二叉树的前序（或中序，或后序，或若已知一棵二叉树的前序（或中序，或后序，或层序）序列，能否唯一确定这棵二叉树呢？层序）序列，能否唯一确定这棵二叉树呢？ABC例：已知前序序列为例：已知前序序列为ABC，则可能的二叉树有，则可能的二叉树有5种。种。ABC二叉树的遍历操作二叉树的遍历操作二叉树的遍历操作二叉树的遍历操作 数据结构（数
59、据结构（C版）版）清华大学出版社清华大学出版社5.3 二叉树的逻辑结构二叉树的逻辑结构例：已知前序遍历序列为例：已知前序遍历序列为ABC，后序遍历序列为，后序遍历序列为CBA，则下列二叉树都满足条件。，则下列二叉树都满足条件。ABCABC若已知一棵二叉树的前序序列和后序序列，能否若已知一棵二叉树的前序序列和后序序列，能否唯一确定这棵二叉树呢？唯一确定这棵二叉树呢？二叉树的遍历操作二叉树的遍历操作二叉树的遍历操作二叉树的遍历操作 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社若已知一棵二叉树的前序序列和中序序列，能否若已知一棵二叉树的前序序列和中序序列，能否唯一确定这棵二叉树呢？怎样
60、确定？唯一确定这棵二叉树呢？怎样确定？ 例如：已知一棵二叉树的前序遍历序列和中序遍历例如：已知一棵二叉树的前序遍历序列和中序遍历序列分别为序列分别为ABCDEFGHI 和和BCAEDGHFI，如何构如何构造该二叉树呢造该二叉树呢? ? 5.3 二叉树的逻辑结构二叉树的逻辑结构二叉树的遍历操作二叉树的遍历操作二叉树的遍历操作二叉树的遍历操作 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社前序：前序：A B C D E F G H I中序：中序：B C A E D G H F I前序：前序：B C中序：中序：B C5.3 二叉树的逻辑结构二叉树的逻辑结构 B C D EF GH IA前
61、序：前序： D E F G H I中序：中序： E D G H F IABCDEFGHI数据结构（数据结构（C版）版）清华大学出版社清华大学出版社前序：前序：F G H I中序：中序：G H F I5.3 二叉树的逻辑结构二叉树的逻辑结构前序：前序： D E F G H I中序：中序： E D G H F IABCDEFGHIABCDEFIGH数据结构（数据结构（C版）版）清华大学出版社清华大学出版社1. 根据前序序列的第一个元素建立根结点；根据前序序列的第一个元素建立根结点；2. 在中序序列中找到该元素，确定根结点的左右子树在中序序列中找到该元素，确定根结点的左右子树的中序序列；的中序序列；
62、3. 在前序序列中确定左右子树的前序序列；在前序序列中确定左右子树的前序序列；4. 由左子树的前序序列和中序序列建立左子树；由左子树的前序序列和中序序列建立左子树；5. 由右子树的前序序列和中序序列建立右子树。由右子树的前序序列和中序序列建立右子树。 5.3 二叉树的逻辑结构二叉树的逻辑结构已知一棵二叉树的前序序列和中序序列，构造该已知一棵二叉树的前序序列和中序序列，构造该二叉树的过程如下：二叉树的过程如下： 二叉树的遍历操作二叉树的遍历操作二叉树的遍历操作二叉树的遍历操作 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社顺序存储结构顺序存储结构二叉树的顺序存储结构就是用一维数组存储
63、二叉树二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的中的结点，并且结点的存储位存储位置置（下标）应能体现（下标）应能体现结点之间的结点之间的逻辑关系逻辑关系父子关系。父子关系。 如何利用数组下标来反映结点之间的逻辑关系如何利用数组下标来反映结点之间的逻辑关系? ?完全二叉树完全二叉树和和满二叉树满二叉树中结点的序号可以唯一中结点的序号可以唯一地反映出结点之间的逻辑关系地反映出结点之间的逻辑关系 。5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 A B C D E F G H I J数组下标数组下标 1 2 3 4
64、 5 6 7 8 9 10完完全全二二叉叉树树的的顺顺序序存存储储5.4 二叉树的存储结构及实现二叉树的存储结构及实现A15234678910BCDEFGHIJ以编号以编号为下标为下标数据结构（数据结构（C版）版）清华大学出版社清华大学出版社二二叉叉树树的的顺顺序序存存储储ABC DE F G数组下标数组下标 1 2 3 4 5 6 7 8 9 10 11 12 135.4 二叉树的存储结构及实现二叉树的存储结构及实现ABCDFGE以编号以编号为下标为下标ABCDFGE123561013按照完全按照完全二叉树编号二叉树编号数据结构（数据结构（C版）版）清华大学出版社清华大学出版社一棵斜树的顺序
65、存储会怎样呢？一棵斜树的顺序存储会怎样呢？深度为深度为k的右斜树，的右斜树，k个结点需分配个结点需分配2k1个存储单元。个存储单元。 一棵二叉树改造后成完一棵二叉树改造后成完全二叉树形态，全二叉树形态，需增加需增加很多空结点很多空结点，造成存储，造成存储空间的浪费。空间的浪费。5.4 二叉树的存储结构及实现二叉树的存储结构及实现二叉树的顺序存储结构一般仅存储二叉树的顺序存储结构一般仅存储完全完全二叉树二叉树ABC137D15数据结构（数据结构（C版）版）清华大学出版社清华大学出版社二叉链表二叉链表基本思想：基本思想：令二叉树的每个结点对应一个链表结点，令二叉树的每个结点对应一个链表结点，链表结
66、点除了存放与二叉树结点有关的数据信链表结点除了存放与二叉树结点有关的数据信息外，息外，还要设置指示左右孩子的指针。还要设置指示左右孩子的指针。 结点结构：结点结构： lchild data rchild其中，其中，data：数据域，存放该结点的数据信息；数据域，存放该结点的数据信息； lchild：左指针域，存放指向左孩子的指针；左指针域，存放指向左孩子的指针； rchild：右指针域，存放指向右孩子的指针。右指针域，存放指向右孩子的指针。 5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（数据结构（C版）版）清华大学出版社清华大学出版社template struct BiNode
67、 T data; BiNode *lchild, *rchild;5.4 二叉树的存储结构及实现二叉树的存储结构及实现lchild data rchild左孩子结点左孩子结点右孩子结点右孩子结点二叉链表二叉链表数据结构（数据结构（C版）版）清华大学出版社清华大学出版社ABCDEFG二叉链表二叉链表5.4 二叉树的存储结构及实现二叉树的存储结构及实现具有具有n个结点的二叉链表中，有多少个空指针？个结点的二叉链表中，有多少个空指针？数据结构（数据结构（C版）版）清华大学出版社清华大学出版社ABCDEFG二叉链表二叉链表5.4 二叉树的存储结构及实现二叉树的存储结构及实现具有具有n个结点的二叉链表中
68、，有个结点的二叉链表中，有n+1个空指针。个空指针。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社二二叉叉链链表表存存储储结结构构的的类类声声明明template class BiTree public: BiTree( )( )root=NULL; BiTree( (BiNode *root) ); BiTree( )( ); void PreOrder( (BiNode *root) ); void InOrder( (BiNode *root) ); void PostOrder( (BiNode *root) ); void LeverOrder( (BiNode *roo
69、t) ); private: BiNode *root; void Creat( (BiNode *root) ); void Release( (BiNode *root) ); ;5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（数据结构（C版）版）清华大学出版社清华大学出版社前序遍历前序遍历递归算法递归算法template void BiTree:PreOrder( (BiNode *root) ) if ( (root =NULL) ) return; else cout-data; PreOrder( (root-lchild) ); PreOrder( (root-rc
70、hild) ); 5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（数据结构（C版）版）清华大学出版社清华大学出版社AGBCDFE5.4 二叉树的存储结构及实现二叉树的存储结构及实现前序遍历前序遍历算法的执行轨迹算法的执行轨迹数据结构（数据结构（C版）版）清华大学出版社清华大学出版社二叉树前序遍历的非递归算法的二叉树前序遍历的非递归算法的关键关键：在前序遍历过：在前序遍历过某结点的整个左子树后，如何找到该结点的某结点的整个左子树后，如何找到该结点的右子树右子树的的根指针。根指针。解决办法：解决办法：在访问完该结点后，将该结点的指针保存在访问完该结点后，将该结点的指针保存在在栈栈中，
71、以便以后能通过它找到该结点的右子树。中，以便以后能通过它找到该结点的右子树。 在在前前序序遍遍历历中中，设设要要遍遍历历二二叉叉树树的的根根指指针针为为root，则则有两种可能：有两种可能： 若若root!=NULL，则表明？如何处理？则表明？如何处理？ 若若root=NULL，则表明？如何处理？则表明？如何处理？5.4 二叉树的存储结构及实现二叉树的存储结构及实现前序遍历前序遍历非递归算法非递归算法数据结构（数据结构（C版）版）清华大学出版社清华大学出版社访问结点序列访问结点序列:A栈栈S内容内容:B D A B前序遍历的前序遍历的非递归非递归实现实现 5.4 二叉树的存储结构及实现二叉树的
72、存储结构及实现ADBC数据结构（数据结构（C版）版）清华大学出版社清华大学出版社访问结点序列访问结点序列:A栈栈S内容内容:B D A前序遍历的前序遍历的非递归非递归实现实现 5.4 二叉树的存储结构及实现二叉树的存储结构及实现ADBC D数据结构（数据结构（C版）版）清华大学出版社清华大学出版社访问结点序列访问结点序列:A栈栈S内容内容:B D C前序遍历的前序遍历的非递归非递归实现实现 5.4 二叉树的存储结构及实现二叉树的存储结构及实现ADBCC数据结构（数据结构（C版）版）清华大学出版社清华大学出版社1.栈栈s初始化；初始化；2.循环直到循环直到root为空且栈为空且栈s为空为空 2.
73、1 当当root不空时循环不空时循环2.1.1 输出输出root-data; 2.1.2 将指针将指针root的值保存到栈中；的值保存到栈中； 2.1.3 继续遍历继续遍历root的左子树的左子树2.2 如果栈如果栈s不空，则不空，则2.2.1 将栈顶元素弹出至将栈顶元素弹出至root；2.2.2 准备遍历准备遍历root的右子树；的右子树； 前序遍历前序遍历非递归算法（伪代码）非递归算法（伪代码）5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（数据结构（C版）版）清华大学出版社清华大学出版社前序遍历前序遍历非递归算法（伪代码）非递归算法（伪代码）5.4 二叉树的存储结构及实现二
74、叉树的存储结构及实现template void BiTree:PreOrder(BiNode *root) top= -1; /采用顺序栈，并假定不会发生上溢采用顺序栈，并假定不会发生上溢 while (root!=NULL | | top!= -1) while (root!= NULL) coutdata; s+top=root; root=root-lchild; if (top!= -1) root=stop-; root=root-rchild; 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社中序遍历中序遍历递归算法递归算法 template void BiTree:In
75、Order ( (BiNode *root) ) if ( (root=NULL) ) return; else InOrder( (root-lchild) ); cout-data; InOrder( (root-rchild) ); 5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（数据结构（C版）版）清华大学出版社清华大学出版社后序遍历后序遍历递归算法递归算法template void BiTree:PostOrder( (BiNode *root) ) if ( (root=NULL) ) return; else PostOrder( (root-lchild) );
76、PostOrder( (root-rchild) ); cout-data; 5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（数据结构（C版）版）清华大学出版社清华大学出版社层序遍历层序遍历5.4 二叉树的存储结构及实现二叉树的存储结构及实现ABCDEFG遍历序列：遍历序列：AAB CBDCE F GD E F G数据结构（数据结构（C版）版）清华大学出版社清华大学出版社层序遍历层序遍历1.队列队列Q初始化；初始化；2. 如果二叉树非空，将根指针入队；如果二叉树非空，将根指针入队；3. 循环直到队列循环直到队列Q为空为空 3.1 q=队列队列Q的队头元素出队；的队头元素出队； 3
77、.2 访问结点访问结点q的数据域；的数据域； 3.3 若结点若结点q存在左孩子，则将左孩子指针入队；存在左孩子，则将左孩子指针入队； 3.4 若结点若结点q存在右孩子，则将右孩子指针入队；存在右孩子，则将右孩子指针入队；5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（数据结构（C版）版）清华大学出版社清华大学出版社二叉树的建立二叉树的建立为为了了建建立立一一棵棵二二叉叉树树，将将二二叉叉树树中中每每个个结结点点的的空空指指针针引引出出一一个个虚虚结结点点，其其值值为为一一特特定定值值如如“#”，以以标标识识其其为为空空，把把这这样样处处理理后后的的二二叉叉树树称称为为原原二二叉叉
78、树树的扩展的扩展二叉树。二叉树。 为什么如此处理为什么如此处理? ?5.4 二叉树的存储结构及实现二叉树的存储结构及实现如何由一种遍历序列生成该二叉树？如何由一种遍历序列生成该二叉树？遍遍历历是是二二叉叉树树各各种种操操作作的的基基础础，可可以以在在遍遍历历的的过过程程中进行各种操作，例如建立一棵二叉树。中进行各种操作，例如建立一棵二叉树。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社扩展二叉树的前序遍历序列扩展二叉树的前序遍历序列:A B # D # # C # #5.4 二叉树的存储结构及实现二叉树的存储结构及实现DBAC#DBAC#二叉树的建立二叉树的建立数据结构（数据结构（
79、C版）版）清华大学出版社清华大学出版社设设二二叉叉树树中中的的结结点点均均为为一一个个字字符符。假假设设扩扩展展二二叉叉树树的的前前序序遍遍历历序序列列由由键键盘盘输输入入，root为为指指向向根根结结点点的的指指针针，二叉链表的建立过程是：二叉链表的建立过程是：首首先先输输入入根根结结点点，若若输输入入的的是是一一个个“#”字字符符，则则表表明明该该二二叉叉树树为为空空树树，即即root=NULL；否否则则输输入入的的字字符符应应该该赋赋给给root-data,，之之后后依依次次递递归归建建立立它它的的左左子子树树和右子树和右子树 。5.4 二叉树的存储结构及实现二叉树的存储结构及实现二叉树
80、的建立二叉树的建立数据结构（数据结构（C版）版）清华大学出版社清华大学出版社template BiTree :BiTree( (BiNode *root) ) creat( (root) )；void BiTree :Creat( (BiNode *root) ) cinch; if ( (ch=# ) ) root=NULL; else root=new BiNode; root-data=ch; creat( (root-lchild) ); creat( (root-rchild) ); 建建立立二二叉叉递递归归算算法法5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（数据结
81、构（C版）版）清华大学出版社清华大学出版社二叉树算法设计练习二叉树算法设计练习 遍历二叉树是二叉树各种操作的基础，遍历算法遍历二叉树是二叉树各种操作的基础，遍历算法中对每个结点的访问操作可以是多种形式及多个操中对每个结点的访问操作可以是多种形式及多个操作，根据遍历算法的框架，适当修改访问操作的内作，根据遍历算法的框架，适当修改访问操作的内容，可以派生出很多关于二叉树的应用算法。容，可以派生出很多关于二叉树的应用算法。 void InOrder ( (BiNode *root) ) if ( (root=NULL) ) return; else InOrder( (root-lchild) );
82、 cout-data; InOrder( (root-rchild) ); 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社二叉树算法设计练习二叉树算法设计练习设计算法求二叉树的结点个数。设计算法求二叉树的结点个数。 void Count(BiNode *root) /n为全局量并已初始化为为全局量并已初始化为0 if (root) Count(root-lchild); n+ +; Count(root-rchild); 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社二叉树算法设计练习二叉树算法设计练习设计算法按前序次序打印二叉树中的叶子结点。设计算法按前序次序打印二叉
83、树中的叶子结点。 void PreOrder(BiNode *root) if (root) if (!root-lchild & !root-rchild) coutdata; PreOrder(root-lchild); PreOrder(root-rchild); 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社二叉树算法设计练习二叉树算法设计练习设计算法求二叉树的深度。设计算法求二叉树的深度。 int Depth(BiNode *root) if (root= =NULL) return 0; else hl= Depth(root-lchild); hr= Depth(ro
84、ot -rchild); return max(hl, hr)+1; 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社二叉树算法设计练习二叉树算法设计练习设计算法求树中结点设计算法求树中结点 x 的第的第 i 个孩子。个孩子。 template TNode *Search(TNode *root, T x, int i) if (root-data= =x) j=1; p=root-firstchild; while (p!=NULL & jrightsib; if (p) return p; else return NULL; Search(root-firstchild, x,
85、i); Search(root-rightsib, x, i);template struct TNode T data; TNode *firstchild, *rightsib; 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社三叉链表三叉链表5.4 二叉树的存储结构及实现二叉树的存储结构及实现ABCDEFG在二叉链表中，如何求某结点的双亲？在二叉链表中，如何求某结点的双亲？数据结构（数据结构（C版）版）清华大学出版社清华大学出版社三叉链表三叉链表 lchild dataparent rchild在二叉链表的基础上增加了一个指向双亲的指针域。在二叉链表的基础上增加了一个指向双亲的
86、指针域。结点结构结点结构其中：其中：data、lchild和和rchild三个域的含义同二三个域的含义同二叉链表的结点结构；叉链表的结点结构；parent域为域为指向该结点的双亲结点的指针。指向该结点的双亲结点的指针。 5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（数据结构（C版）版）清华大学出版社清华大学出版社ABCDEFG三叉链表三叉链表5.4 二叉树的存储结构及实现二叉树的存储结构及实现数据结构（数据结构（C版）版）清华大学出版社清华大学出版社ABCDEFG三叉链表的静态链表形式三叉链表的静态链表形式5.4 二叉树的存储结构及实现二叉树的存储结构及实现0123456dat
87、a parent lchild rchildABCDEFG-1 0 0 1 2 2 3 1 3 4-1-1-1-1 2-1 5 6-1-1-1数据结构（数据结构（C版）版）清华大学出版社清华大学出版社线索链表线索链表5.4 二叉树的存储结构及实现二叉树的存储结构及实现如何保存二叉树的某种遍历序列？如何保存二叉树的某种遍历序列？ABCDEFG中序遍历序列：中序遍历序列：D G B A F C F如果二叉树如果二叉树不不改变，如何保存？改变，如何保存？顺序顺序存储存储D G B A F C F数据结构（数据结构（C版）版）清华大学出版社清华大学出版社线索链表线索链表5.4 二叉树的存储结构及实现二
88、叉树的存储结构及实现如何保存二叉树的某种遍历序列？如何保存二叉树的某种遍历序列？ABCDEFG中序遍历序列：中序遍历序列：D G B A F C F如果二叉树改变，如何保存？如果二叉树改变，如何保存？链接链接存储存储 D F 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社线索链表线索链表5.4 二叉树的存储结构及实现二叉树的存储结构及实现如何保存二叉树的某种遍历序列？如何保存二叉树的某种遍历序列？ABCDEFG中序遍历序列：中序遍历序列：D G B A F C F如何将二叉链表与中序链表结合？如何将二叉链表与中序链表结合？链接链接存储存储 D F 数据结构（数据结构（C版）版）清华
89、大学出版社清华大学出版社线索链表线索链表线索：线索：将二叉链表中的空指针域指向前驱结点和后继将二叉链表中的空指针域指向前驱结点和后继结点的指针被称为线索；结点的指针被称为线索；线索化：线索化：使二叉链表中结点的空链域存放其前驱或后使二叉链表中结点的空链域存放其前驱或后继信息的过程称为线索化；继信息的过程称为线索化；线索二叉树：线索二叉树：加上线索的二叉树称为线索二叉树。加上线索的二叉树称为线索二叉树。5.4 二叉树的存储结构及实现二叉树的存储结构及实现如何保存二叉树的某种遍历序列？如何保存二叉树的某种遍历序列？将二叉链表中的空指针域指向其前驱结点和后继结点将二叉链表中的空指针域指向其前驱结点和
90、后继结点数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 ltag lchild data child rtag0: lchild指向该结点的左孩子指向该结点的左孩子1: lchild指向该结点的前驱结点指向该结点的前驱结点0: rchild指向该结点的右孩子指向该结点的右孩子1: rchild指向该结点的后继结点指向该结点的后继结点ltag=rtag=5.4 二叉树的存储结构及实现二叉树的存储结构及实现结点结构结点结构线索链表线索链表数据结构（数据结构（C版）版）清华大学出版社清华大学出版社enum flag Child, Thread; template struct ThrNo
91、de T data; ThrNode *lchild, *rchild; flag ltag, rtag;5.4 二叉树的存储结构及实现二叉树的存储结构及实现线索链表线索链表 ltag lchild data child rtag结点结构结点结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社二叉树的遍历方式有二叉树的遍历方式有4种，故有种，故有4种意义下的前驱和后种意义下的前驱和后继，相应的有继，相应的有4种线索二叉树：种线索二叉树： 前序线索二叉树前序线索二叉树 中序线索二叉树中序线索二叉树 后序线索二叉树后序线索二叉树 层序线索二叉树层序线索二叉树5.4 二叉树的存储结构及实现
92、二叉树的存储结构及实现线索二叉树线索二叉树数据结构（数据结构（C版）版）清华大学出版社清华大学出版社FABDCEG中序线索二叉树中序线索二叉树5.4 二叉树的存储结构及实现二叉树的存储结构及实现线索二叉树线索二叉树中序序列：中序序列：D G B A E C F数据结构（数据结构（C版）版）清华大学出版社清华大学出版社template class InThrBiTree public: InThrBiTree( (ThrNode * root) ); InThrBiTree( )( ); ThrNode *Next( (ThrNode *p) ); void InOrder( (ThrNode
93、*root) ); private: ThrNode *root; void Creat( (ThrNode *root) ); void ThrBiTree( (ThrNode *root) );5.4 二叉树的存储结构及实现二叉树的存储结构及实现中中序序线线索索链链表表类类的的声声明明数据结构（数据结构（C版）版）清华大学出版社清华大学出版社分析：分析：建立线索链表，实质上就是将二叉链表中的空建立线索链表，实质上就是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历该二叉树时才能得到。息只有在遍历该二叉树时才能得到。5.
94、4 二叉树的存储结构及实现二叉树的存储结构及实现建立二叉链表建立二叉链表遍历二叉树，将遍历二叉树，将空指针改为线索空指针改为线索中序线索链表的建立中序线索链表的建立构造函数构造函数数据结构（数据结构（C版）版）清华大学出版社清华大学出版社头指针头指针00000000000000中序线索链表中序线索链表的建立过程的建立过程5.4 二叉树的存储结构及实现二叉树的存储结构及实现已经建立起二叉链表已经建立起二叉链表数据结构（数据结构（C版）版）清华大学出版社清华大学出版社头指针头指针00000000000000中序线索链表中序线索链表的建立过程的建立过程5.4 二叉树的存储结构及实现二叉树的存储结构及
95、实现中序遍历二叉链表中序遍历二叉链表p为正在访问的结点为正在访问的结点pre为刚访问的结点为刚访问的结点p1数据结构（数据结构（C版）版）清华大学出版社清华大学出版社头指针头指针00000000000000中序线索链表中序线索链表的建立过程的建立过程5.4 二叉树的存储结构及实现二叉树的存储结构及实现中序遍历二叉链表中序遍历二叉链表p为正在访问的结点为正在访问的结点pre为刚访问的结点为刚访问的结点pre1p1数据结构（数据结构（C版）版）清华大学出版社清华大学出版社头指针头指针00000000000000中序线索链表中序线索链表的建立过程的建立过程5.4 二叉树的存储结构及实现二叉树的存储结
96、构及实现中序遍历二叉链表中序遍历二叉链表p为正在访问的结点为正在访问的结点pre为刚访问的结点为刚访问的结点pre11p1数据结构（数据结构（C版）版）清华大学出版社清华大学出版社头指针头指针00000000000000中序线索链表中序线索链表的建立过程的建立过程5.4 二叉树的存储结构及实现二叉树的存储结构及实现中序遍历二叉链表中序遍历二叉链表p为正在访问的结点为正在访问的结点pre为刚访问的结点为刚访问的结点pre11p11数据结构（数据结构（C版）版）清华大学出版社清华大学出版社头指针头指针00000000000000中序线索链表中序线索链表的建立过程的建立过程5.4 二叉树的存储结构及
97、实现二叉树的存储结构及实现中序遍历二叉链表中序遍历二叉链表p为正在访问的结点为正在访问的结点pre为刚访问的结点为刚访问的结点pre11p111数据结构（数据结构（C版）版）清华大学出版社清华大学出版社头指针头指针00000000000000中序线索链表中序线索链表的建立过程的建立过程5.4 二叉树的存储结构及实现二叉树的存储结构及实现中序遍历二叉链表中序遍历二叉链表p为正在访问的结点为正在访问的结点pre为刚访问的结点为刚访问的结点pre11p1111数据结构（数据结构（C版）版）清华大学出版社清华大学出版社头指针头指针00000000000000中序线索链表中序线索链表的建立过程的建立过程
98、5.4 二叉树的存储结构及实现二叉树的存储结构及实现中序遍历二叉链表中序遍历二叉链表p为正在访问的结点为正在访问的结点pre为刚访问的结点为刚访问的结点pre11p11111数据结构（数据结构（C版）版）清华大学出版社清华大学出版社头指针头指针00000000000000中序线索链表中序线索链表的建立过程的建立过程5.4 二叉树的存储结构及实现二叉树的存储结构及实现中序遍历二叉链表中序遍历二叉链表p为正在访问的结点为正在访问的结点pre为刚访问的结点为刚访问的结点pre11111111数据结构（数据结构（C版）版）清华大学出版社清华大学出版社在遍历过程中，访问当前结点在遍历过程中，访问当前结点
99、root的操作为：的操作为：如果如果root的左、右指针域为空，则将相应标志置的左、右指针域为空，则将相应标志置1；若若root的的左左指指针针域域为为空空，则则令令其其指指向向它它的的前前驱驱，这这需需要要设设指指针针pre始始终终指指向向刚刚刚刚访访问问过过的的结结点点，显显然然pre的的初初值值为为NULL；若若pre的的右右指指针针域域为为空空，则则令令其其指指向向它的后继，即当前访问的结点它的后继，即当前访问的结点root; 令令pre指向刚刚访问过的结点指向刚刚访问过的结点root；5.4 二叉树的存储结构及实现二叉树的存储结构及实现中序线索链表的建立中序线索链表的建立数据结构（数
100、据结构（C版）版）清华大学出版社清华大学出版社1. 建立二叉链表，将每个结点的左右标志置为建立二叉链表，将每个结点的左右标志置为0；2. 遍历二叉链表，建立线索；遍历二叉链表，建立线索； 2.1 如果二叉链表如果二叉链表root为空，则空操作返回；为空，则空操作返回； 2.2 对对root的左子树建立线索；的左子树建立线索； 2.3 对根结点对根结点root建立线索；建立线索； 2.3.1 若若root没有左孩子，则为没有左孩子，则为root加上前驱线索加上前驱线索; 2.3.2 若若root没有右孩子没有右孩子，则将则将root右标志置为右标志置为1； 2.3.3 若结点若结点pre右标志为
101、右标志为1，则为，则为pre加上后继线索；加上后继线索； 2.3.4 令令pre指向刚刚访问的结点指向刚刚访问的结点root； 2.4 对对root的右子树建立线索。的右子树建立线索。5.4 二叉树的存储结构及实现二叉树的存储结构及实现中序线索链表的建立中序线索链表的建立构造函数构造函数数据结构（数据结构（C版）版）清华大学出版社清华大学出版社5.5 树、森林与二叉树的转换树、森林与二叉树的转换是哪些树结构的是哪些树结构的存储结构存储结构? ?树和二叉树之间具有对应关系树和二叉树之间具有对应关系AEBCFDGA BCED F GABCDEFG数据结构（数据结构（C版）版）清华大学出版社清华大学
102、出版社5.5 树、森林与二叉树的转换树、森林与二叉树的转换树和二叉树之间的对应关系树和二叉树之间的对应关系 树：兄弟关系树：兄弟关系二叉树：双亲和右孩子二叉树：双亲和右孩子 树：双亲和长子树：双亲和长子二叉树：双亲和左孩子二叉树：双亲和左孩子AEBCFDGABCDEFG数据结构（数据结构（C版）版）清华大学出版社清华大学出版社5.5 树、森林与二叉树的转换树、森林与二叉树的转换 1.兄兄弟弟加加线线.树和二叉树之间的对应关系树和二叉树之间的对应关系ABCDEFG数据结构（数据结构（C版）版）清华大学出版社清华大学出版社5.5 树、森林与二叉树的转换树、森林与二叉树的转换2.保保留留双双亲亲与与
103、第第一一孩孩子子连连线线,删删去去与与其他孩子的连线其他孩子的连线.ABCDEFG树和二叉树之间的对应关系树和二叉树之间的对应关系 1.兄兄弟弟加加线线.数据结构（数据结构（C版）版）清华大学出版社清华大学出版社3.顺顺时时针针转转动动,使使之之层次分明层次分明.5.5 树、森林与二叉树的转换树、森林与二叉树的转换树和二叉树之间的对应关系树和二叉树之间的对应关系2.保保留留双双亲亲与与第第一一孩孩子子连连线线,删删去去与与其他孩子的连线其他孩子的连线. 1.兄兄弟弟加加线线.ABCDEFG数据结构（数据结构（C版）版）清华大学出版社清华大学出版社3.顺顺时时针针转转动动,使使之之层次分明层次分
104、明.5.5 树、森林与二叉树的转换树、森林与二叉树的转换树和二叉树之间的对应关系树和二叉树之间的对应关系2.保保留留双双亲亲与与第第一一孩孩子子连连线线,删删去去与与其他孩子的连线其他孩子的连线. 1.兄兄弟弟加加线线.GDABECF数据结构（数据结构（C版）版）清华大学出版社清华大学出版社树转换为二叉树树转换为二叉树 加线加线树中所有相邻兄弟之间加一条连线。树中所有相邻兄弟之间加一条连线。 去线去线对树中的每个结点，只保留它与第一个对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间孩子结点之间的连线，删去它与其它孩子结点之间的连线。的连线。 层次调整层次调整以根结
105、点为轴心，将树顺时针转动以根结点为轴心，将树顺时针转动一定的角度，使之层次分明。一定的角度，使之层次分明。 5.5 树、森林与二叉树的转换树、森林与二叉树的转换数据结构（数据结构（C版）版）清华大学出版社清华大学出版社CBEDFGAABEFCDG前序遍历前序遍历AEBCFDGABEFCDG前序遍历前序遍历树树的的前前序序遍遍历历等等价价于于二叉树的前序遍历！二叉树的前序遍历！5.5 树、森林与二叉树的转换树、森林与二叉树的转换数据结构（数据结构（C版）版）清华大学出版社清华大学出版社EFBCGDA后序遍历后序遍历EFBCGDA中序遍历中序遍历树树的的后后序序遍遍历历等等价价于于二叉树的中序遍历
106、！二叉树的中序遍历！5.5 树、森林与二叉树的转换树、森林与二叉树的转换CBEDFGAAEBCFDG数据结构（数据结构（C版）版）清华大学出版社清华大学出版社森林转换为二叉树森林转换为二叉树 将森林中的每棵树转换成二叉树；将森林中的每棵树转换成二叉树； 从第二棵二叉树开始，依次把后一棵二叉树的根从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点结点作为前一棵二叉树根结点的右孩子，当所有二的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树换得到的二叉树。5.5 树、森林与二叉树的转换树、森林与二叉树的转换数据
107、结构（数据结构（C版）版）清华大学出版社清华大学出版社FEDCBAGHIJBAFEDCGHIKKIFEHABCGD5.5 树、森林与二叉树的转换树、森林与二叉树的转换数据结构（数据结构（C版）版）清华大学出版社清华大学出版社二叉树转换为树或森林二叉树转换为树或森林 加线加线若某结点若某结点x是其双亲是其双亲y的左孩子，则把结点的左孩子，则把结点x的右孩子、右孩子的右孩子、的右孩子、右孩子的右孩子、，都与结点，都与结点y用线连用线连起来；起来； 去去线线删删去去原原二二叉叉树树中中所所有有的的双双亲亲结结点点与与右右孩孩子子结结点的连线；点的连线； 层次调整层次调整整理由整理由、两步所得到的树或
108、森林，两步所得到的树或森林，使之层次分明。使之层次分明。 5.5 树、森林与二叉树的转换树、森林与二叉树的转换数据结构（数据结构（C版）版）清华大学出版社清华大学出版社FHGEAICDBFHGDCEBAIFEDCBAHGI加线加线去线去线层次调整层次调整IHGBCDAFE5.5 树、森林与二叉树的转换树、森林与二叉树的转换数据结构（数据结构（C版）版）清华大学出版社清华大学出版社森林的遍历森林的遍历森林有两种遍历方法：森林有两种遍历方法：前序（根）遍历：前序遍历森林即为前序遍历森前序（根）遍历：前序遍历森林即为前序遍历森林中的每一棵树。林中的每一棵树。 后序（根）遍历：后序遍历森林即为后序遍历
109、森后序（根）遍历：后序遍历森林即为后序遍历森林中的每一棵树。林中的每一棵树。 5.5 树、森林与二叉树的转换树、森林与二叉树的转换数据结构（数据结构（C版）版）清华大学出版社清华大学出版社相关概念相关概念叶子结点的权值：叶子结点的权值：对叶子结点赋予的一个有意义的数对叶子结点赋予的一个有意义的数值量。值量。 二叉树的带权路径长度：二叉树的带权路径长度：设二叉树具有设二叉树具有n个带权值的个带权值的叶子结点，从根结点到各个叶子结点的路径长度与叶子结点，从根结点到各个叶子结点的路径长度与相相应叶子结点权值的乘积之和。应叶子结点权值的乘积之和。 记为：记为：WPL=5.6 哈夫曼树及哈夫曼编码哈夫曼
110、树及哈夫曼编码 = =nkkklw1第第k个叶子的权值；个叶子的权值；从根结点到第从根结点到第k个叶子的路径长度个叶子的路径长度数据结构（数据结构（C版）版）清华大学出版社清华大学出版社哈夫曼树：哈夫曼树：给定一组具有确定权值的给定一组具有确定权值的叶子叶子结点，带权结点，带权路径路径长度最小的二叉树长度最小的二叉树。例：给定例：给定4个叶子结点，其权值分别为个叶子结点，其权值分别为2，3，4，7，可以构造出形状不同的可以构造出形状不同的多个二叉树。多个二叉树。 5.6 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码WPL=32 WPL=41 WPL=30234723477423数据结构（数据结构（
111、C版）版）清华大学出版社清华大学出版社哈夫曼树的特点：哈夫曼树的特点：1. 权值越大的叶子结点越靠近根结点，而权值越小的权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。叶子结点越远离根结点。 2. 只有度为只有度为0（叶子结点）和度为（叶子结点）和度为2（分支结点）的结（分支结点）的结点，不存在度为点，不存在度为1的结点的结点. 5.6 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码2347WPL=32 WPL=41 WPL=3023477423数据结构（数据结构（C版）版）清华大学出版社清华大学出版社哈夫曼算法基本思想：哈夫曼算法基本思想： 初始化初始化：由给定的：由给定的n个权
112、值个权值w1，w2，wn构造构造n棵只有一个根结点的二叉树，从而得到一个二叉树棵只有一个根结点的二叉树，从而得到一个二叉树集合集合FT1，T2，Tn； 选选取取与与合合并并：在在F中中选选取取根根结结点点的的权权值值最最小小的的两两棵棵二二叉叉树树分分别别作作为为左左、右右子子树树构构造造一一棵棵新新的的二二叉叉树树，这这棵棵新新二二叉叉树树的的根根结结点点的的权权值值为为其其左左、右右子子树树根根结结点的权值之和；点的权值之和； 删删除除与与加加入入：在在F中中删删除除作作为为左左、右右子子树树的的两两棵棵二叉树，并将新建立的二叉树加入到二叉树，并将新建立的二叉树加入到F中；中； 重复重复、
113、两步，当集合两步，当集合F中只剩下一棵二叉树中只剩下一棵二叉树时，这棵二叉树便是哈夫曼树。时，这棵二叉树便是哈夫曼树。 5.6 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码数据结构（数据结构（C版）版）清华大学出版社清华大学出版社第第1步：初始化步：初始化W2，3，4，5 哈夫曼树的构造过程哈夫曼树的构造过程5.6 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码3524第第2步：选取与合并步：选取与合并32 5第第3步：删除与加入步：删除与加入5432 5数据结构（数据结构（C版）版）清华大学出版社清华大学出版社W2，3，4，5 哈夫曼树的构造过程哈夫曼树的构造过程5.6 哈夫曼树及哈夫曼编码哈夫曼树及
114、哈夫曼编码重复第重复第2步步5432 554 9重复第重复第3步步 554 932数据结构（数据结构（C版）版）清华大学出版社清华大学出版社W2，3，4，5 哈夫曼树的构造过程哈夫曼树的构造过程5.6 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码重复第重复第2步步重复第重复第3步步 554 932 554 93214数据结构（数据结构（C版）版）清华大学出版社清华大学出版社哈夫曼算法的存储结构哈夫曼算法的存储结构 1. 设置一个数组设置一个数组huffTree2n- -1保存哈夫曼树中各保存哈夫曼树中各点的点的信息，数组元素的结点结构信息，数组元素的结点结构 。 weight lchild rch
115、ild parent其中：其中：weight：权值域，保存该结点的权值；：权值域，保存该结点的权值； lchild：指针域，结点的左孩子结点在数组中的下标；：指针域，结点的左孩子结点在数组中的下标； rchild：指针域，结点的右孩子结点在数组中的下标；：指针域，结点的右孩子结点在数组中的下标； parent：指针域，该结点的双亲结点在数组中的下标。：指针域，该结点的双亲结点在数组中的下标。struct element int weight; int lchild, rchild, parent;5.6 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码数据结构（数据结构（C版）版）清华大学出版社清华大
116、学出版社伪代码伪代码1.数组数组huffTree初始化，所有元素结点的双亲、左初始化，所有元素结点的双亲、左 右孩子都置为右孩子都置为- -1；2. 数组数组huffTree的前的前n个元素的权值置给定值个元素的权值置给定值wn；3. 进行进行n- -1次合并次合并 3.1 在二叉树集合中选取两个权值最小的根结点，在二叉树集合中选取两个权值最小的根结点， 其下标分别为其下标分别为i1, i2； 3.2 将二叉树将二叉树i1、i2合并为一棵新的二叉树合并为一棵新的二叉树k；5.6 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码数据结构（数据结构（C版）版）清华大学出版社清华大学出版社weight pa
117、rent lchild rchild-1 -1 -1-1 -1 -1-1 -1 -1-1 -1 -1-1 -1 -1-1 -1 -1-1 -1 -10123456初初 态态5.6 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码35242453数据结构（数据结构（C版）版）清华大学出版社清华大学出版社2 -1 -1 -14 -1 -1 -15 -1 -1 -13 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -10123456过程过程5.6 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码3524i1i2k503445432 5weight parent lchild rchild数据结构
118、（数据结构（C版）版）清华大学出版社清华大学出版社2 -1 -1 -14 -1 -1 -15 -1 -1 -13 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -10123456过程过程5.6 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码i1i2k503445432 591455 554 932weight parent lchild rchild数据结构（数据结构（C版）版）清华大学出版社清华大学出版社2 -1 -1 -14 -1 -1 -15 -1 -1 -13 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -10123456过程过程5.6 哈夫曼树及哈
119、夫曼编码哈夫曼树及哈夫曼编码i1i2k5034491455 554 932142566 554 93214weight parent lchild rchild数据结构（数据结构（C版）版）清华大学出版社清华大学出版社void HuffmanTree( (element huffTree , int w , int n ) ) for ( (i=0; i2*n- -1; i+) ) huffTree i.parent= - -1; huffTree i.lchild= - -1; huffTree i.rchild= - -1; for ( (i=0; in; i+) ) huffTree i
120、.weight=wi; for ( (k=n; k2*n- -1; k+) ) Select(h(huffTree, i1, i2) ); huffTreek.weight=huffTreei1.weight+huffTreei2.weight; huffTreei1.parent=k; huffTreei2.parent=k; huffTreek.lchild=i1; huffTreek.rchild=i2; 5.6 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码数据结构（数据结构（C版）版）清华大学出版社清华大学出版社哈夫曼树应用哈夫曼树应用哈夫曼编码哈夫曼编码编编码码：给给每每一一个个对对象象
121、标标记记一一个个二二进进制制位位串串来来表表示示一一组组对象。对象。例：例：ASCII，指令系统，指令系统等长编码：表示一组对象的二进制位串的长度相等。等长编码：表示一组对象的二进制位串的长度相等。不不等等长长编编码码：表表示示一一组组对对象象的的二二进进制制位位串串的的长长度度不不相相等。等。不不等等长长编编码码什什么么情情况况下空间效率高？下空间效率高？等等长长编编码码什什么么情情况况下下空间效率高？空间效率高？5.6 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码数据结构（数据结构（C版）版）清华大学出版社清华大学出版社5.6 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码前前缀缀编编码码：一一组组
122、编编码码中中任任一一编编码码都都不不是是其其它它任任何何一一个编码的前缀个编码的前缀 。前缀编码保证了在解码时不会有多种可能。前缀编码保证了在解码时不会有多种可能。 例例：一一组组字字符符A, B, C, D, E, F, G出出现现的的频频率率分分别别是是9, 11, 5, 7, 8, 2, 3，设计最经济的编码方案。，设计最经济的编码方案。哈夫曼树应用哈夫曼树应用哈夫曼编码哈夫曼编码数据结构（数据结构（C版）版）清华大学出版社清华大学出版社9523510191126871545000000111111ABDCEFG5.6 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码编码方案：编码方案：A：00
123、B：10C：010D：110E：111F：0110G：0111哈夫曼树应用哈夫曼树应用哈夫曼编码哈夫曼编码数据结构（数据结构（C版）版）清华大学出版社清华大学出版社树树 结结 构构树树 二二 叉叉 树树逻辑结构逻辑结构逻辑结构逻辑结构存储结构存储结构存储结构存储结构树树的的定定义义基基本本术术语语抽抽象象数数据据类类型型双双亲亲表表示示法法孩孩子子表表示示法法孩孩子子兄兄弟弟表表示示法法二二叉叉树树的的定定义义特特殊殊的的二二叉叉树树二二叉叉树树的的性性质质抽抽象象数数据据类类型型顺顺序序存存储储结结构构二二叉叉链链表表斜树斜树满二叉树满二叉树完全二叉树完全二叉树三三叉叉链链表表线线索索链链表
124、表树树的的遍遍历历前序遍历前序遍历后序遍历后序遍历层序遍历层序遍历二二叉叉树树的的遍遍历历前序遍历前序遍历中序遍历中序遍历后序遍历后序遍历层序遍历层序遍历遍历操作的遍历操作的实现实现基于遍历的基于遍历的其他算法其他算法相互转换相互转换小结小结:第第 5 章章 树和二叉树树和二叉树数据结构（数据结构（C版）版）清华大学出版社清华大学出版社1. 编写非递归算法，求二叉树中叶子结点的个数。编写非递归算法，求二叉树中叶子结点的个数。 2. 已知某字符串已知某字符串S为为“abcdeacedaeadcedabadadaead” ，对该字符串用，对该字符串用0，1进行前缀编码，问该字符串的编码至少有多少位。进行前缀编码，问该字符串的编码至少有多少位。第第 5 章章 树和二叉树树和二叉树作业：作业：
