数据结构(JAVA版)-课件（PPT定稿）.ppt

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