文档介绍：The course of elaboration for Data Structures 数据结构(JAVA版) 树?树的定义树是由一个或多个结点构成的有限集合。每棵树必有一个称做根的结点。根结点可以有零个以上的子结点,而各子结点也可为子树。?树的有关术语?根结点(root) 一棵树中没有父结点的结点?叶结点或终端结点(leaf node)没有子结点的结点?非终端结点(nonterminal) 除了叶结点以外的其他结点?父结点(parent)和子结点(child) 若结点X有一个以结点Y为树根的子树,则X为Y的父结点,而Y就是X的子结点?兄弟(sibling) 同一个父结点的结点?分支度(degree) 每个结点的子结点数?高度(height)或深度(depth) 一棵树中最大层数?祖先(ancestor) 由结点X到根结点路径上所有的结点?森林(forest) n≥ 二叉树?二叉树(Binary tree)的递归定义二叉树是有n个结点组成的有限集合,n=0时为空二叉树;n>0时,二叉树是由有一个根结点和两棵互不相交的、分别称为左子树和右子树构成。二叉树有一种有序树。两棵不同的二叉树:ADGECF(a)(b) 二叉树的性质?二叉树的第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无右孩子。 二叉树的存储结构?二叉树的顺序存储结构(适合于完全二叉树) 二叉树的存储结构?二叉树的链式存储结构二叉链式存储结构的每个结点包含三个域: Root指向二叉树的根结点。若二叉树为空,则root=null。在一棵有n个结点的链式存储的二叉树中,有n+1个空链域。 二叉树的存储结构(1)不带头结点的二叉树;(2)带头结点的二叉树ABCDEFG∧∧∧∧∧∧∧∧(a)ABCDEFG∧∧∧∧∧∧∧∧(b)rootroot∧ 二叉树的存储结构?声明二叉树类二叉树的结点类 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; } } 二叉树的遍历?遍历二叉树就是按照一定的规则访问二叉树中所有的结点,并且每个结点仅被访问一次。所谓的访问,是指对每个结点数据进行查询、修改等操作。?若对子树的访问按“先左后右”的次序进行,则遍历二叉树有三种方法:?先根遍历:访问根结点,先根遍历左子树,先根遍历右子树。?中根遍历:中根遍历左子树,访问根结点,中根遍历右子树。?后根遍历:后根遍历左子树,后根遍历右子树,访问根结点。