数据结构二叉树ppt

第6章树与二叉树数据结构二叉树ppt全文共42页，当前为第1页。校长一系二系三系六系教务处科研处总务处601602教务科603ABCD…………张三李四王五…例1…工厂数据结构二叉树ppt全文共42页，当前为第2页。(根目录)

\f1f2f3fnd1d2dm………例2f11f12f1kd11d12…………数据结构二叉树ppt全文共42页，当前为第3页。例3数据结构二叉树ppt全文共42页，当前为第4页。1树的基本概念2树的存储结构3二叉树4二叉树的存储结构5二叉树的遍历6线索二叉树数据结构二叉树ppt全文共42页，当前为第5页。

6.1

树的基本概念

树是由n0个结点组成的有穷集合(不妨用D表示)以及结点之间关系组成的集合构成的结构。当n=0时，称该树为空树；在任何一棵非空的树中，有一个特殊的结点tD，称之为该树的根结点；其余结点D–{t}被分割成m>0个不相交的子集D1,D2,…,Dm,其中每一个子集Di又为一棵树，分别称之为t的子树。递归定义一.树的定义数据结构二叉树ppt全文共42页，当前为第6页。2021/3/117JIHGFEACXBA的第1棵子树A的第3棵子树A的第2棵子树二.树(逻辑上)的特点1.有且仅有一个结点没有前驱结点,该结点为树的根结点。2.除了根结点外,每个结点有且仅有一个直接前驱结点。3.包括根结点在内，每个结点可以有多个后继结点。数据结构二叉树ppt全文共42页，当前为第7页。JIHGFEACXB4.

树形表示法

借助自然界中一棵倒置的树的形状来表示数据元素之间层次关系的方法。数据结构二叉树ppt全文共42页，当前为第8页。1.

结点的度：2.

树的度：3.

叶结点：4.

分支结点:5.

层次的定义:JIHGFEACXB该结点拥有的子树的数目。树中结点度的最大值。度为0的结点.度非0的结点.

根结点为第一层,若某结点在第i层,

则其孩子结点(若存在)为第i+1层.四.基本名词术语第1层第2层第3层数据结构二叉树ppt全文共42页，当前为第9页。7.

树林(森林):m0棵不相交的树组成的树的集合.8.

树的有序性:6.

树的深度:树中结点所处的最大层次数.

若树中结点的子树的相对位置不能随意改变,则称该树为有序树，否则称该树为无序树。JIHGFEACXB深度为3的树数据结构二叉树ppt全文共42页，当前为第10页。二叉树的基本形态：(空)根根左子树根右子树根左子树右子树

6.2

二叉树数据结构二叉树ppt全文共42页，当前为第11页。二.两种特殊形态的二叉树

若一棵二叉树中的结点,或者为叶结点，或者具有两棵非空子树,并且叶结点都集中在二叉树的最下面一层.这样的二叉树为满二叉树.1.满二叉树

若一棵二叉树中只有最下面两层的结点的度可以小于2,并且最下面一层的结点(叶结点)都依次排列在该层从左至右的位置上。这样的二叉树为完全二叉树.2.完全二叉树数据结构二叉树ppt全文共42页，当前为第12页。1.一棵非空二叉树的第i层最多有2i–1个结点(i1)。三.二叉树的性质2.

深度为h的非空二叉树最多有2h-1个结点.3.

若非空二叉树有n0个叶结点,有n2个度为2的结点,

则n0=n2+1

4.

具有n个结点的完全二叉树的深度h=log2n+1.数据结构二叉树ppt全文共42页，当前为第13页。

二叉树的存储结构一.二叉树的顺序存储结构12345678910ABCDEFGHIJBT[1:15]123456789101112131415ABCDEFGHIJ

根据完全二叉树的性质

,对于深度为h的完全二叉树,将树中所有结点的数据信息按照编号的顺序依次存储到一维数组BT[1:2h-1]中,由于编号与数组的下标一一对应,该数组就是该完全二叉树的顺序存储结构.1.完全二叉树的顺序存储结构数据结构二叉树ppt全文共42页，当前为第14页。12345678910ABCDEFGHIJ111213BT[1:15]123456789101112131415ABCDEFGHJ

IABCDEFGHIJ2.一般二叉树的顺序存储结构数据结构二叉树ppt全文共42页，当前为第15页。2021/3/1116

对于一般二叉树,只须在二叉树中“添加”一些实际上二叉树中并不存在的“虚结点”

(可以认为这些结点的数据信息为空),使其在形式上成为一棵“完全二叉树”,然后按照完全二叉树的顺序存储结构的构造方法将所有结点的数据信息依次存放于数组BT[1:2h-1]中。数据结构二叉树ppt全文共42页，当前为第16页。二.二叉树的链式存储结构(二叉链表)链结点的构造为lchilddatarchild

