数据结构二叉树ppt

第6章树与二叉树校长一系二系三系六系教务处科研处总务处601602教务科603ABCD…………张三李四王五…例1…工厂(根目录)\f1f2f3fnd1d2dm………例2f11f12f1kd11d12…………例31树的基本概念2树的存储结构3二叉树4二叉树的存储结构5二叉树的遍历6线索二叉树6.1树的基本概念树是由n0个结点组成的有穷集合(不妨用D表示)以及结点之间关系组成的集合构成的结构。当n=0时，称该树为空树；在任何一棵非空的树中，有一个特殊的结点tD，称之为该树的根结点；其余结点D–{t}被分割成m0个不相交的子集D1,D2,…,Dm,其中每一个子集Di又为一棵树，分别称之为t的子树。递归定义一.树的定义JIHGFEACXBA的第1棵子树A的第3棵子树A的第2棵子树二.树(逻辑上)的特点1.有且仅有一个结点没有前驱结点,该结点为树的根结点。2.除了根结点外,每个结点有且仅有一个直接前驱结点。3.包括根结点在内，每个结点可以有多个后继结点。JIHGFEACXB4.树形表示法借助自然界中一棵倒置的树的形状来表示数据元素之间层次关系的方法。1.结点的度：2.树的度：3.叶结点：4.分支结点:5.层次的定义:JIHGFEACXB该结点拥有的子树的数目。树中结点度的最大值。度为0的结点.度非0的结点.根结点为第一层,若某结点在第i层,则其孩子结点(若存在)为第i+1层.四.基本名词术语第1层第2层第3层7.树林(森林):m0棵不相交的树组成的树的集合.8.树的有序性:6.树的深度:树中结点所处的最大层次数.若树中结点的子树的相对位置不能随意改变,则称该树为有序树，否则称该树为无序树。JIHGFEACXB深度为3的树二叉树的基本形态：(空)根根左子树根右子树根左子树右子树6.2二叉树二.两种特殊形态的二叉树若一棵二叉树中的结点,或者为叶结点，或者具有两棵非空子树,并且叶结点都集中在二叉树的最下面一层.这样的二叉树为满二叉树.1.满二叉树若一棵二叉树中只有最下面两层的结点的度可以小于2,并且最下面一层的结点(叶结点)都依次排列在该层从左至右的位置上。这样的二叉树为完全二叉树.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]中,由于编号与数组的下标一一对应,该数组就是该完全二叉树的顺序存储结构.1.完全二叉树的顺序存储结构12345678910ABCDEFGHIJ111213BT[1:15]123456789101112131415ABCDEFGHJIABCDEFGHIJ2.一般二叉树的顺序存储结构对于一般二叉树,只须在二叉树中“添加”一些实际上二叉树中并不存在的“虚结点”(可以认为这些结点的数据信息为空),使其在形式上成为一棵“完全二叉树”,然后按照完全二叉树的顺序存储结构的构造方法将所有结点的数据信息依次存放于数组BT[1:2h-1]中。二.二叉树的链式存储结构(二叉链表)链结点的构造为lchilddatarchild其中,data为数据域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.何谓线索二叉树？遍历结果是求得结点的一个线性序列。指向该线性序列“前驱”和“后继”的指针，称“线索”；包含“线索”的存储结构，称为“线索链表”；与其相应的二叉树，称为“线索二叉树”；对二叉树以某种次序遍历，使其变为线索二叉树的过程，称为“线索化”。2.线索链表中结点的结构在二叉链表的结点结构中增加两个标志域，并规定：lchildLTagdataRTagrchild其中：LTag=0lchild域指示结点的左孩子1lchild域指示结点的前驱RTag=0rchild域指示结点的右孩子1rchild域指示结点的后继二叉树二叉线索存储表示typedefenum{Link,Thread}PointerThr;//Link==0:指针，Thread==1:线索typedefstructBiThrNode{TElemTypedata;StructBiThrNode*lchild,*rchild;//左右孩子指针PointerThrLTag,RTag;//左右标志}BiThrNode,*BiThrTree;3.线索二叉树图例线索二叉树及其存储结构（a）中序线索二叉树（b）中序线索链表1234567010020131141050161171thrt01如何在线索树中找结点的后继？结合中序线索树若其右标志为“1”，右链是线索，右链直接指示了结点的后继；若其右标志为“0”，右链是指针，其后继为右子树中最左下的结点。1234567如何在线索树中找结点的前驱？结合中序线索树若其左标志为“1”，左链为线索，直接指示其前驱；若其左标志为“0”，左子树中最右下的结点为其前驱。1234567线索链表的中序遍历算法StatusIOTraver_T(BiThrTreeT,Status(*Visit)(TElemTypee)){//T指向头结点，头结点的左链lchild指向根结点，中序遍历//二叉线索树T的非递归算法，对每个数据元素调用函数Visit。p=T-lchild;//p指向根结点while(p!=T){//空树或遍历结束时，p==Twhile(p-LTag==Link)p=p-lchild;if(!Visit(p-data))returnERROR;//访问其左子树为空的结点while(p-RTag==Thread&&p-rchild!=T){p=p-rchild;Visit(p-data);}//访问后继结点p=p-rchild;}returnOK;}//IOTraver_T010020131141050161171T0116.4.2森林和二叉树的转换1.树和二叉树的对应关系由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。树转换为二叉树方法：1）对每个孩子进行从左到右的排序；2）在兄弟之间加一条连线；3）对每个结点，除了左孩子外，去除其与其余孩子之间的联系；4）以根结点为轴心，将整个树顺时针转45°。ABCDEGHFIaABCDEGHFIbABCDEGHFIcABCDEGHFId2.森林和二叉树的对应关系从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树必空。若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可导出森林和二叉树的对应关系。BCDEGHFIaBCDEGHFIbBCDEGHFIcBCDEGHFId已知条件：森林和二叉树的对应关系设森林F=(T1,T2,…,Tn);T1=(root，t11,t12,…,t1m);二叉树B=(LBT,Node(root),RBT);由森林转换成二叉树的转换规则为:若F=Φ，则B=Φ;否则，由Root(T1)对应得到Node(root);由(t11,t12,…,t1m)对应得到LBT;由(T2,T3,…,Tn)对应得到RBT。由二叉树转换为森林的转换规则为:若B=Φ,则F=Φ;否则，由Node(root)对应得到Root(T1);由LBT对应得到(t11,t12,…，t1m);T1除根以外所构成的森林由RBT对应得到(T2,T3,…,Tn)；除T1之外的森林6.4.3树和森林的遍历1.树的遍历：有三条搜索路径先根(序)遍历：若树不空，则先访问根结点，然后依次先根遍历各棵子树。后根(序)遍历：若树不空，则先依次后根遍历各棵子树，然后访问根结点。按层次遍历：若树不空，则自上而下自左至右访问树中每个结点。例对树进行先根遍历，获得的先根序列是：对树进行后根遍历，获得的后根序列是：ABCDEGHFIABEFCDGHIEFBCGHIDA2.森林的遍历先序遍历(对森林中的每一棵树进行先根遍历)1）若森林不空，访问森林中第一棵树的根结点；2）先序遍历森林中第一棵树的子树森林；3）先序遍历森林中(除第一棵树外)其余树构成的森林。后序遍历(对森林中的每一棵树进行后根遍历)1）若森林不空，后序遍历森林中第一棵树的子树森林；2）访问森林中第一棵树的根结点；3）后序遍历森林中(除第一棵树外)其余树构成的森林。例：对森林进行先序遍历，获得的先序序列是：对森林进行后序遍历，获得的后序序列是：BCDEGHFIBEFCDGHIEFBCGHID总结：1.二叉树的线索化2.树的表示及其遍历操作；3.建立森林与二叉树的对应关系。由于在树和森林中，一个结点的孩子的个数不定，它们在计算机中的表示以及在各种操作计算机中的算法实现均不易实现，因此将树和森林表示为二叉树，并将对树和森林的操作转化为对二叉树的操作是通常采用的方法。