数据结构与算法分析.ppt

《数据结构与算法分析.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法分析.ppt（47页珍藏版）》请在装配图网上搜索。

1、第5章 树,5.1 树的概念 5.2 二叉树的定义 5.3 二叉树的性质 5.4 二叉树的存储结构 5.5 二叉树的遍历 5.6 线索二叉树 5.7 树和二叉树的转换及树的存储结构 5.8 哈夫曼树及其应用,5.1 树的概念,5.1.1 树的定义 树是一种数据结构，表示为TREE=（D，R）； 其中：D是具有相同特性的数据元素的集合；R是元素集合D上的关系集合，如果D中只含有一个数据元素，则R为空集。 或者用递归定义为： 树是N（N0）个结点的有限集合，其唯一关系具有下列属性： 集合中存在唯一的一个结点，称为树根，该结点没有前驱；除根结点外，其余结点分为M（M0）个互不相交的集合，其中每一个集

2、合都是一棵树，并称其为根的子树。,5.1 树的概念,5.1.2 基本术语 一个结点的子树个数称为该结点的度（degree） 一棵树中结点度的最大值称为该树的度 度为零的结点称为叶子（leaf）或者终端结点 度不为零的结点称为分支结点或者非终端结点 除根结点之外的分支结点统称为内部结点 树中结点的后继结点称为儿子（child）或者儿子结点，简称儿子 结点的前驱结点称为儿子的双亲（parents）或者父亲结点，简称父亲 同一个父亲的儿子互称为兄弟（sibling）,5.1 树的概念,若树中存在一个结点序列k1k2k3kj，使得ki是ki+1的父亲（1ij），则称该结点序列是从k1到kj的一条路径（

3、path）或者道路 路径的长度等于j-1，它是该路径所经过的边（即连接两个结点的线段）的数目 若树中结点k到ks存在一条路径，则称k是ks的祖先（Ancestor），ks是k的子孙（Descendant） 结点的层数（level）是从根开始算起的。设根结点的层数为1，其余结点的层数等于其父亲结点的层数加1 树中结点的最大层数称为树的高度（Height）或者深度（Depth）,5.1 树的概念,若把树中每个结点的各子树看成从左到右有次序的（即不能互换），则称该树为有序树（Ordered Tree）；否则称为无序树（Unordered Tree） 森林（Forest）是m（m0）棵互不相交树的集合

4、 树形结构是非线性结构 祖先与子孙的关系则是对父子关系的延伸，其定义了树中结点的纵向次序 如果规定k1和k2是兄弟，且k1在k2的左边，则k1的任一子孙都在k2的任一子孙的左边，则定义了树中结点的横向次序,5.2 二叉树的定义,二叉树是由n（n0）结点的有限集合，此集合或者为空，或者由一个根结点加上两棵分别称为左、右子树的，互不相交的二叉树组成 二叉树可以为空集，因此根可以有空的左子树或者右子树，亦或者左、右子树皆为空 从二叉树定义中可以看出，二叉树结构与一般树结构区别如下： （1）二叉树可以为空树，即不包含任何结点；一般树至少应有一个结点。 （2）二叉树区别于度数为2的有序树，在二叉树中允许

5、某些结点只有右子树而没有左子树；而有序树中，一个结点如果没有第一子树就不可能有第二子树的存在。,5.3 二叉树的性质,5.3.1 二叉树性质 性质1 二叉树第i（i1）层上的结点数最多为2i-1 性质2 高度为k的二叉树最多有2k-1个结点 性质3 对任何二叉树T，设n0、n1、n2分别表示度数为0、1、2的结点个数，则n0=n2+1,5.3 二叉树的性质,性质4 具有n个结点的完全二叉树（包括满二叉树）的高度为 （或者 ） 性质5 满二叉树原理 非空满二叉树的叶结点数等于其分支结点数加1 性质6 一棵非空二叉树空子树的数目等于其结点数目加1,5.3 二叉树的性质,5.3.2 二叉树的抽象数据

