The course of elaboration for Data Structures 数据结构数据结构(JAVA版版)www.YT_JAVA.com烟台职业学院精品课第第7章章 树和二叉树树和二叉树树树 1二叉树二叉树 2二叉树的存储结构二叉树的存储结构 3树转换成二叉树树转换成二叉树 5线索二叉树线索二叉树 6二叉树的遍历二叉树的遍历 471 树树v树的定义树的定义 树是由一个或多个结点构成的有限集合每棵树必有一个称做根的结点树是由一个或多个结点构成的有限集合每棵树必有一个称做根的结点根结点可以有零个以上的子结点，而各子结点也可为子树根结点可以有零个以上的子结点，而各子结点也可为子树v树的有关术语树的有关术语l 根结点根结点(root)一棵树中没有父结点的结点一棵树中没有父结点的结点l 叶结点或终端结点叶结点或终端结点(leaf node)没有子结点的结点没有子结点的结点l 非终端结点非终端结点(nonterminal)除了叶结点以外的其他结点除了叶结点以外的其他结点l 父结点父结点(parent)和子结点和子结点(child)若结点若结点X有一个以结点有一个以结点Y为树根为树根的子树，则的子树，则X为为Y的父结点，而的父结点，而Y就是就是X的子结点的子结点l 兄弟兄弟(sibling)同一个父结点的结点同一个父结点的结点l 分支度分支度(degree)每个结点的子结点数每个结点的子结点数l 高度高度(height)或深度或深度(depth)一棵树中最大层数一棵树中最大层数l 祖先祖先(ancestor)由结点由结点X到根结点路径上所有的结点到根结点路径上所有的结点l 森林森林(forest)n0个树的集合个树的集合7.2 二叉树二叉树v 二叉树（二叉树（Binary tree）的递归定义）的递归定义 二叉树是有二叉树是有n个结点组成的有限集合，个结点组成的有限集合，n=0时为空二时为空二叉树；叉树；n0时，二叉树是由有一个根结点和两棵互不相时，二叉树是由有一个根结点和两棵互不相交的、分别称为左子树和右子树构成。
二叉树有一种有序交的、分别称为左子树和右子树构成二叉树有一种有序树两棵不同的二叉树两棵不同的二叉树:A ADGECF(a)(b)B BA ADGECFB B722 二叉树的性质二叉树的性质v二叉树的第二叉树的第I 层上最多有层上最多有2i-1个结点个结点v在深度为在深度为k的二叉树中，最大结点数为的二叉树中，最大结点数为2k-1个结点个结点v二叉树中，若叶子结点数为二叉树中，若叶子结点数为n0，度为，度为2的结点数为的结点数为n2，则有，则有n0=n2+1v若一棵完全二叉树有有若一棵完全二叉树有有n个结点，则其深度为个结点，则其深度为k=log2n+1v一棵深度为一棵深度为k的满二叉树是具有的满二叉树是具有2k-1个结点的二叉树个结点的二叉树对满二叉树进行编号，从根结点开始，自上而下，自左到右编号对满二叉树进行编号，从根结点开始，自上而下，自左到右编号若一棵具有若一棵具有n个结点深度为个结点深度为k的二叉树，若每个结点都与深度为的二叉树，若每个结点都与深度为k的的满二叉树编号为满二叉树编号为1n一一对应，则称此二叉树为一一对应，则称此二叉树为完全二叉树完全二叉树v若将一棵具有若将一棵具有n个结点的完全二叉树，对于编号为个结点的完全二叉树，对于编号为i的结点，有如下的结点，有如下特点：特点：若i=1，则i为根结点，无双亲；否则i结点的双亲编号为i/2的结点。
若2in，则i的左孩子编号为2i，否则i无左孩子若2i+1n，则i的右孩子编号为2i+1，否则i无右孩子7.3 二叉树的存储结构二叉树的存储结构v 二叉树的顺序存储结构二叉树的顺序存储结构(适合于完全二叉树适合于完全二叉树)非完全二叉树的顺序存储结构如下图 7.3 二叉树的存储结构二叉树的存储结构v 二叉树的链式存储结构二叉树的链式存储结构 二叉链式链式存储结构的每个结点包含三个域:Root指向二叉树的根结点若二叉树为空，则root=null在一棵有n个结点的链式存储的二叉树中，有n+1个空链域dataleftChildrightChild7.3 二叉树的存储结构二叉树的存储结构(1)不带头结点的二叉树不带头结点的二叉树;(2)带头结点的二叉树带头结点的二叉树ABCDEFG (a)ABCDEFG (b)rootroot 7.3 二叉树的存储结构二叉树的存储结构v声明二叉树类声明二叉树类 二叉树的结点类二叉树的结点类 Package ds_java;Public class treenodel Public string data;Public treenode1 left,right;Public treenode1()This(“?”);Public treenode1(string d)Data=d;Left=right=null;7.4 二叉树的遍历二叉树的遍历v 遍历二叉树就是按照一定的规则访问二叉树中遍历二叉树就是按照一定的规则访问二叉树中所有的结点，并且每个结点仅被访问一次。
所谓所有的结点，并且每个结点仅被访问一次所谓的访问，是指对每个结点数据进行查询、修改等的访问，是指对每个结点数据进行查询、修改等操作v若对子树的访问按若对子树的访问按“先左后右先左后右”的次序进行，则的次序进行，则遍历二叉树有三种方法：遍历二叉树有三种方法：l 先根遍历：访问根结点，先根遍历左子树，先根先根遍历：访问根结点，先根遍历左子树，先根遍历右子树遍历右子树l 中根遍历：中根遍历左子树，访问根结点，中根中根遍历：中根遍历左子树，访问根结点，中根遍历右子树遍历右子树l 后根遍历：后根遍历左子树，后根遍历右子树，后根遍历：后根遍历左子树，后根遍历右子树，访问根结点访问根结点7.4 二叉树的遍历二叉树的遍历实例实例 ABCDE可得到上面二叉树先根遍历的顺序为：ABDCE中根遍历上图得到的顺序为：BDAEC后根遍历上面的二叉树得到的序列为：DBECA7.4 二叉树的遍历二叉树的遍历v 程序实现程序实现 先根遍历递归程序先根遍历递归程序 public static void PreOrder（int Pointer）if（Pointer！=-1）/遍历的终止条件遍历的终止条件 /处理打印节点内容处理打印节点内容 System.out.print(“”+TreeDataPointer+”)；PreOrder（LeftNodePointer）；）；/处理左子树处理左子树 PreOrder（RightNodePointer）；）；/处理右子树处理右子树 7.4 二叉树的遍历二叉树的遍历v 程序实现程序实现 中序遍历递归程序中序遍历递归程序 public static void InOrder（int Pointer）if（Pointer！=-1）/遍历的终止条件遍历的终止条件 /处理打印节点内容处理打印节点内容 InOrder（LeftNodePointer）；）；/处理左子树处理左子树 System.out.print(“”+TreeDataPointer+”)；InOrder（RightNodePointer）；）；/处理右子树处理右子树 7.4 二叉树的遍历二叉树的遍历后根遍历递归程序后根遍历递归程序:public static void PostOrder（int Pointer）if（Pointer！=-1）/遍历的终止条件遍历的终止条件 /处理打印节点内容处理打印节点内容 PostOrder（LeftNodePointer）；）；/处理左子树处理左子树 PostOrder（LeftNodePointer）；）；/处理左子树处理左子树 System.out.print(“”+TreeDataPointer+”)；7.4.3 二叉树的非递归算法二叉树的非递归算法v以中根遍历为例以中根遍历为例 中根遍历二叉树的非递归算法描述如下：设置一个中根遍历二叉树的非递归算法描述如下：设置一个栈为空；从二叉树根结点栈为空；从二叉树根结点P开始，若开始，若P不空或栈不空，循不空或栈不空，循环执行以下操作，直到走完二叉树或栈为空为止。
环执行以下操作，直到走完二叉树或栈为空为止l 若若P不空，将不空，将P进栈，进入左子树；进栈，进入左子树；l 若若P不空并且栈不空，出栈不空并且栈不空，出栈P，访问，访问P结点，再进入结点，再进入P的右的右子树算法实现算法实现:Tree5类继承类继承tree2类，以表明空子树的先根次序建立类，以表明空子树的先根次序建立一棵二叉树一棵二叉树设计一个栈设计一个栈stack1，元素是，元素是object对象，栈元素是二对象，栈元素是二叉树的结点类叉树的结点类treenode1程序中将出栈的程序中将出栈的object对对象强制转换为象强制转换为treenode1对象对象7.4.3 二叉树的非递归算法二叉树的非递归算法 Public void inordertraver()Stack1 s1=new stack1(20);Treenode1 p=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 二叉树的按层遍历二叉树的按层遍历v二叉树的层序遍历算法如下二叉树的层序遍历算法如下：（1）初始化设置一个队列；（2）把根结点指针入队列；（3）当队列非空时，循环执行以下步骤:（a）出队列取得当前队头结点，访问该结点；（b）若该结点的左孩子结点非空，则将该结点的左孩子结点指针入队列；（c）若该结点的右孩子结点非空，则将该结点的右孩子结点指针入队列；（4）结束。
7.4.4 二叉树的按层遍历二叉树的按层遍历 public class BiTrLeIterator extends BiTreeInterator LinQueue q=new LinQueue();BiTrLeIterator(BiTreeNode t)super(t);public void reset()if(root=null)iteComplete=1;else iteComplete=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(Exception e)e.printStackTrace();7.4.4 二叉树的按层次遍历二叉树的按层次遍历 public void next()if(iteComplete=1)System.out.println(已到二叉树尾！已到二叉树尾！);return;if(!q.isEmpty()trycurrent=(BiTreeNode)q.delete();if(current.getLeft()!=null)q.append(current.getLeft();if(current.getRight()!=null)q.append(current.getRight();catch(Exception e)e.printStackTrace();else iteComplete=1;7.5 树转换成二叉树树转换成二叉树v 将一般树转换成二叉树，要将将一般树转换成二叉树，要将n个分支变成个分支变成2个个分支，主要有分支，主要有4步：步：(1)保留所有结点与其左子树的链接 (2)连结所有兄弟结点神志神志神志 (3)打断所有结点原本与右子树的链接 (4)将兄弟结点顺时针转450v二叉树还原为树的方法是：二叉树还原为树的方法是：（1）若某结点是其双亲结点的左孩子，则把该结点的右孩子、右孩子的右孩子都与该结点的双亲结点用线连起来。
2）删除原二叉树中所有双亲结点与右孩子结点的连线3）整理所有保留的和添加的连线，使每个结点的所有孩子结点位于相同层次高度7.5 树转换成二叉树树转换成二叉树v 树转换为二叉树的过程树转换为二叉树的过程ABCDEFGABCDEFGABCDEFGABEFCDG(a)(b)(c)(d)7.6 线索二叉树线索二叉树v在链式存储结构的二叉树中，若结点的子树为空，在链式存储结构的二叉树中，若结点的子树为空，则指向孩子的链就为空因此，具有则指向孩子的链就为空因此，具有n个结点的个结点的二叉树，在总共二叉树，在总共2n个链中，只需要个链中，只需要n-1个链，其个链，其余余n+1个链为空个链为空将这将这n+1个链指向结点的前个链指向结点的前驱或后继，构成线索二叉树指向前驱或后继的驱或后继，构成线索二叉树指向前驱或后继的链成为线索对二叉树以某中次序遍历加线索的链成为线索对二叉树以某中次序遍历加线索的过程成为线索化过程成为线索化v线索二叉树中，原非空链保持不变，仍然指向其线索二叉树中，原非空链保持不变，仍然指向其左右孩子的结点，原来空的左右孩子的结点，原来空的left指向该结点的前指向该结点的前驱，原来空的驱，原来空的right指向该结点的后继。
指向该结点的后继为了区为了区别链到底是指向孩子还是线索，需要增加两个状别链到底是指向孩子还是线索，需要增加两个状态位态位ltag和和rtag，用来标记链的状态，用来标记链的状态.7.6 线索二叉树线索二叉树v中序线索二叉树中序线索二叉树 设设root指向一棵二叉树的根结点，指向一棵二叉树的根结点，p指向某个结点，指向某个结点，front指向指向P的前驱P从根结点开始，当从根结点开始，当P 非空时，执非空时，执行下面的操作：行下面的操作：l 中序线索中序线索P结点的左子树结点的左子树;l 如果如果P的左子树为空，设置的左子树为空，设置P的的left指向前驱结点指向前驱结点front的线索，的线索，p.ltag标记为标记为1l 如果如果P的右子树为空，设置前驱结点的右子树为空，设置前驱结点front的的right指向指向p的线索，的线索，p.rtag标记为标记为1 Front指向指向Pl 中序线索中序线索P的右子树的右子树7.6 线索二叉树线索二叉树v示例示例AEFCBDG(a)7.6 线索二叉树线索二叉树v 中序线索二叉树7.6 线索二叉树线索二叉树二叉树中序线索化二叉树中序线索化 Protected threadtreenode front=null;Public void inthreadnode(threadtreenode p)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”;Else instr=instr+”front=null”;instr=instr+”p=”+p.data+”rn”;front=p;inthreadtreenode(p.right);Public void inorderthread()Front=null;Inthreadtreenode(root);7.6 线索二叉树线索二叉树v遍历中序线索二叉树遍历中序线索二叉树 l 寻找第一个访问结点，它是根左子树最左边的结点寻找第一个访问结点，它是根左子树最左边的结点P;l 访问访问P结点，再找结点，再找P的后继结点的后继结点;l 重复执行上面的步骤重复执行上面的步骤.索二叉树索二叉树threadtree1类中，增加类中，增加inordertraver()方法，调用方法，调用innext()方法在方法在中序线索二叉树中实现遍历中序线索二叉树中实现遍历.7.6 线索二叉树线索二叉树v 程序实现程序实现 Public void inordertraver()Threadtreenode p=root;If(p)System.out.print(“中根次序：中根次序：“);While(p.ltag=0)P=p.left;Do System.out.print(p.data+”“);P=innext(p);while(p);System.out.println();The course of elaboration for Data Structures 。