数据结构二叉树.pptxVIP

第1页/共43页数据结构二叉树第2页/共43页张三李四王五…例1校长一系二系三系…六系……教务处科研处总务处工厂…601602603教务科…ABCD第3页/共43页例2(根目录) \………f1f2f3fnd1d2dmf11f12f1kd11d12……… …第4页/共43页例3第5页/共43页1 树的基本概念2 树的存储结构3 二叉树4 二叉树的存储结构5 二叉树的遍历6 线索二叉树第6页/共43页一. 树的定义 树是由n?0 个结点组成的有穷集合(不妨用D表示)以及结点之间关系组成的集合构成的结构。 当n=0 时，称该树为空树； 在任何一棵非空的树中，有一个特殊的结点t ?D，称之为该树的根结点；其余结点D–{t}被分割成m0个不相交的子集D1, D2, … ,Dm,其中每一个子集Di又为一棵树，分别称之为t 的子树。递归定义 6.1 树的基本概念第7页/共43页ACXBEFGHIJA的第1棵子树A的第3棵子树A的第2棵子树二. 树(逻辑上)的特点1. 有且仅有一个结点没有前驱结点,该结点为树的根结点。2. 除了根结点外,每个结点有且仅有一个直接前驱结点。3. 包括根结点在内，每个结点可以有多个后继结点。第8页/共43页 借助自然界中一棵倒置的树的形状来表示数据元素之间层次关系的方法。ACXBEFGHIJ4. 树形表示法 第9页/共43页四. 基本名词术语A第1层第2层第3层CXBEFGHIJ该结点拥有的子树的数目。1. 结点的度：2. 树的度：树中结点度的最大值。度为0 的结点.3. 叶结点：4. 分支结点:度非0 的结点.5. 层次的定义: 根结点为第一层,若某结点在第i 层, 则其孩子结点(若存在)为第i+1层.第10页/共43页ACXBEFGHIJ深度为3的树6. 树的深度:树中结点所处的最大层次数.7. 树林(森林): m?0 棵不相交的树组成的树的集合.8. 树的有序性: 若树中结点的子树的相对位置不能 随意改变, 则称该树为有序树，否 则称该树为无序树。第11页/共43页根根根左子树左子树右子树根右子树 6.2 二叉树二叉树的基本形态：(空)第12页/共43页1. 满二叉树 若一棵二叉树中的结点,或者为叶结点， 或者具有两棵非空子树,并且叶结点都集中在二叉树的最下面一层.这样的二叉树为满二叉树.2.完全二叉树 若一棵二叉树中只有最下面两层的结点的度可以小于2,并且最下面一层的结点(叶结点)都依次排列在该层从左至右的位置上。这样的二叉树为完全二叉树.二. 两种特殊形态的二叉树第13页/共43页三. 二叉树的性质1. 一棵非空二叉树的第i 层最多有2i–1个结点(i?1)。2. 深度为h 的非空二叉树最多有2h -1个结点.3. 若非空二叉树有n0个叶结点,有n2个度为2的结点, 则n0=n2+1 4. 具有n个结点的完全二叉树的深度h=?log2n?+1.第14页/共43页 根据完全二叉树的性质 ,对于深度为h 的完全二叉树, 将树中所有结点的数据信息按照编号的顺序依次存储到一维数组BT[1:2h-1]中,由于编号与数组的下标一一对应, 该数组就是该完全二叉树的顺序存储结构.1A23BT[1:15]BCA B C D E F G H I J 67541 2 3 4 5 6 7 8 9 10 11 12 13 14 15GEDF9810IHJ 二叉树的存储结构一.二叉树的顺序存储结构 1. 完全二叉树的顺序存储结构第15页/共43页1AA23CBCB5746EDGDFFGE1112131089HJIHJIBT[1:15]A B C D E F G H J I1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 2. 一般二叉树的顺序存储结构第16页/共43页 对于一般二叉树, 只须在二叉树中“添加”一些实际上二叉树中并不存在的“虚结点” ( 可以认为这些结点的数据信息为空),使其在形式上成为一棵“完全二叉树”,然后按照完全二叉树的顺序存储结构的构造方法将所有结点的数据信息依次存放于数组BT[1: 2h -1]中。第17页/共43页链结点的构造为lchilddatarchild 其中, data 为数据域 lchild 与rchild 分别为指向左、右子树的指针域.TAABCBCGEFD^E^G^^^^DFJI^^^^JI二.二叉树的链式存储结构(二叉链表)第18页/共43页6.3.3 二叉树的遍历第19页/共43页二.前序遍历第20页/共43页三.中序遍历第21页/共43页四.后序遍历第22页/共43页例ABC