数据结构与算法分析

《数据结构与算法分析》由会员分享，可在线阅读，更多相关《数据结构与算法分析（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

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

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

5、）二叉树区别于度数为2的有序树，在二叉树中允许某 些结点只有右子树而没有左子树；而有序树中，一个结 点如果没有第一子树就不可能有第二子树的存在。 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 一棵非空二叉树空子树的数目等于 其结

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

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

8、 下，从左到右）把各结点依次存入数组中 5.4 二叉树的存储结构 在顺序存储结构中，由某结点的存储单元地址可以推出 其父亲、左儿子、右儿子及兄弟的地址，假设给定结点 的地址为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 p

10、ublic static void main (String args) 5.4 二叉树的存储结构 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+” : ”);

11、Data=console.readInt(); Bitree.Create(Data); /建立二叉树 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;i TreeDataLevel) /右子树是否有下一层 if (RightNodelevel!=-1) level=RightNodelevel; 5.4 二

12、叉树的存储结构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; System.out.println(“二叉树结点值：”); S

13、ystem.out.println(“ lchild data rchild”); for (i=0；ileft) (3) 往右走，递归处理preorder(root-right) Java语言实现示例： void preorder(BinNode rt) /rt是子树的根 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) 往左走，递归处理inorder(root-left) (2) 处理当前的结点 (3) 往右走，递归处理inorder(root-right) Java语言实现示例： void inorder(BinNode rt) /rt是子树的根 if (rt = null) return; /空子树 inorder(rt.left(