Java数据结构之树与二叉树

单击此处编辑母版文本样式,第二级,第三级,*,学习目标,树,二叉树的定义及性质,二叉树的遍历,树与二叉树的转换,树,树的定义,树的术语,树的定义,树（,tree,）是由,n,（,n0,）个结点组成的有限集合。,n=0,的树称为空树；对,n0,的树,T,，有：,有一个特殊的结点称为根结点（,root,），它只有直接后继结点，没有直接前驱结点。,当,n1,时，除根结点之外的其他结点分为,m,（,m0,）个互不相交的集合,T1, T2, , Tm,，其中每个集合,Tm,（,1im,）本身又是一棵结构与树类同的子树（,subtree,）。每棵子树的根结点有且仅有一个直接前驱结点，但可以有零或多个直接后继结点。,树的术语,结点,孩子结点与双亲结点,兄弟结点,祖先结点与后代结点,结点的度,叶子结点与分支结点,树的度,二叉树的定义及性质,二叉树的定义,二叉树的性质,二叉树的存储结构,声明二叉树类,二叉树的定义,二叉树的递归定义,二叉树（,binary tree,）是,n,（,n0,）个结点组成的有限集合。,n=0,时称为空二叉树；,n0,的二叉树由一个根结点和两棵互不相交的、分别称为左子树和右子树的子二叉树构成。,二叉树的基本形态,3,个结点树与二叉树的基本形态,二叉树的性质,性质,1,若根结点的层次为,1,，则二叉树第,i,层的结点数目最多为,2,i,-1,（,i1,）。,性质,2,在深度为,k,的二叉树中，至多有,2,k,-1,个结点（,k0,）。,性质,3,二叉树中，若叶子结点数为,n0,，,2,度结点数为,n2,，则有,n0=n2+1,。,满二叉树与完全二叉树,性质,4,如果一棵完全二叉树有,n,个结点，则其深度。,性质,5,若将一棵具有,n,个结点的完全二叉树按顺序表示，对于编号为,i,（,1in,）的结点，有如下特点：,若,i=1,，则,i,为根结点，无双亲；若,i1,，则,i,的双亲是编号为,i /2,的结点。,若,2in,，则,i,的左孩子是编号为,2i,的结点；若,2i,n,，则,i,无左孩子。,若,2i+1n,，则,i,的右孩子是编号为,2i+1,的结点；若,2i+1,n,，则,i,无右孩子。,二叉树的存储结构,二叉树的顺序存储结构,二叉树的链式存储结构,声明二叉树类,二叉树的结点类,public,class,TreeNode ,public,Object,data,;,/,数据元素,public,TreeNode,left,right,;,/,指向左、右孩子结点的链,public,TreeNode() ,this,(,?,);,public,TreeNode(Object o),/,构造有值结点,data,= o;,left,=,null,;,right,=,null,;,二叉树类节点,public,void,setData(Object data) ,this,.,data,= data;,public,Object getData() ,return,data,;,public,void,setLeft(TreeNode left) ,this,.,left,= left;,public,TreeNode getLeft() ,return,left,;,二叉树类节点,public,TreeNode setRight(TreeNode right) ,return,this,.,right,= right;,public,TreeNode getRight() ,return,right,;,/,测试一个节点是否是叶子节点,public,boolean,isLeaf() ,return,left,=,null,&,right,=,null,;,/如何从最左节点或最右节点获取数据？,二叉树类节点,/从最左节点或最右节点获取数据,public,Object getLeftmostData(),if,(,left,=,null,) ,return,data,;,else,return,left,.getLeftmostData();,/如何删除最左节点或最右节点？,提示：,二叉树类节点,/删除最左或最右节点,public,TreeNode removeLeftmost(),if,(,left,=,null,),/,最左节点是根节点，因为它没有左孩子,return,right,;,else,/,一个递归调用删除左子树的最左节点,left,=,left,.removeLeftmost();,return,this,;,练习,提供复制一棵二叉树的方法,public static TreeNode treeCopy(TreeNode source),练习,编写程序，求寻找最右边节点的方法。,编写程序，求删除最右边节点的方法,。,