6、类型 下列给出一个二叉树结点的JAVA接口，称之为BinNode。BinNode类中存储了指向Object类的引用。创建二叉树时，可以根据需要而采用实际的数据类型。成员函数包括返回元素的值，返回左、右结点指针，设置元素的值，以了标志该结点是否为叶结点。 interface BinNode /二叉树结点的抽象数据类型 /返回并设置元素值 public Object element(); public Object setElement(Object v);,5.3 二叉树的性质,/返回并设置左孩子 public Binnode left(); public Binnode setLeft(Bin

7、Node p); /返回并设置右孩子 public Binnode right(); public Binnode setRight(BinNode p); /判断是否为叶结点 public boolean isLeaf(); /interface BinNode,5.4 二叉树的存储结构,5.4.1 二叉树顺序存储结构 二叉树的顺序存储结构是把二叉树的所有结点按照一定的次序顺序存储到一组包含n个存储单元的空间中 二叉树顺序存储的原则是：不管给定的二叉树是不是完全二叉树，都看作完全二叉树，即按完全二叉树的层次次序（从上到下，从左到右）把各结点依次存入数组中,5.4 二叉树的存储结构,在顺序存储

8、结构中，由某结点的存储单元地址可以推出其父亲、左儿子、右儿子及兄弟的地址，假设给定结点的地址为I，则： （1）若I1，则该结点是为根结点，无父亲。 （2）若I1，则该结点的父亲结点地址为I2的整数部分。 （3）若2In，则该结点的左儿子结点地址为2I，否则该结点无左儿子。 （4）若2I+1n，则该结点的右儿子结点地址为2I+1，否则该结点无右儿子。 （5）若I为奇数（不为1），则该结点的左兄弟为I-1。 （6）若I为偶数（不为n），则该结点的右兄弟为I+1。,5.4 二叉树的存储结构,5.4.2 二叉树的链接存储结构 二叉树的链接存储中每个结点由数据域和指针域两部分组成 二叉树每个结点的指针域

9、有两个，一个指向左儿子，一个指向右儿子 还需一个链表的头指针指向根结点 二叉树的链接存储结构也称为二叉链表 若二叉树为空，则根结点为NULL,5.4 二叉树的存储结构,5.4.3 二叉树的实现举例 1以数组方式实现二叉树 先依次序输入元素值，一一建立二叉树数组，其中根结点的下标为1，其余结点的建立则遵循左小（level*2）右大（level*2+1）的原则，最后输出所建立二叉树的结点内容。 import ConsoleReader.*; /引入数据输入类 public class bitree01 public static void main (String args),5.4 二叉树的存储

10、结构, int i； /循环变量 int Index=1; /数组下标变量 int Data; /读取输入值的临时变量 BiTreeArray BiTree=new BitreeArray(); /声明二叉树数组 System.out.printin(“请输入二叉树数据元素（输入0退出！）:”); ConsoleReader console=new ConsoleReader(System.in); do /依次序读取结点值 System.out.print(“Data”+Index+” : ”); Data=console.readInt(); Bitree.Create(Data); /建

11、立二叉树 Index+; while(Data!=0);,5.4 二叉树的存储结构,BiTree.PrintAll(); /输出二叉树的结点值 class BiTreeArray int MaxSize=16; int ABiTree=new intMaxSize; public void BiTreeArray() int i; for (i=0;iMaxSize;i+) ABiTreei=0; ,5.4 二叉树的存储结构,/建立二叉树 public void Create(int Data) int i; int Level; /树的层数 Level=1; /从层1开始建立 while(A

12、BiTreeLevel!=0) /判断是否存在子树 if DataABiTreeLevel) /判断是左子树？还是右子树？ Level=Level*2; /左子树 else Level=Level*2+1; /右子树 ABiTreeLevel=Data; /将元素值插入结点,5.4 二叉树的存储结构,/输出二叉树结点值 public void PrintAll() int i; System.out.println(“二叉树结点值依次是：”)； for (i=1;iMaxSize;i+) System.out.print(“Node”+i); System.out.println(“:“+AB

13、iTreei+”); ,5.4 二叉树的存储结构,2数组方式实现二叉树的链接存储 以下示例为以结点数组方式建立二叉树，并输出结点内容。依次序输入结点值，并存入数组中，再一一建立成二叉树数组，其中根结点的下标为0，其余结点的建立则遵守左字段存左子结点的下标，右字段存右子结点下标的原则，最后输出所建立二叉树的结点值。 import ConsoleReader.*; /引入己定义的数据输入类 public class bitree02 public static void main(String argS),5.4 二叉树的存储结构, int i; /循环变量 int index=l; /数组下标变

