1、数据结构和算法数据结构和算法课程课程13Ver. 1.0目标目标在本章中，你将学习：在树中存储数据实现二叉树实现二叉搜索树1数据结构和算法数据结构和算法课程课程13Ver. 1.0在树中存储数据在树中存储数据假设你被要求呈现操作系统的目录结构。目录结构含有不同的文件夹和文件。一个文件夹可能含有更多的子文件夹和文件。在这种情况下，要用线型结构来表示这种结构几乎是不可能的，因为所有的项目之间都有层级关系。要表示这样的结构，就需要一种非线型的数据存储机制。2数据结构和算法数据结构和算法课程课程13Ver. 1.0一个树结构就是以非线型结构来表示不同数据元素之间的层级关系的数据结构。ABCDIJHKG
2、LMFE定义树结构定义树结构 树被应用于数据元素之间的关系以层级关系来表示的应用程序中。3数据结构和算法数据结构和算法课程课程13Ver. 1.0每个树结构中的数据元素都被称为一个节点。最顶层的节点被称为根（root）。root定义树结构（续）定义树结构（续）nodeABCDIJHKGLMFE4数据结构和算法数据结构和算法课程课程13Ver. 1.0树中的每一个节点在其层级下可能有子树。root定义树结构（续）定义树结构（续）nodeABCDIJHKGLMFE5数据结构和算法数据结构和算法课程课程13Ver. 1.0树结构术语树结构术语叶子节点：指没有子节点的节点。叶子节点：指没有子节点的节点
3、。 节点 E, F, G, H, I, J, L, 和 M 是叶子节点。ABCDIJHKGLMFE让我们来讨论树结构常用的一些术语。6数据结构和算法数据结构和算法课程课程13Ver. 1.0子树：子树：是树结构的一部分， 但它本身也可被看作一个树结构，这就是子树。 子树也可以含有叶子节点。子节点：子节点：一个树结构中子树的根节点被称为子节点。 树结构术语（续）树结构术语（续） 有根B的树结构包含节点E、F、G和H，此树是节点A的子树。 E, F, G和 H 是B节点的子节点。 B是这些节点的父节点。ABCDIJHKGLMFE7数据结构和算法数据结构和算法课程课程13Ver. 1.0节点的度：节
4、点的度：它指树结构中一个节点的子树的数量。树结构术语（续）树结构术语（续）C节点的度为1D节点的度为2A节点的度为3B节点的度为4ABCDIJHKGLMFE边：边：从父节点到子节点的连接被称为一个边。Edge8数据结构和算法数据结构和算法课程课程13Ver. 1.0 B、C和D节点互为兄弟节点。 E、F、G和H互为兄弟节点。兄弟：兄弟：它指同一个节点的子节点。树结构术语（续）树结构术语（续）ABCDIJHKGLMFE9数据结构和算法数据结构和算法课程课程13Ver. 1.0节点的层级：节点的层级：它指一个节点与根节点之间的距离（按节点数目计算）。根节点永远位于0级。当你将树移至低处，层级增加1
5、。树结构术语（续）树结构术语（续）内部节点：内部节点：它指根节点与叶子节点之间的中间节点 。 节点 B, C, D和 K 是内部节点。Level 0Level 1Level 2Level 3ABCDIJHKGLMFE10数据结构和算法数据结构和算法课程课程13Ver. 1.0树结构术语（续）树结构术语（续）树结构的深度：树结构的深度：指一个树结构的最大层级。下面的树结构的深度是 4。Level 0Level 1Level 2Level 3ABCDIJHKGLMFE11数据结构和算法数据结构和算法课程课程13Ver. 1.0查看下列树结构并回答问题：a. 该树的深度为多少？b. 节点B的子节点是
6、那个？c. F节点的父节点是那个？d. E节点的层级为多少？e. H节点的兄弟节点是那个？f.D节点的兄弟节点是那个？g. 那些节点是叶子节点？课间思考课间思考ABFGCEDHIroot12数据结构和算法数据结构和算法课程课程13Ver. 1.0课间思考（续）课间思考（续）答案：a. 4b. D 和Ec. Cd. 2e. H 没有兄弟节点f.D节点的兄弟节点是Eg. F, G, H和 I13数据结构和算法数据结构和算法课程课程13Ver. 1.0定义二叉树定义二叉树一个二叉树就是每个节点只能最多拥有2个子节点的树结构。这些子节点一般被视为左子节点和右子节点。 二叉树有各种类型：严格二叉树二叉树
7、的每一个节点（叶节点除外）都有非空的左子节点和右子节点。满二叉树完整二叉树14数据结构和算法数据结构和算法课程课程13Ver. 1.0满二叉树 深度d的二叉树拥有刚好2d 1个节点。ABCDEFG 深度 = 3 节点数 = 23 1 = 7定义二叉树（续）定义二叉树（续）15数据结构和算法数据结构和算法课程课程13Ver. 1.0完整二叉树： 指有 n 个节点且深度为 d ，且其节点对应深度为k 的完整二叉树中序号从0到n 1 的节点。ABCDEF完整二叉树完整二叉树ABCDEG不完整二叉树不完整二叉树定义二叉树（续）定义二叉树（续）ABCDEF满二叉树满二叉树G012654301234501
8、234516数据结构和算法数据结构和算法课程课程13Ver. 1.0表示一个二叉树表示一个二叉树二叉树的数组表示：所有节点被表示为数组中的元素。ABCDEFGABCDEGF01234560123456二叉树二叉树数组表示数组表示如果一个二叉树有N个节点，那么对于索引为I的任何节点，其中0 i n 1， 那么此节点没有左子节点。i 的右子节点位于 2i + 2：如果 2i + 2 n 1，那么此节点没有右子节点。17数据结构和算法数据结构和算法课程课程13Ver. 1.0二叉树的链接表现形式：使用链接列表来实现一个二叉树。链接表示中的每个节点都具有以下信息：数据对左子节点的引用对右子节点的引用如
9、果一个节点不含有左子节点或右子节点，或一个子节点都没有，相应的左（右）子节点字段就指向NULL。DataNode表示一个二叉树（续）表示一个二叉树（续）18数据结构和算法数据结构和算法课程课程13Ver. 1.05268597224807036.5236682459727080二叉树二叉树链接表示链接表示rootroot表示一个二叉树（续）表示一个二叉树（续）19数据结构和算法数据结构和算法课程课程13Ver. 1.0你可以在叉树上执行各种操作。在二叉树上最常见的操作是遍历。遍历指的是访问树中所有节点一次的过程。遍历二叉树有三种方式：中序遍历（Inorder traversal）前序遍历（Pr
10、eorder traversal）后序遍历（Postorder traversal）遍历二叉树遍历二叉树20数据结构和算法数据结构和算法课程课程13Ver. 1.0中序遍历一个二叉数所需的步骤如下： 1. 遍历左子树 2.访问根节点 3.遍历右子树让我们考虑一个示例。中序遍历中序遍历21数据结构和算法数据结构和算法课程课程13Ver. 1.0中序遍历（续）中序遍历（续）ACEBFGDHIroot节点A的左子树不为 NULL。因此，移动到B以遍历A的左子树。节点B的左子树不为NULL。因此，移动到D以遍历B的左子树。22数据结构和算法数据结构和算法课程课程13Ver. 1.0中序遍历（续）中序遍
11、历（续）节点D的左子树为 NULL。因此，访问节点D。DACEBFGDHIroot23数据结构和算法数据结构和算法课程课程13Ver. 1.0中序遍历（续）中序遍历（续）D的右子树不为NULL。因此，移动到D的右子树。DACEBFGDHIroot24数据结构和算法数据结构和算法课程课程13Ver. 1.0中序遍历（续）中序遍历（续）H的左子树为空。因此，访问节点 H。DHACEBFGDHIroot25数据结构和算法数据结构和算法课程课程13Ver. 1.0中序遍历（续）中序遍历（续）H的右子树为空。因此，移动到节点 B。DHACEBFGDHIroot26数据结构和算法数据结构和算法课程课程13
12、Ver. 1.0中序遍历（续）中序遍历（续）已经访问了B的左子树。因此，访问节点 B。DHBACEBFGDHIroot27数据结构和算法数据结构和算法课程课程13Ver. 1.0中序遍历（续）中序遍历（续）B的右子树不为空。因此，移动到B的右子树。DHBACEBFGDHIroot28数据结构和算法数据结构和算法课程课程13Ver. 1.0中序遍历（续）中序遍历（续）E的左子树为空。因此，访问节点E。DHEBACEBFGDHIroot29数据结构和算法数据结构和算法课程课程13Ver. 1.0中序遍历（续）中序遍历（续）E的右子树为空。因此，移动到节点A。DHEBACEBFGDHIroot30数
13、据结构和算法数据结构和算法课程课程13Ver. 1.0中序遍历（续）中序遍历（续）已经访问过A的左子树。因此，访问节点A.DHEBAACEBFGDHIroot31数据结构和算法数据结构和算法课程课程13Ver. 1.0中序遍历（续）中序遍历（续）A 的右子树不为空。因此，移动到A的右子树。DHEBAACEBFGDHIroot32数据结构和算法数据结构和算法课程课程13Ver. 1.0中序遍历（续）中序遍历（续）C的左子树不为空。因此，移动到C的左子树。DHEBAACEBFGDHIroot33数据结构和算法数据结构和算法课程课程13Ver. 1.0中序遍历（续）中序遍历（续）F的左子树为空。因此
14、，访问节点F。DHEBAFACEBFGDHIroot34数据结构和算法数据结构和算法课程课程13Ver. 1.0中序遍历（续）中序遍历（续）F的右子树为空。因此，移动到节点C。DHEBAFACEBFGDHIroot35数据结构和算法数据结构和算法课程课程13Ver. 1.0中序遍历（续）中序遍历（续）已经访问过节点C的左子树。因此，访问节点C.DHEBAFCACEBFGDHIroot36数据结构和算法数据结构和算法课程课程13Ver. 1.0中序遍历（续）中序遍历（续）C的右子树不为空。因此，移动到节点C的右子树。DHEBAFCACEBFGDHIroot37数据结构和算法数据结构和算法课程课程
15、13Ver. 1.0中序遍历（续）中序遍历（续）G的左子树不为空。因此，移动到节点G的左子树。DHEBAFCACEBFGDHIroot38数据结构和算法数据结构和算法课程课程13Ver. 1.0中序遍历（续）中序遍历（续）I的左子树为空。因此，访问 I。DHEBAFCIACEBFGDHIroot39数据结构和算法数据结构和算法课程课程13Ver. 1.0中序遍历（续）中序遍历（续）I的右子树为空。因此，移动到节点G。DHEBAFCIACEBFGDHIroot40数据结构和算法数据结构和算法课程课程13Ver. 1.0中序遍历（续）中序遍历（续）访问节点 G。DHEBAFCIGACEBFGDHI
16、root41数据结构和算法数据结构和算法课程课程13Ver. 1.0中序遍历（续）中序遍历（续）G的右子树为空。DHEBAFCIG遍历完成遍历完成ACEBFGDHIroot42数据结构和算法数据结构和算法课程课程13Ver. 1.0前序遍历前序遍历按前序遍历一个二叉树的顺序如下： 1. 访问根节点 2.遍历左子树 3.遍历右子树43数据结构和算法数据结构和算法课程课程13Ver. 1.0前序遍历（续）前序遍历（续）ACEBFGDHI对下面的树执行前序遍历。ABDHECFGI前序遍历：前序遍历：44数据结构和算法数据结构和算法课程课程13Ver. 1.0后序遍历后序遍历在二叉树中进行后序遍历的步
17、骤如下：1. 遍历左子树2. 遍历右子树3. 访问根节点45数据结构和算法数据结构和算法课程课程13Ver. 1.0后序遍历（续）后序遍历（续）ACEBFGDHI对下面的树执行后序遍历。HDEBFIGCA后序遍历：后序遍历：46数据结构和算法数据结构和算法课程课程13Ver. 1.0在_遍历方法中，会首先访问根节点，然后再是左右子树。课间思考课间思考答案：前序47数据结构和算法数据结构和算法课程课程13Ver. 1.0在本节课中，你已经学到：一个树结构就是以非线型数据结构来表示不同数据元素之间的层级关系。一个二叉树就是一个特定类型的树，其中的每个节点最多只能有2个子节点。二叉树可以使用数组来实施，也可以使用链接列表，取决于需求。树的遍历操作就是访问树中所有节点一遍。有三种类型的遍历，中序、前序和后序遍历。小结小结48
