数据结构JAVA版课件共30页

ThecourseofelaborationforDataStructures数据结构(JAVA版)YT_JAVA烟台职业学院精品课第7章树和二叉树树1二叉树2二叉树的存储结构3树转换成二叉树5线索二叉树6二叉树的遍历47．1树树的定义树是由一个或多个结点构成的有限集合。每棵树必有一个称做根的结点。根结点可以有零个以上的子结点，而各子结点也可为子树。树的有关术语根结点(root)一棵树中没有父结点的结点叶结点或终端结点(leafnode)没有子结点的结点非终端结点(nonterminal)除了叶结点以外的其他结点父结点(parent)和子结点(child)若结点X有一个以结点Y为树根的子树，则X为Y的父结点，而Y就是X的子结点兄弟(sibling)同一个父结点的结点分支度(degree)每个结点的子结点数高度(height)或深度(depth)一棵树中最大层数祖先(ancestor)由结点X到根结点路径上所有的结点森林(forest)n≥0个树的集合7.2二叉树二叉树（Binarytree）的递归定义二叉树是有n个结点组成的有限集合，n=0时为空二叉树；n0时，二叉树是由有一个根结点和两棵互不相交的、分别称为左子树和右子树构成。二叉树有一种有序树。两棵不同的二叉树:ADGECF(a)(b)BADGECFB7．2．2二叉树的性质二叉树的第I层上最多有2i-1个结点在深度为k的二叉树中，最大结点数为2k-1个结点二叉树中，若叶子结点数为n0，度为2的结点数为n2，则有n0=n2+1若一棵完全二叉树有有n个结点，则其深度为k=∟log2n」+1一棵深度为k的满二叉树是具有2k-1个结点的二叉树。对满二叉树进行编号，从根结点开始，自上而下，自左到右编号。若一棵具有n个结点深度为k的二叉树，若每个结点都与深度为k的满二叉树编号为1～n一一对应，则称此二叉树为完全二叉树。若将一棵具有n个结点的完全二叉树，对于编号为i的结点，有如下特点：若i=1，则i为根结点，无双亲；否则i结点的双亲编号为i/2的结点。若2i≤n，则i的左孩子编号为2i，否则i无左孩子。若2i+1≤n，则i的右孩子编号为2i+1，否则i无右孩子。7.3二叉树的存储结构二叉树的顺序存储结构(适合于完全二叉树)非完全二叉树的顺序存储结构如下图ABCDEFG(a)(b)ABCDEFGABCDEFG∧∧∧∧∧∧(c)0124591236781011下标数组7.3二叉树的存储结构二叉树的链式存储结构二叉链式存储结构的每个结点包含三个域:Root指向二叉树的根结点。若二叉树为空，则root=null。在一棵有n个结点的链式存储的二叉树中，有n+1个空链域。dataleftChildrightChild7.3二叉树的存储结构(1)不带头结点的二叉树;(2)带头结点的二叉树ABCDEFG∧∧∧∧∧∧∧∧(a)ABCDEFG∧∧∧∧∧∧∧∧(b)rootroot∧7.3二叉树的存储结构声明二叉树类二叉树的结点类Packageds_java;Publicclasstreenodel{Publicstringdata;Publictreenode1left,right;Publictreenode1(){This(“?”);}Publictreenode1(stringd){Data=d;Left=right=null;}}7.4二叉树的遍历遍历二叉树就是按照一定的规则访问二叉树中所有的结点，并且每个结点仅被访问一次。所谓的访问，是指对每个结点数据进行查询、修改等操作。若对子树的访问按“先左后右”的次序进行，则遍历二叉树有三种方法：先根遍历：访问根结点，先根遍历左子树，先根遍历右子树。中根遍历：中根遍历左子树，访问根结点，中根遍历右子树。后根遍历：后根遍历左子树，后根遍历右子树，访问根结点。7.4二叉树的遍历实例ABCDE可得到上面二叉树先根遍历的顺序为：ABDCE中根遍历上图得到的顺序为：BDAEC后根遍历上面的二叉树得到的序列为：DBECA7.4二叉树的遍历程序实现先根遍历递归程序publicstaticvoidPreOrder（intPointer）{if（Pointer！=-1）//遍历的终止条件{//处理打印节点内容System.out.print(“”+TreeData[Pointer]+””)；PreOrder（LeftNode[Pointer]）；//处理左子树PreOrder（RightNode[Pointer]）；//处理右子树}}7.4二叉树的遍历程序实现中序遍历递归程序publicstaticvoidInOrder（intPointer）{if（Pointer！=-1）//遍历的终止条件{//处理打印节点内容InOrder（LeftNode[Pointer]）；//处理左子树System.out.print(“”+TreeData[Pointer]+””)；InOrder（RightNode[Pointer]）；//处理右子树}}7.4二叉树的遍历后根遍历递归程序:publicstaticvoidPostOrder（intPointer）{if（Pointer！=-1）//遍历的终止条件{//处理打印节点内容PostOrder（LeftNode[Pointer]）；//处理左子树PostOrder（LeftNode[Pointer]）；//处理左子树System.out.print(“”+TreeData[Pointer]+””)；}}7.4.3二叉树的非递归算法以中根遍历为例中根遍历二叉树的非递归算法描述如下：设置一个栈为空；从二叉树根结点P开始，若P不空或栈不空，循环执行以下操作，直到走完二叉树或栈为空为止。若P不空，将P进栈，进入左子树；若P不空并且栈不空，出栈P，访问P结点，再进入P的右子树。算法实现:Tree5类继承tree2类，以表明空子树的先根次序建立一棵二叉树。设计一个栈stack1，元素是object对象，栈元素是二叉树的结点类treenode1。程序中将出栈的object对象强制转换为treenode1对象。7.4.3二叉树的非递归算法Publicvoidinordertraver(){Stack1s1=newstack1(20);Treenode1p=root;Syatem.out.print(“中根次序：“);While(p||!s1.isempty())If(p){S1.push(p);P=p.left;}Else{P=(treenode1)s1.pop();System.out.print(p.data+”“);P=p.right;}System.out.println();}7.4.4二叉树的按层遍历二叉树的层序遍历算法如下：（1）初始化设置一个队列；（2）把根结点指针入队列；（3）当队列非空时，循环执行以下步骤:（a）出队列取得当前队头结点，访问该结点；（b）若该结点的左孩子结点非空，则将该结点的左孩子结点指针入队列；（c）若该结点的右孩子结点非空，则将该结点的右孩子结点指针入队列；（4）结束。7.4.4二叉树的按层遍历publicclassBiTrLeIteratorextendsBiTreeInterator{LinQueueq=newLinQueue();BiTrLeIterator(BiTreeNodet){super(t);}publicvoidreset(){if(root==null)iteComplete=1;elseiteComplete=0;if(root==null)return;current=root;try{if(root.getLeft()!=null)q.append(root.getLeft());if(root.getRight()!=null)q.append(root.getRight());}catch(Exceptione){e.printStackTrace();}}7.4.4二叉树的按层次遍历publicvoidnext(){if(iteComplete==1){System.out.println(已到二叉树尾！);return;}if(!q.isEmpty()){try{current=(BiTreeNode)q.delete();if(current.getLeft()!=null)q.append(current.getLeft());if(current.getRight()!=null)q.append(current.getRight());}catch(Exceptione){e.printStackTrace();}}elseiteComplete=1;}}7.5树转换成二叉树将一般树转换成二叉树，要将n个分支变成2个分支，主要有4步：(1)保留所有结点与其左子树的链接(2)连结所有兄弟结点神志神志神志(3)打断所有结点原本与右子树的链接(4)将兄弟结点顺时针转450二叉树还原为树的方法是：（1）若某结点是其双亲结点的左孩子，则把该结点的右孩子、右孩子的右孩子……都与该结点的双亲结点用线连起来。（2）删除原二叉树中所有双亲结点与右孩子结点的连线。（3）整理所有保留的和添加的连线，使每个结点的所有孩子结点位于相同层次高度。7.5树转换成二叉树树转换为二叉树的过程ABCDEFGABCDEFGABCDEFGABEFCDG(a)(b)(c)(d)7.6线索二叉树在链式存储结构的二叉树中，若结点的子树为空，则指向孩子的链就为空。因此，具有n个结点的二叉树，在总共2n个链中，只需要n-1个链，其余n+1个链为空。将这n+1个链指向结点的前驱或后继，构成线索二叉树。指向前驱或后继的链成为线索。对二叉树以某中次序遍历加线索的过程成为线索化。线索二叉树中，原非空链保持不变，仍然指向其左右孩子的结点，原来空的left指向该结点的前驱，原来空的right指向该结点的后继。为了区别链到底是指向孩子还是线索，需要增加两个状态位ltag和rtag，用来标记链的状态.7.6线索二叉树中序线索二叉树设root指向一棵二叉树的根结点，p指向某个结点，front指向P的前驱。P从根结点开始，当P非空时，执行下面的操作：中序线索P结点的左子树;如果P的左子树为空，设置P的left指向前驱结点front的线索，p.ltag标记为1如果P的右子树为空，设置前驱结点front的right指向p的线索，p.rtag标记为1Front指向P中序线索P的右子树7.6线索二叉树示例AEFCBDG(a)7.6线索二叉树中序线索二叉树7.6线索二叉树二叉树中序线索化Protectedthreadtreenodefront=null;Publicvoidinthreadnode(threadtreenodep){If(p){Inthreadtreenode(p.left);If(p.left==null){p.ltag=1;p.left=front;}If(p.right==null)p.rtag=1;If(front!=null&&front.rtag==1)front.right=p;If(front!=null)instr=instr+”front=”front.data+”\t”;Elseinstr=instr+”front=null”;instr=instr+”p=”+p.data+”\r\n”;front=p;inthreadtreenode(p.right);}}Publicvoidinorderthread(){Front=null;Inthreadtreenode(root);}7.6线索二叉树遍历中序线索二叉树寻找第一个访问结点，它是根左子树最左边的结点P;访问P结点，再找P的后继结点;重复执行上面的步骤.在线索二叉树threadtree1类中，增加inordertraver()方法，调用i