14、量 int data; /输入值所使用的临时变量 BiTreeArray BiTree=new BiTreeArray(); /声明二叉树数组 System.out.println(请输入二叉树结点值(输入0退出0)：”); ConsolReader console=new ConsoleReader(SyStem.in)； System.out.print(“Data “+index+” ： “); Data=console.readInt(); BiTree.TreeData0=data； index+；,5.4 二叉树的存储结构,while (true) /读取输入值 System.ou

15、t.print(“Data “+index+” ： “); data=console.readInt()； if (data=0) break; BiTree.Create(data); /建立二叉树 index+； BiTree.PrintAll(); /输出二叉树的内容 ,5.4 二叉树的存储结构,class BiTreeArray int MaxSize=16; int TreeData=new intMaxSize; int RightNode=new intMaxSize; int LeftNode=new intMaxSize; public BiTreeArray() int i

16、; /循环变量 for (i=0; iMaxSize; i+) TreeDatai=0; RightNodei=-1; LeftNodei=-1; ,5.4 二叉树的存储结构,/建立二叉树 public void Create(int data) int i; int level=0; /树的层数 int Position=0; for (i=0; TreeDatai!=0; i+) TreeDatai=data; while (true) /寻找结点位置 /判断是左子树还是右子树 if (data TreeDataLevel) /右子树是否有下一层 if (RightNodelevel!=-

17、1) level=RightNodelevel;,5.4 二叉树的存储结构,else Position=-1; /设置为右子树 break； else /左子树是否有下一阶层 if (LeftNodelevel!=-1) level=LeftNodelevel; else Position=1; /设置为左子树 break; ,5.4 二叉树的存储结构,if (Position=1) /建立结点的左右连结 LeftNodelevel=i; /连结左子树 else RightNodelevel=i; /连结右子树 /打印所有二叉树结点值 public void PrintAll() int i;

18、 System.out.println(“二叉树结点值：”); System.out.println(“ lchild data rchild”); for (i=0；iMaxSize；i+),5.4 二叉树的存储结构, if(TreeDatai!=0) System.out.print(“Node”+i); System.out.print(“ “+LeftNodei+”); System.out.print(“ “+TreeDatai+”); System.out.println(“ ”+RightNodei+”); ,5.5 二叉树的遍历,5.5.1 二叉树的前序遍历 “遍历”是抽取数据

19、结构中的各个数据值 前序遍历(Preorder traversal)是先遍历根结点，再遍历左子树，最后才遍历右子树 即若二叉树非空，则依次进行如下操作： （1） 访问根结点； （2） 前序遍历左子树； 前序遍历右子树。,5.5 二叉树的遍历,前序遍历(preorder)的递归算法如下： if 指向根结点的指针=NULL then 此为空树，遍历结束 else (1) 处理当前的结点 (2) 往左走，递归处理preorder(root-left) (3) 往右走，递归处理preorder(root-right) Java语言实现示例： void preorder(BinNode rt) /rt是

