数据结构+二叉树及遍历

.,目标,在本章中，你将学习：在树中存储数据实现二叉树实现二叉搜索树,.,在树中存储数据,假设你被要求呈现操作系统的目录结构。目录结构含有不同的文件夹和文件。一个文件夹可能含有更多的子文件夹和文件。在这种情况下，要用线型结构来表示这种结构几乎是不可能的，因为所有的项目之间都有层级关系。要表示这样的结构，就需要一种非线型的数据存储机制。,.,一个树结构就是以非线型结构来表示不同数据元素之间的层级关系的数据结构。,A,B,C,D,I,J,H,K,G,L,M,F,E,定义树结构,树被应用于数据元素之间的关系以层级关系来表示的应用程序中。,.,每个树结构中的数据元素都被称为一个节点。最顶层的节点被称为根（root）。,root,定义树结构（续）,node,A,B,C,D,I,J,H,K,G,L,M,F,E,.,树中的每一个节点在其层级下可能有子树。,root,定义树结构（续）,node,A,B,C,D,I,J,H,K,G,L,M,F,E,.,树结构术语,叶子节点：指没有子节点的节点。,节点E,F,G,H,I,J,L,和M是叶子节点。,A,B,C,D,I,J,H,K,G,L,M,F,E,让我们来讨论树结构常用的一些术语。,.,子树：是树结构的一部分，但它本身也可被看作一个树结构，这就是子树。子树也可以含有叶子节点。,子节点：一个树结构中子树的根节点被称为子节点。,树结构术语（续）,有根B的树结构包含节点E、F、G和H，此树是节点A的子树。,E,F,G和H是B节点的子节点。B是这些节点的父节点。,A,B,C,D,I,J,H,K,G,L,M,F,E,.,节点的度：它指树结构中一个节点的子树的数量。,树结构术语（续）,C节点的度为1D节点的度为2A节点的度为3B节点的度为4,A,B,C,D,I,J,H,K,G,L,M,F,E,边：从父节点到子节点的连接被称为一个边。,Edge,.,B、C和D节点互为兄弟节点。E、F、G和H互为兄弟节点。,兄弟：它指同一个节点的子节点。,树结构术语（续）,A,B,C,D,I,J,H,K,G,L,M,F,E,.,节点的层级：它指一个节点与根节点之间的距离（按节点数目计算）。根节点永远位于0级。当你将树移至低处，层级增加1。,树结构术语（续）,内部节点：它指根节点与叶子节点之间的中间节点。,节点B,C,D和K是内部节点。,Level0,Level1,Level2,Level3,A,B,C,D,I,J,H,K,G,L,M,F,E,.,树结构术语（续）,树结构的深度：指一个树结构的最大层级。下面的树结构的深度是4。,Level0,Level1,Level2,Level3,A,B,C,D,I,J,H,K,G,L,M,F,E,.,查看下列树结构并回答问题：该树的深度为多少？节点B的子节点是那个？F节点的父节点是那个？E节点的层级为多少？H节点的兄弟节点是那个？D节点的兄弟节点是那个？那些节点是叶子节点？,课间思考,A,B,F,G,C,E,D,H,I,root,.,课间思考（续）,答案：4D和EC2H没有兄弟节点D节点的兄弟节点是EF,G,H和I,.,定义二叉树,一个二叉树就是每个节点只能最多拥有2个子节点的树结构。这些子节点一般被视为左子节点和右子节点。二叉树有各种类型：严格二叉树二叉树的每一个节点（叶节点除外）都有非空的左子节点和右子节点。满二叉树完整二叉树,.,满二叉树深度d的二叉树拥有刚好2d1个节点。,A,B,C,D,E,F,G,深度=3节点数=231=7,定义二叉树（续）,.,完整二叉树：指有n个节点且深度为d，且其节点对应深度为k的完整二叉树中序号从0到n1的节点。,A,B,C,D,E,F,完整二叉树,A,B,C,D,E,G,不完整二叉树,定义二叉树（续）,A,B,C,D,E,F,满二叉树,G,0,1,2,6,5,4,3,0,1,2,3,4,5,0,1,2,3,4,5,.,表示一个二叉树,二叉树的数组表示：所有节点被表示为数组中的元素。,A,B,C,D,E,F,G,A,B,C,D,E,G,F,0,1,2,3,4,5,6,0,1,2,3,4,5,6,二叉树,数组表示,如果一个二叉树有N个节点，那么对于索引为I的任何节点，其中0n1，那么此节点没有左子节点。i的右子节点位于2i+2：如果2i+2n1，那么此节点没有右子节点。,.,二叉树的链接表现形式：使用链接列表来实现一个二叉树。链接表示中的每个节点都具有以下信息：数据对左子节点的引用对右子节点的引用如果一个节点不含有左子节点或右子节点，或一个子节点都没有，相应的左（右）子节点字段就指向NULL。,Data,Node,表示一个二叉树（续）,.,52,68,59,72,24,80,70,36,.,.,.,.,.,.,.,.,52,36,68,24,59,72,70,80,二叉树,链接表示,root,root,表示一个二叉树（续）,.,你可以在叉树上执行各种操作。在二叉树上最常见的操作是遍历。遍历指的是访问树中所有节点一次的过程。遍历二叉树有三种方式：中序遍历（Inordertraversal）前序遍历（Preordertraversal）后序遍历（Postordertraversal）,遍历二叉树,.,中序遍历一个二叉数所需的步骤如下：1.遍历左子树2.访问根节点3.遍历右子树让我们考虑一个示例。,中序遍历,.,中序遍历（续）,A,C,E,B,F,G,D,H,I,root,节点A的左子树不为NULL。因此，移动到B以遍历A的左子树。节点B的左子树不为NULL。因此，移动到D以遍历B的左子树。,.,中序遍历（续）,节点D的左子树为NULL。因此，访问节点D。,D,A,C,E,B,F,G,D,H,I,root,.,中序遍历（续）,D的右子树不为NULL。因此，移动到D的右子树。,D,A,C,E,B,F,G,D,H,I,root,.,中序遍历（续）,H的左子树为空。因此，访问节点H。,D,H,A,C,E,B,F,G,D,H,I,root,.,中序遍历（续）,H的右子树为空。因此，移动到节点B。,D,H,A,C,E,B,F,G,D,H,I,root,.,中序遍历（续）,已经访问了B的左子树。因此，访问节点B。,D,H,B,A,C,E,B,F,G,D,H,I,root,.,中序遍历（续）,B的右子树不为空。因此，移动到B的右子树。,D,H,B,A,C,E,B,F,G,D,H,I,root,.,中序遍历（续）,E的左子树为空。因此，访问节点E。,D,H,E,B,A,C,E,B,F,G,D,H,I,root,.,中序遍历（续）,E的右子树为空。因此，移动到节点A。,D,H,E,B,A,C,E,B,F,G,D,H,I,root,.,中序遍历（续）,已经访问过A的左子树。因此，访问节点A.,D,H,E,B,A,A,C,E,B,F,G,D,H,I,root,.,中序遍历（续）,A的右子树不为空。因此，移动到A的右子树。,D,H,E,B,A,A,C,E,B,F,G,D,H,I,root,.,中序遍历（续）,C的左子树不为空。因此，移动到C的左子树。,D,H,E,B,A,A,C,E,B,F,G,D,H,I,root,.,中序遍历（续）,F的左子树为空。因此，访问节点F。,D,H,E,B,A,F,A,C,E,B,F,G,D,H,I,root,.,中序遍历（续）,F的右子树为空。因此，移动到节点C。,D,H,E,B,A,F,A,C,E,B,F,G,D,H,I,root,.,中序遍历（续）,已经访问过节点C的左子树。因此，访问节点C.,D,H,E,B,A,F,C,A,C,E,B,F,G,D,H,I,root,.,中序遍历（续）,C的右子树不为空。因此，移动到节点C的右子树。,D,H,E,B,A,F,C,A,C,E,B,F,G,D,H,I,root,.,中序遍历（续）,G的左子树不为空。因此，移动到节点G的左子树。,D,H,E,B,A,F,C,A,C,E,B,F,G,D,H,I,root,.,中序遍历（续）,I的左子树为空。因此，访问I。,D,H,E,B,A,F,C,I,A,C,E,B,F,G,D,H,I,root,.,中序遍历（续）,I的右子树为空。因此，移动到节点G。,D,H,E,B,A,F,C,I,A,C,E,B,F,G,D,H,I,root,.,中序遍历（续）,访问节点G。,D,H,E,B,A,F,C,I,G,A,C,E,B,F,G,D,H,I,root,.,中序遍历（续）,G的右子树为空。,D,H,E,B,A,F,C,I,G,遍历完成,A,C,E,B,F,G,D,H,I,root,.,前序遍历,按前序遍历一个二叉树的顺序如下：1.访问根节点2.遍历左子树3.遍历右子树,.,前序遍历（续）,A,C,E,B,F,G,D,H,I,对下面的树执行前序遍历。,A,B,D,H,E,C,F,G,I,前序遍历：,.,后序遍历,在二叉树中进行后序遍历的步骤如下：1.遍历左子树2.遍历右子树3.访问根节点,.,后序遍历（续）,A,C,E,B,F,G,D,H,I,对下面的树执行后序遍历。,H,D,E,B,F,I,G,C,A