数据结构二叉树ppt.ppt

《数据结构二叉树ppt.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章树与二叉树校长一系二系三系六系教务处科研处总务处601602教务科603ABCD…………张三李四王五…例1…工厂(根目录)f1f2f3fnd1d2dm………例2f11f12f1kd11d12…………例31树的基本概念2树的存储结构3二叉树4二叉树的存储结构5二叉树的遍历6线索二叉树6.1树的基本概念树是由n0个结点组成的有穷集合(不妨用D表示)以及结点之间关系组成的集合构成的结构。当n=0时，称该树为空树；在任何一棵非空的树中，有一个特殊的结点tD，称之为该树的根结点；其余结点D–{t}被分割成m>0个不相交的子集D1,D2,…,Dm,其中每一个子集Di又为一棵树，分别称之为t

2、的子树。递归定义一.树的定义JIHGFEACXBA的第1棵子树A的第3棵子树A的第2棵子树二.树(逻辑上)的特点1.有且仅有一个结点没有前驱结点,该结点为树的根结点。2.除了根结点外,每个结点有且仅有一个直接前驱结点。3.包括根结点在内，每个结点可以有多个后继结点。JIHGFEACXB4.树形表示法借助自然界中一棵倒置的树的形状来表示数据元素之间层次关系的方法。1.结点的度：2.树的度：3.叶结点：4.分支结点:5.层次的定义:JIHGFEACXB该结点拥有的子树的数目。树中结点度的最大值。度为0的结点.度非0的结点.根结点为第一层,若某结点在第i层,则其孩子结点(若存在)为第i+1层.四

3、.基本名词术语第1层第2层第3层7.树林(森林):m0棵不相交的树组成的树的集合.8.树的有序性:6.树的深度:树中结点所处的最大层次数.若树中结点的子树的相对位置不能随意改变,则称该树为有序树，否则称该树为无序树。JIHGFEACXB深度为3的树二叉树的基本形态：(空)根根左子树根右子树根左子树右子树6.2二叉树二.两种特殊形态的二叉树若一棵二叉树中的结点,或者为叶结点，或者具有两棵非空子树,并且叶结点都集中在二叉树的最下面一层.这样的二叉树为满二叉树.1.满二叉树若一棵二叉树中只有最下面两层的结点的度可以小于2,并且最下面一层的结点(叶结点)都依次排列在该层从左至右的位置上。这样的二

4、叉树为完全二叉树.2.完全二叉树1.一棵非空二叉树的第i层最多有2i–1个结点(i1)。三.二叉树的性质2.深度为h的非空二叉树最多有2h-1个结点.3.若非空二叉树有n0个叶结点,有n2个度为2的结点,则n0=n2+14.具有n个结点的完全二叉树的深度h=log2n+1.二叉树的存储结构一.二叉树的顺序存储结构12345678910ABCDEFGHIJBT[1:15]123456789101112131415ABCDEFGHIJ根据完全二叉树的性质,对于深度为h的完全二叉树,将树中所有结点的数据信息按照编号的顺序依次存储到一维数组BT[1:2h-1]中,由于编号与数组的下标一一对应

5、,该数组就是该完全二叉树的顺序存储结构.1.完全二叉树的顺序存储结构12345678910ABCDEFGHIJ111213BT[1:15]123456789101112131415ABCDEFGHJIABCDEFGHIJ2.一般二叉树的顺序存储结构对于一般二叉树,只须在二叉树中“添加”一些实际上二叉树中并不存在的“虚结点”(可以认为这些结点的数据信息为空),使其在形式上成为一棵“完全二叉树”,然后按照完全二叉树的顺序存储结构的构造方法将所有结点的数据信息依次存放于数组BT[1:2h-1]中。二.二叉树的链式存储结构(二叉链表)链结点的构造为lchilddatarchild其中,data为数

6、据域lchild与rchild分别为指向左、右子树的指针域.ABCDEFGIJABCDEFGJIT^^^^^^^^^^6.3.3二叉树的遍历二.前序遍历三.中序遍历四.后序遍历ABCDKFGIJEH前序遍历序列:A,B,D,K,J,G,C,F,I,E,H中序遍历序列:D,B,G,J,K,A,F,I,E,C,H后序遍历序列:D,G,J,K,B,E,I,F,H,C,A按层次遍历序列:A,B,C,D,K,F,H,J,I,G,E例6.3.2线索二叉树1.何谓线索二叉树？遍历结果是求得结点的一个线性序列。指向该线性序列“前驱”和“后继”的指针，称“线索”；包含“线索”的存储结构，称为“线索链表”；与

7、其相应的二叉树，称为“线索二叉树”；对二叉树以某种次序遍历，使其变为线索二叉树的过程，称为“线索化”。2.线索链表中结点的结构在二叉链表的结点结构中增加两个标志域，并规定：lchildLTagdataRTagrchild其中：LTag=0lchild域指示结点的左孩子1lchild域指示结点的前驱RTag=0rchild域指示结点的右孩子1rchild域指示结点的后继二叉树二叉线索存储表示typedefenum{Link