20、子树的根 if (rt = null) return; /空子树 visit(rt); preorder(rt.left(); preorder(rt.right(); ,5.5 二叉树的遍历,5.5.2 二叉树的中序遍历 中序遍历(Inorder traversal)是先遍历左子树，再遍历根结点，最后才遍历右子树 若二叉树非空，则依次序进行如下操作： (1)中序遍历左子树； (2)访问根结点； (3)中序遍历右子树。,5.5 二叉树的遍历,中序遍历(inorder)的递归算法如下： if 指向根结点的指针=NULL then 此为空树，遍历结束 else (1) 往左走，递归处理inorde

21、r(root-left) (2) 处理当前的结点 (3) 往右走，递归处理inorder(root-right) Java语言实现示例： void inorder(BinNode rt) /rt是子树的根 if (rt = null) return; /空子树 inorder(rt.left(); visit(rt); inorder(rt.right(); ,5.5 二叉树的遍历,5.5.3 二叉树的后序遍历 后序遍历(Postorder traversal)是先遍历左子树，再遍历右子树，最后才遍历根结点 若二叉树非空，则依次序进行如下操作： （1） 后序遍历左子树； （2） 后序遍历右子树

22、； （3） 访问根结点。,5.5 二叉树的遍历,后序遍历(postorder)的递归算法如下： if 指向根结点的指针=NULL then 此为空树，遍历结束 else (1) 往左走，递归处理postorder(root-left) (2) 往右走，递归处理postorder(root-right) (3) 处理目前的结点 Java语言实现示例： void postorder(BinNode rt) /rt是子树的根 if (rt = null) return; /空子树 postorder(rt.left(); postorder(rt.right(); visit(rt); ,5.5 二

23、叉树的遍历,5.5.4 二叉树的层次遍历 层次遍历是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。 对一棵非空的二叉树进行层次遍历，可按照如下步骤进行： 1初始化一个队列； 2二叉树的根结点放入队列； 3重复步骤47直至队列为空； 4从队列中取出一个结点x； 5访问结点x； 6如果x存在左子结点，将左子结点放入队列； 7如果x存在右子结点，将右子结点放入队列。,5.6 线索二叉树,5.6.1 二叉树的线索化 当我们对二叉树以某种方式遍历后，就可以得到二叉树中所有结点的一个线性序列，在这种意义下，二叉树中的结点就有了前趋结点和后继结点。 在大多

24、数情况下，寻找结点的前趋结点或后继结点都需要遍历二叉树。 为方便寻找二叉树中结点的前趋结点或后继结点，可以通过一次遍历记下各结点在遍历所得的线性序列中的相对位置 可以设法利用空指针域来存放结点的前驱结点和后继结点的指针信息，这种附加的指针称为“线索”。 加上了的二叉链表称为线索链表，相应的二叉树称为线索二叉树（Threaded Binary Tree）。,5.6 线索二叉树,为了区分一个结点的指针是指向其儿子的指针、还是指向其前趋或者后继的线索，可以在每个结点上增加两个线索标志域ltag和rtag 这样线索链表的结点结构为： 其中： 左线索标志 ltag=0；/lchild是指向结点的左儿子的

25、指针 ltag=1；/lchild是指向结点的前趋结点的左线索 右线索标志 rtag=0；/rchild是指向结点的右儿子的指针 rtag=1；/rchild是指向结点的后继结点的右线索 每个标志位令其只占一个bit，这样就只需增加很少的存储空间 一棵二叉树以某种方式遍历并使其变成线索二叉树的过程称为二叉树的线索化,5.6 线索二叉树,对同一棵二叉树遍历的方式不同，所得到的线索树也不同，二叉树有前序、中序和后序三种遍历方式，所以线索树也有前序线索二叉树、中序线索二叉树和后序线索二叉树三种 通常在二叉树中增加一个与树中结点相同类型的头结点，令头结点的信息域为空，其lchild域指向二叉树的根结点

26、，当二叉树为空时，lchild域值为空；其rchild域指向以某种方式遍历二叉树时最后访问的结点，当二叉树为空时，rchild域指向该结点本身，同时令原来指向二叉树根结点的头指针指向该头结点，以某种方式遍历二叉树时第一个被访问结点的左指针域和最后一个被访问结点的右指针域的值如果是线索，也指向该头结点。,5.6 线索二叉树,5.6.2 线索二叉树上的运算 下面以中序线索二叉树为例,讨论线索二叉树的运算 1建立一棵中序线索二叉树 2在中序线索二叉树上寻找任意结点的中序前驱结点 3在中序线索二叉树上寻找任意结点的中序后继结点。 4在中序线索二叉树中查找值为x的结点。 5在中序线索二叉树上插入结点。,

27、5.7 树和二叉树的转换及树的存储结构,5.7.1 树转换为二叉树 将一棵树转换为二叉树的方法是： 1树中所有相邻兄弟之间加一条连线； 2对树中的每个结点，只保留它与第一个儿子结点之间的连线，删去它与其它儿子结点之间的连线。 3以树的根结点为轴心，将整棵树顺时针转动一定的角度，使之结构层次分明。,5.7 树和二叉树的转换及树的存储结构,5.7.2 二叉树还原为树 树转换为二叉树这一转换过程是可逆的，可以依据二叉树的根结点有无右儿子结点，将一棵二叉树还原为树，具体方法如下： 1若某结点是其双亲的左儿子，则把该结点的右儿子、右儿子的右儿子、都与该结点的双亲结点用线连起来； 2删掉原二叉树中所有的双

28、亲结点与右儿子结点的连线； 3整理由(1)、(2)两步所得到的树，使之结构层次分明。,5.7 树和二叉树的转换及树的存储结构,5.7.3 森林转换为二叉树 森林是若干棵树的集合，森林亦可用二叉树表示。 森林转换为二叉树的方法如下： 1将森林中的每棵树转换成相应的二叉树； 2第一棵二叉树不动，从第二棵二叉树开始，依次序将后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有的二叉树连在一起后，这样所得到的二叉树就是由森林转换得到的二叉树。 设F=T1，T2，Tn是森林，其所对应的二叉树为B(T1，T2，Tn)，有： 1若n=0，即F为空，那么B亦为空； 2若n0，则二叉树的根结点为树T1的根

29、结点，其左子树为B(T11，T12，T1m)，其中T11，T12，T1m是根结点T1的子树，而其右子树为B(T2，T3，Tn)。,5.7 树和二叉树的转换及树的存储结构,5.7.4 树的遍历 1先根遍历 先根遍历的定义为： (1) 访问根结点； (2) 按照从左到右的顺序先根遍历根结点的每一棵子树。 2后根遍历 后根遍历的定义为： (1) 按照从左到右的顺序后根遍历根结点的每一棵子树； (2) 访问根结点。,5.7 树和二叉树的转换及树的存储结构,5.7.5 森林的遍历 1前序遍历 前序遍历的定义为： (1) 访问森林中第一棵树的根结点； (2) 前序遍历第一棵树的根结点的子树森林； (3)

30、前序遍历剩余的其他子森林。 2中序遍历 中序遍历的定义为： (1) 中序遍历第一棵树的根结点的子树森林； (2) 访问森林中第一棵的根结点； (3) 中序遍历剩余的其他子森林。,5.7 树和二叉树的转换及树的存储结构,5.7.6 树的存储结构 1双亲链表表示法 2孩子链表表示法 3双亲孩子链表表示法 4孩子兄弟链表表示法,5.8 哈夫曼树及其应用,5.8.1 哈夫曼树的基本概念 1路径和路径长度 在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。 若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。 2结点的权及带权路径长度 若

31、将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。 结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。 3树的带权路径长度 树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。,5.8 哈夫曼树及其应用,4给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。 5哈夫曼树的构造 假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为W1、W2、Wn,则哈夫曼树的构造规则为： (1)将W1、W2、Wn看成是有n棵树的森林(每棵树仅有一个结点)； (2)在森林中选出两个根结点的

32、权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； (3)从森林中删除选取的两棵树，并将新树加入森林； (4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为我们所求得的哈夫曼树。,5.8 哈夫曼树及其应用,5.8.2 哈夫曼树在编码问题中的应用 哈夫曼树可用于构造使电文的编码总长最短的编码方案 具体作法如下：设需要编码的字符集合为d1，d2，dn，而它们在电文中出现的次数或频率集合为w1，w2，wn，以d1，d2，dn作为叶结点，w1，w2，wn作为它们的权值构造一棵哈夫曼树，规定哈夫曼树中的左分支代表“0”，右分支代表“1”，则从根结点到每个叶结点所经过的路径分支组成的0或1序列便为该结点对应字符的编码，称之为哈夫曼编码。,5.8 哈夫曼树及其应用,在哈夫曼编码树中，树的带权路径长度的含义是各个字符的码长与其出现次数的乘积和，也就是电文的代码总长 因为哈夫曼算法构造的是带权路径长度最小的二叉树，所以采用哈夫曼树构造的编码是一种能使电文代码总长最短的不等长编码 在哈夫曼树中，由于每个字符结点都是叶结点，它们不可能在根结点到其它字符结点的路径上，所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀，从而保证了译码的非二义性。 实现哈夫曼编码的算法可分为两大部分，构造哈夫曼树和在哈夫曼树上求叶结点的编码。,