数据结构JAVA版课件.ppt

《数据结构JAVA版课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构(JAVA版)YT_JAVA烟台职业学院精品课第7章树和二叉树树1二叉树2二叉树的存储结构3树转换成二叉树5线索二叉树6二叉树的遍历47．1树树的定义树是由一个或多个结点构成的有限集合。每棵树必有一个称做根的结点。根结点可以有零个以上的子结点，而各子结点也可为子树。树的有关术语根结点(root)一棵树中没有父结点的结点叶结点或终端结点(leafnode)没有子结点的结点非终端结点(nonterminal)除了叶结点以外的其他结点父结点(parent)和子结点(child)若结点X有一个以结

2、点Y为树根的子树，则X为Y的父结点，而Y就是X的子结点兄弟(sibling)同一个父结点的结点分支度(degree)每个结点的子结点数高度(height)或深度(depth)一棵树中最大层数祖先(ancestor)由结点X到根结点路径上所有的结点森林(forest)n≥0个树的集合7.2二叉树二叉树（Binarytree）的递归定义二叉树是有n个结点组成的有限集合，n=0时为空二叉树；n>0时，二叉树是由有一个根结点和两棵互不相交的、分别称为左子树和右子树构成。二叉树有一种有序树。两棵不同的二叉树

3、:7．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个结点的完全二叉树，对

4、于编号为i的结点，有如下特点：若i=1，则i为根结点，无双亲；否则i结点的双亲编号为i/2的结点。若2i≤n，则i的左孩子编号为2i，否则i无左孩子。若2i+1≤n，则i的右孩子编号为2i+1，否则i无右孩子。7.3二叉树的存储结构二叉树的顺序存储结构(适合于完全二叉树)非完全二叉树的顺序存储结构如下图7.3二叉树的存储结构二叉树的链式存储结构二叉链式存储结构的每个结点包含三个域:Root指向二叉树的根结点。若二叉树为空，则root=null。在一棵有n个结点的链式存储的二叉树中，有n+1个空链域

5、。dataleftChildrightChild7.3二叉树的存储结构(1)不带头结点的二叉树;(2)带头结点的二叉树ABCDEFG∧∧∧∧∧∧∧∧(a)ABCDEFG∧∧∧∧∧∧∧∧(b)rootroot∧7.3二叉树的存储结构声明二叉树类二叉树的结点类Packageds_java;Publicclasstreenodel{Publicstringdata;Publictreenode1left,right;Publictreenode1(){This(“?”);}Publictreenode1

6、(stringd){Data=d;Left=right=null;}}7.4二叉树的遍历遍历二叉树就是按照一定的规则访问二叉树中所有的结点，并且每个结点仅被访问一次。所谓的访问，是指对每个结点数据进行查询、修改等操作。若对子树的访问按“先左后右”的次序进行，则遍历二叉树有三种方法：先根遍历：访问根结点，先根遍历左子树，先根遍历右子树。中根遍历：中根遍历左子树，访问根结点，中根遍历右子树。后根遍历：后根遍历左子树，后根遍历右子树，访问根结点。7.4二叉树的遍历实例ABCDE可得到上面二叉树先根遍历的

7、顺序为：ABDCE中根遍历上图得到的顺序为：BDAEC后根遍历上面的二叉树得到的序列为：DBECA7.4二叉树的遍历程序实现先根遍历递归程序publicstaticvoidPreOrder（intPointer）{if（Pointer！=-1）//遍历的终止条件{//处理打印节点内容System.out.print(“”+TreeData[Pointer]+””)；PreOrder（LeftNode[Pointer]）；//处理左子树PreOrder（RightNode[Pointer]）；//处

8、理右子树}}7.4二叉树的遍历程序实现中序遍历递归程序publicstaticvoidInOrder（intPointer）{if（Pointer！=-1）//遍历的终止条件{//处理打印节点内容InOrder（LeftNode[Pointer]）；//处理左子树System.out.print(“”+TreeData[Pointer]+””)；InOrder（RightNode[Pointer]）；//处理右子树}}7.4二叉树的遍历后根遍历递归程序:publicstaticvo