数据结构JAVA版课件.ppt
《数据结构JAVA版课件.ppt》由会员分享,可在线阅读,更多相关《数据结构JAVA版课件.ppt(29页珍藏版)》请在三一文库上搜索。
1、,数据结构(JAVA版),www.YT_JAVA.com,烟台职业学院精品课,第7章 树和二叉树,71 树,树的定义 树是由一个或多个结点构成的有限集合。每棵树必有一个称做根的结点。根结点可以有零个以上的子结点,而各子结点也可为子树。 树的有关术语 根结点(root) 一棵树中没有父结点的结点 叶结点或终端结点 (leaf node)没有子结点的结点 非终端结点(nonterminal) 除了叶结点以外的其他结点 父结点(parent)和子结点(child) 若结点X有一个以结点Y为树根的子树,则X为Y的父结点,而Y就是X的子结点 兄弟(sibling) 同一个父结点的结点 分支度(degre
2、e) 每个结点的子结点数 高度(height)或深度(depth) 一棵树中最大层数 祖先(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
3、若一棵完全二叉树有有n个结点,则其深度为k=log2n+1 一棵深度为k的满二叉树是具有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 二叉树的存储结构,二叉树的顺序存储结构(适合于完全二叉
4、树) 非完全二叉树的顺序存储结构如下图,7.3 二叉树的存储结构,二叉树的链式存储结构 二叉链式存储结构的每个结点包含三个域: 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()
5、This(“?”); Public treenode1(string d) Data=d; Left=right=null; ,7.4 二叉树的遍历,遍历二叉树就是按照一定的规则访问二叉树中所有的结点,并且每个结点仅被访问一次。所谓的访问,是指对每个结点数据进行查询、修改等操作。 若对子树的访问按“先左后右”的次序进行,则遍历二叉树有三种方法: 先根遍历:访问根结点,先根遍历左子树,先根遍历右子树。 中根遍历:中根遍历左子树,访问根结点,中根遍历右子树。 后根遍历:后根遍历左子树,后根遍历右子树,访问根结点。,7.4 二叉树的遍历,实例,可得到上面二叉树先根遍历的顺序为:ABDCE,中根遍历上
6、图得到的顺序为:BDAEC,后根遍历上面的二叉树得到的序列为:DBECA,7.4 二叉树的遍历,程序实现 先根遍历递归程序 public static void PreOrder( int Pointer) if (Pointer != -1) /遍历的终止条件 /处理打印节点内容 System.out.print(“”+TreeDataPointer+”); PreOrder(LeftNodePointer);/处理左子树 PreOrder(RightNodePointer);/处理右子树 ,7.4 二叉树的遍历,程序实现 中序遍历递归程序 public static void InOrde
7、r( 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);/处理左子树 Post
8、Order(LeftNodePointer);/处理左子树 System.out.print(“”+TreeDataPointer+”); ,7.4.3 二叉树的非递归算法,以中根遍历为例 中根遍历二叉树的非递归算法描述如下:设置一个栈为空;从二叉树根结点P开始,若P不空或栈不空,循环执行以下操作,直到走完二叉树或栈为空为止。 若P不空,将P进栈,进入左子树; 若P不空并且栈不空,出栈P,访问P结点,再进入P的右子树。 算法实现: Tree5类继承tree2类,以表明空子树的先根次序建立一棵二叉树。 设计一个栈stack1,元素是object对象,栈元素是二叉树的结点类treenode1。程序
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 JAVA 课件
链接地址:https://www.31doc.com/p-3185598.html