数据结构(JAVA版)(精品·公开课件).ppt

数据结构(JAVA版) www.YT_JAVA.com 第7章 树和二叉树 7．1 树 树的定义 树是由一个或多个结点构成的有限集合。每棵树必有一个称做根的结点。根结点可以有零个以上的子结点，而各子结点也可为子树。 树的有关术语 根结点(root) 一棵树中没有父结点的结点 叶结点或终端结点 (leaf node)没有子结点的结点 非终端结点(nonterminal) 除了叶结点以外的其他结点 父结点(parent)和子结点(child) 若结点X有一个以结点Y为树根的子树，则X为Y的父结点，而Y就是X的子结点 兄弟(sibling) 同一个父结点的结点 分支度(degree) 每个结点的子结点数 高度(height)或深度(depth) 一棵树中最大层数 祖先(ancestor) 由结点X到根结点路径上所有的结点 森林(forest) n≥0个树的集合 7.2 二叉树 二叉树（Binary tree）的递归定义  二叉树是有n个结点组成的有限集合，n=0时为空二叉树；n0时，二叉树是由有一个根结点和两棵互不相交的、分别称为左子树和右子树构成。二叉树有一种有序树。 两棵不同的二叉树: 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个结点的完全二叉树，对于编号为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个空链域。 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=right=null; } } 7.4 二叉树的遍历 遍历二叉树就是按照一定的规则访问二叉树中所有的结点，并且每个结点仅被访问一次。所谓的访问，是指对每个结点数据进行查询、修改等操作。 若对子树的访问按“先左后右”的次序进行，则遍历二叉树有三种方法： 先根遍历：访问根结点，先根遍历左子树，先根遍历右子树。 中根遍历：中根遍历左子树，访问根结点，中根遍历右子树。 后根遍历：后根遍历左子树，后根遍历右子树，访问根结点。 7.4 二叉树的遍历 实例 7.4 二叉树的遍历 程序实现 先根遍历递归程序 public static void PreOrder（ int Pointer） { if （Pointer ！= -1） //遍历的终止条件 { //处理打印节点内容 System.out.print(“”+TreeData[Pointer]+””)； PreOrder（LeftNode[Pointer]）；//处理左子树