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