数据结构与算法分析5

第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（M≥0）个互不相交的集合，其中每一个集合都是一棵树，并称其为根的子树。5.1树的概念•5.1.2基本术语•一个结点的子树个数称为该结点的度（degree）•一棵树中结点度的最大值称为该树的度•度为零的结点称为叶子（leaf）或者终端结点•度不为零的结点称为分支结点或者非终端结点•除根结点之外的分支结点统称为内部结点•树中结点的后继结点称为儿子（child）或者儿子结点，简称儿子•结点的前驱结点称为儿子的双亲（parents）或者父亲结点，简称父亲•同一个父亲的儿子互称为兄弟（sibling）5.1树的概念•若树中存在一个结点序列k1k2k3…kj，使得ki是ki+1的父亲（1≤i＜j），则称该结点序列是从k1到kj的一条路径（path）或者道路•路径的长度等于j-1，它是该路径所经过的边（即连接两个结点的线段）的数目•若树中结点k到ks存在一条路径，则称k是ks的祖先（Ancestor），ks是k的子孙（Descendant）•结点的层数（level）是从根开始算起的。设根结点的层数为1，其余结点的层数等于其父亲结点的层数加1•树中结点的最大层数称为树的高度（Height）或者深度（Depth）5.1树的概念•若把树中每个结点的各子树看成从左到右有次序的（即不能互换），则称该树为有序树（OrderedTree）；否则称为无序树（UnorderedTree）•森林（Forest）是m（m≥0）棵互不相交树的集合•树形结构是非线性结构•祖先与子孙的关系则是对父子关系的延伸，其定义了树中结点的纵向次序•如果规定k1和k2是兄弟，且k1在k2的左边，则k1的任一子孙都在k2的任一子孙的左边，则定义了树中结点的横向次序5.2二叉树的定义•二叉树是由n（n≥0）结点的有限集合，此集合或者为空，或者由一个根结点加上两棵分别称为左、右子树的，互不相交的二叉树组成•二叉树可以为空集，因此根可以有空的左子树或者右子树，亦或者左、右子树皆为空•从二叉树定义中可以看出，二叉树结构与一般树结构区别如下：（1）二叉树可以为空树，即不包含任何结点；一般树至少应有一个结点。（2）二叉树区别于度数为2的有序树，在二叉树中允许某些结点只有右子树而没有左子树；而有序树中，一个结点如果没有第一子树就不可能有第二子树的存在。5.3二叉树的性质•5.3.1二叉树性质•性质1二叉树第i（i≥1）层上的结点数最多为2i-1•性质2高度为k的二叉树最多有2k-1个结点•性质3对任何二叉树T，设n0、n1、n2分别表示度数为0、1、2的结点个数，则n0=n2+11log2n5.3二叉树的性质•性质4具有n个结点的完全二叉树（包括满二叉树）的高度为（或者）•性质5满二叉树原理非空满二叉树的叶结点数等于其分支结点数加1•性质6一棵非空二叉树空子树的数目等于其结点数目加11log2n1log2n5.3二叉树的性质•5.3.2二叉树的抽象数据类型•下列给出一个二叉树结点的JAVA接口，称之为BinNode。BinNode类中存储了指向Object类的引用。创建二叉树时，可以根据需要而采用实际的数据类型。成员函数包括返回元素的值，返回左、右结点指针，设置元素的值，以了标志该结点是否为叶结点。•interfaceBinNode{//二叉树结点的抽象数据类型•//返回并设置元素值•publicObjectelement();•publicObjectsetElement(Objectv);5.3二叉树的性质•//返回并设置左孩子•publicBinnodeleft();•publicBinnodesetLeft(BinNodep);••//返回并设置右孩子•publicBinnoderight();•publicBinnodesetRight(BinNodep);••//判断是否为叶结点•publicbooleanisLeaf();•}//interfaceBinNode5.4二叉树的存储结构•5.4.1二叉树顺序存储结构•二叉树的顺序存储结构是把二叉树的所有结点按照一定的次序顺序存储到一组包含n个存储单元的空间中•二叉树顺序存储的原则是：不管给定的二叉树是不是完全二叉树，都看作完全二叉树，即按完全二叉树的层次次序（从上到下，从左到右）把各结点依次存入数组中5.4二叉树的存储结构•在顺序存储结构中，由某结点的存储单元地址可以推出其父亲、左儿子、右儿子及兄弟的地址，假设给定结点的地址为I，则：•（1）若I＝1，则该结点是为根结点，无父亲。•（2）若I≠1，则该结点的父亲结点地址为I／2的整数部分。•（3）若2×I≤n，则该结点的左儿子结点地址为2×I，否则该结点无左儿子。•（4）若2×I+1≤n，则该结点的右儿子结点地址为2×I+1，否则该结点无右儿子。•（5）若I为奇数（不为1），则该结点的左兄弟为I-1。•（6）若I为偶数（不为n），则该结点的右兄弟为I+1。5.4二叉树的存储结构•5.4.2二叉树的链接存储结构•二叉树的链接存储中每个结点由数据域和指针域两部分组成•二叉树每个结点的指针域有两个，一个指向左儿子，一个指向右儿子•还需一个链表的头指针指向根结点•二叉树的链接存储结构也称为二叉链表•若二叉树为空，则根结点为NULL5.4二叉树的存储结构•5.4.3二叉树的实现举例•1．以数组方式实现二叉树•先依次序输入元素值，一一建立二叉树数组，其中根结点的下标为1，其余结点的建立则遵循左小（level*2）右大（level*2+1）的原则，最后输出所建立二叉树的结点内容。••importConsoleReader.*;//引入数据输入类••publicclassbitree01•{•publicstaticvoidmain(Stringargs[])5.4二叉树的存储结构•{•inti；//循环变量•intIndex=1;//数组下标变量•intData;//读取输入值的临时变量•BiTreeArrayBiTree=newBitreeArray();//声明二叉树数组•System.out.printin(“请输入二叉树数据元素（输入0退出！）:”);••ConsoleReaderconsole=newConsoleReader(System.in);•do//依次序读取结点值•{•System.out.print(“Data”+Index+”:”);•Data=console.readInt();•Bitree.Create(Data);//建立二叉树•Index++;•}while(Data!=0);5.4二叉树的存储结构•BiTree.PrintAll();//输出二叉树的结点值•}•}••classBiTreeArray•{•intMaxSize=16;•int[]ABiTree=newint[MaxSize];••publicvoidBiTreeArray()•{•inti;•for(i=0;iMaxSize;i++)•ABiTree[i]=0;•}5.4二叉树的存储结构•//建立二叉树•publicvoidCreate(intData)•{•inti;•intLevel;//树的层数••Level=1;//从层1开始建立••while(ABiTree[Level]!=0)//判断是否存在子树•{•ifDataABiTree[Level])//判断是左子树？还是右子树？•Level=Level*2;//左子树•else•Level=Level*2+1;//右子树•}•ABiTree[Level]=Data;//将元素值插入结点5.4二叉树的存储结构•//输出二叉树结点值•publicvoidPrintAll()•{•inti;•System.out.println(“二叉树结点值依次是：”)；•for(i=1;iMaxSize;i++)•{•System.out.print(“Node”+i);•System.out.println(“:[“+ABiTree[i]+”]”);•}•}•}5.4二叉树的存储结构•2．数组方式实现二叉树的链接存储•以下示例为以结点数组方式建立二叉树，并输出结点内容。依次序输入结点值，并存入数组中，再一一建立成二叉树数组，其中根结点的下标为0，其余结点的建立则遵守左字段存左子结点的下标，右字段存右子结点下标的原则，最后输出所建立二叉树的结点值。•importConsoleReader.*;//引入己定义的数据输入类••publicclassbitree02•{•publicstaticvoidmain(StringargS[])5.4二叉树的存储结构•{•inti;//循环变量•intindex=l;//数组下标变量•intdata;//输入值所使用的临时变量•BiTreeArrayBiTree=newBiTreeArray();//声明二叉树数组••System.out.println(’’请输入二叉树结点值(输入0退出0)：”);•ConsolReaderconsole=newConsoleReader(SyStem.in)；••System.out.print(“Data“+index+”：“);•Data=console.readInt();•BiTree.TreeData[0]=data；•index++；5.4二叉树的存储结构•while(true)//读取输入值•{•System.out.print(“Data“+index+”：“);•data=console.readInt()；•if(data==0)•break;•BiTree.Create(data);//建立二叉树•index++；•}•BiTree.PrintAll();//输出二叉树的内容•}•}5.4二叉树的存储结构•classBiTreeArray•{•intMaxSize=16;•int[]TreeData=newint[MaxSize];•int[]RightNode=newint[MaxSize];•int[]LeftNode=newint[MaxSize];••publicBiTreeArray()•{•inti;//循环变量•for(i=0;iMaxSize;i++)•{•TreeData[i]=0;•RightNode[i]=-1;•LeftNode[i]=-1;•}•}5.4二叉树的存储结构•//建立二叉树•publicvoidCreate(intdata)•{•inti;•intlevel=0;//树的层数•intPosition=0;••for(i=0;TreeData[i]!=0;i++)•TreeData[i]=data;•while(true)//寻找结点位置•{•//判断是左子树还是右子树•if(dataTreeData[Level])•//右子树是否有下一层•if(RightNode[level]!=-1)•level=RightNode[level];5.4二叉树的存储结构•else•{•Position=-1;//设置为右子树•break；•}•else•{•//左子树是否有下一阶层•if(LeftNode[level]!=-1)•level=LeftNode[level];•else•{•Position=1;//设置为左子树•break;•}•}•}5.4二叉树的存储结构•if(