其中,data为数据域

lchild

与rchild分别为指向左、右子树的指针域.ABCDEFGIJABCDEFGJIT^^^^^^^^^^数据结构二叉树ppt全文共42页，当前为第17页。6.3.3

二叉树的遍历数据结构二叉树ppt全文共42页，当前为第18页。二.前序遍历数据结构二叉树ppt全文共42页，当前为第19页。三.中序遍历数据结构二叉树ppt全文共42页，当前为第20页。四.后序遍历数据结构二叉树ppt全文共42页，当前为第21页。2021/3/1122ABCDKFGIJEH前序遍历序列:

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例数据结构二叉树ppt全文共42页，当前为第22页。2021/3/11236.3.2线索二叉树1.何谓线索二叉树？遍历结果是求得结点的一个线性序列。指向该线性序列“前驱”和“后继”的指针，称“线索”；包含“线索”的存储结构，称为“线索链表”；与其相应的二叉树，称为“线索二叉树”；对二叉树以某种次序遍历，使其变为线索二叉树的过程，称为“线索化”。数据结构二叉树ppt全文共42页，当前为第23页。2.线索链表中结点的结构在二叉链表的结点结构中增加两个标志域，并规定：lchildLTagdataRTagrchild其中：LTag=0lchild域指示结点的左孩子1lchild域指示结点的前驱RTag=0rchild域指示结点的右孩子1rchild域指示结点的后继数据结构二叉树ppt全文共42页，当前为第24页。2021/3/1125二叉树二叉线索存储表示typedefenum{Link,Thread}PointerThr;

//Link==0:指针，Thread==1:线索typedefstructBiThrNode{TElemTypedata;StructBiThrNode*lchild,*rchild;

//左右孩子指针

PointerThrLTag,RTag;//左右标志}BiThrNode,*BiThrTree;数据结构二叉树ppt全文共42页，当前为第25页。2021/3/11263.线索二叉树图例

线索二叉树及其存储结构（a）中序线索二叉树（b）中序线索链表1234567010020131141050161171thrt0

1数据结构二叉树ppt全文共42页，当前为第26页。2021/3/1127如何在线索树中找结点的后继？结合中序线索树若其右标志为“1”，右链是线索，右链直接指示了结点的后继；若其右标志为“0”，右链是指针，其后继为右子树中最左下的结点。1234567数据结构二叉树ppt全文共42页，当前为第27页。2021/3/1128如何在线索树中找结点的前驱？结合中序线索树

若其左标志为“1”，左链为线索，直接指示其前驱；若其左标志为“0”，左子树中最右下的结点为其前驱。1234567数据结构二叉树ppt全文共42页，当前为第28页。2021/3/1129线索链表的中序遍历算法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_T010020131141050161171T011数据结构二叉树ppt全文共42页，当前为第29页。2021/3/11306.4.2森林和二叉树的转换1.树和二叉树的对应关系由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。数据结构二叉树ppt全文共42页，当前为第30页。2021/3/1131数据结构二叉树ppt全文共42页，当前为第31页。2021/3/1132树转换为二叉树方法：1）对每个孩子进行从左到右的排序；2）在兄弟之间加一条连线；3）对每个结点，除了左孩子外，去除其与其余孩子之间的联系；4）以根结点为轴心，将整个树顺时针转45°。数据结构二叉树ppt全文共42页，当前为第32页。2021/3/1133ABCDEGHFIaABCDEGHFIbABCDEGHFIcABCDEGHFId数据结构二叉树ppt全文共42页，当前为第33页。2021/3/11342.森林和二叉树的对应关系从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树必空。若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可导出森林和二叉树的对应关系。数据结构二叉树ppt全文共42页，当前为第34页。2021/3/1135数据结构二叉树ppt全文共42页，当前为第35页。2021/3/1136BCDEGHFIaBCDEGHFIbBCDEGHFIcBCDEGHFId数据结构二叉树ppt全文共42页，当前为第36页。2021/3/1137已知条件：森林和二叉树的对应关系设森林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之外的森林数据结构二叉树ppt全文共42页，当前为第37页。2021/3/11386.4.3树和森林的遍历1.树的遍历：有三条搜索路径先根(序)遍历：若树不空，则先访问根结点，然后依次先根遍历各棵子树。后根(序)遍历：若树不空，则先依次后根遍历各棵子树，然后访问根结点。按层次遍历：若树不空，则自上而下自左至右访问树中每个结点。数据结构二叉树ppt全文共42页，当前为第38页。2021/3/1139