数据结构+二叉树及遍历+PPT.ppt

《数据结构+二叉树及遍历+PPT.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、目标在本章中，你将学习：在树中存储数据实现二叉树实现二叉搜索树在树中存储数据假设你被要求呈现操作系统的目录结构。目录结构含有不同的文件夹和文件。一个文件夹可能含有更多的子文件夹和文件。在这种情况下，要用线型结构来表示这种结构几乎是不可能的，因为所有的项目之间都有层级关系。要表示这样的结构，就需要一种非线型的数据存储机制。一个树结构就是以非线型结构来表示不同数据元素之间的层级关系的数据结构。ABCDIJHKGLMFE定义树结构树被应用于数据元素之间的关系以层级关系来表示的应用程序中。每个树结构中的数据元素都被称为一个节点。最顶层的节点被称为

2、根（root）。root定义树结构（续）nodeABCDIJHKGLMFE树中的每一个节点在其层级下可能有子树。root定义树结构（续）nodeABCDIJHKGLMFE树结构术语叶子节点：指没有子节点的节点。节点E,F,G,H,I,J,L,和M是叶子节点。ABCDIJHKGLMFE让我们来讨论树结构常用的一些术语。子树：是树结构的一部分，但它本身也可被看作一个树结构，这就是子树。子树也可以含有叶子节点。子节点：一个树结构中子树的根节点被称为子节点。树结构术语（续）有根B的树结构包含节点E、F、G和H，此树是节点A的子树。E,F,G和H是

3、B节点的子节点。B是这些节点的父节点。ABCDIJHKGLMFE节点的度：它指树结构中一个节点的子树的数量。树结构术语（续）C节点的度为1D节点的度为2A节点的度为3B节点的度为4ABCDIJHKGLMFE边：从父节点到子节点的连接被称为一个边。EdgeB、C和D节点互为兄弟节点。E、F、G和H互为兄弟节点。兄弟：它指同一个节点的子节点。树结构术语（续）ABCDIJHKGLMFE节点的层级：它指一个节点与根节点之间的距离（按节点数目计算）。根节点永远位于0级。当你将树移至低处，层级增加1。树结构术语（续）内部节点：它指根节点与叶子节点之间

4、的中间节点。节点B,C,D和K是内部节点。Level0Level1Level2Level3ABCDIJHKGLMFE树结构术语（续）树结构的深度：指一个树结构的最大层级。下面的树结构的深度是4。Level0Level1Level2Level3ABCDIJHKGLMFE查看下列树结构并回答问题：该树的深度为多少？节点B的子节点是那个？F节点的父节点是那个？E节点的层级为多少？H节点的兄弟节点是那个？D节点的兄弟节点是那个？那些节点是叶子节点？课间思考ABFGCEDHIroot课间思考（续）答案：4D和EC2H没有兄弟节点D节点的兄弟节点是E

5、F,G,H和I定义二叉树一个二叉树就是每个节点只能最多拥有2个子节点的树结构。这些子节点一般被视为左子节点和右子节点。二叉树有各种类型：严格二叉树二叉树的每一个节点（叶节点除外）都有非空的左子节点和右子节点。满二叉树完整二叉树满二叉树深度d的二叉树拥有刚好2d–1个节点。ABCDEFG深度=3节点数=23–1=7定义二叉树（续）完整二叉树：指有n个节点且深度为d，且其节点对应深度为k的完整二叉树中序号从0到n−1的节点。ABCDEF完整二叉树ABCDEG不完整二叉树定义二叉树（续）ABCDEF满二叉树G012654301234501234

6、5表示一个二叉树二叉树的数组表示：所有节点被表示为数组中的元素。ABCDEFGABCDEGF[0][1][2][3][4][5][6]0123456二叉树数组表示如果一个二叉树有N个节点，那么对于索引为I的任何节点，其中0n–1，那么此节点没有左子节点。i的右子节点位于2i+2：如果2i+2>n–1，那么此节点没有右子节点。二叉树的链接表现形式：使用链接列表来实现一个二叉树。链接表示中的每个节点都具有以下信息：数据对左子节点的引用对右子节点的引用如果一个节点

7、不含有左子节点或右子节点，或一个子节点都没有，相应的左（右）子节点字段就指向NULL。DataNode表示一个二叉树（续）5268597224807036........5236682459727080二叉树链接表示rootroot表示一个二叉树（续）你可以在叉树上执行各种操作。在二叉树上最常见的操作是遍历。遍历指的是访问树中所有节点一次的过程。遍历二叉树有三种方式：中序遍历（Inordertraversal）前序遍历（Preordertraversal）后序遍历（Postordertraversal）遍历二叉树中序遍历一个二叉数所需的步

8、骤如下：1.遍历左子树2.访问根节点3.遍历右子树让我们考虑一个示例。中序遍历中序遍历（续）ACEBFGDHIroot节点A的左子树不为NULL。因此，移动到B以遍历A的左子树。节点B的左子树