Java数据结构之树与二叉树

1、学习目标树二叉树的定义及性质二叉树的遍历树与二叉树的转换树树的定义义树的术语语树的定义义树（tree）是由n（n0）个结点点组成的的有限集集合。n=0的树称为为空树；对n0的树T，有：有一个特特殊的结结点称为为根结点点（root），它只只有直接接后继结结点，没没有直接接前驱结结点。当n1时，除根根结点之之外的其其他结点点分为m（m0）个互不不相交的的集合T1,T2, , Tm，其中每每个集合合Tm（1im）本身又又是一棵棵结构与与树类同同的子树树（subtree）。每棵棵子树的的根结点点有且仅仅有一个个直接前前驱结点点，但可可以有零零或多个个直接后后继结点点。树的术语语结点孩子结点点与双亲亲结

2、点兄弟结点点祖先结点点与后代代结点结点的度度叶子结点点与分支支结点树的度二叉树的的定义及及性质二叉树的的定义二叉树的的性质二叉树的的存储结结构声明二叉叉树类二叉树的的定义二叉树的的递归定定义二叉树（binarytree）是n（n0）个结点点组成的的有限集集合。n=0时称为空空二叉树树；n0的二叉树树由一个个根结点点和两棵棵互不相相交的、分别称称为左子子树和右右子树的的子二叉叉树构成成。二叉树的的基本形形态3个结点树树与二叉叉树的基基本形态态二叉树的的性质性质1若根结点点的层次次为1，则二叉叉树第i层的结点点数目最最多为2i-1（i1）。性质2在深度为为k的二叉树树中，至至多有2k-1个结点（k

3、0）。性质3二叉树中中，若叶叶子结点点数为n0，2度结点数数为n2，则有n0=n2+1。满二叉树树与完全全二叉树树性质4如果一棵棵完全二二叉树有有n个结点，则其深深度。性质5若将一棵棵具有n个结点的的完全二二叉树按按顺序表表示，对对于编号号为i（1in）的结点点，有如如下特点点：若i=1，则i为根结点点，无双双亲；若若i1，则i的双亲是是编号为为i /2的结点。若2in，则i的左孩子子是编号号为2i的结点；若2in，则i无左孩子子。若2i+1n，则i的右孩子子是编号号为2i+1的结点；若2i+1n，则i无右孩子子。二叉树的的存储结结构二叉树的的顺序存存储结构构二叉树的的链式存存储结构构声明二叉

4、叉树类二叉树的的结点类类publicclassTreeNodepublicObjectdata;/数据元素素publicTreeNodeleft,right;/指向左、右孩子子结点的的链publicTreeNode() this(?);publicTreeNode(Objecto)/构造有值值结点data= o;left=null;right=null;二叉树类类节点publicvoidsetData(Objectdata)this.data= data;publicObjectgetData() returndata;publicvoidsetLeft(TreeNode left) this

5、.left= left;publicTreeNodegetLeft()returnleft;二叉树类类节点publicTreeNodesetRight(TreeNoderight)returnthis.right= right;publicTreeNodegetRight() returnright;/测试一个个节点是是否是叶叶子节点点publicbooleanisLeaf()returnleft=null&right=null;/如何何从最左左节点或或最右节节点获取取数据？二叉树类类节点/从最最左节点点或最右右节点获获取数据据publicObjectgetLeftmostData()if(left=null) returndata;elsereturnleft.getLeftmostData();/如何何删除最最左节点点或最右右节点？提示：二叉树类类节点/删除除最左或或最右节节点publicTreeNoderemoveLeftmost()if(left=null)/最左节点点是根节节点，因因为它没没有左孩孩子returnright;else/一个递归归调用删删除左子子树的最最左节点点left=left.removeLeftmost();returnthis;练习提供复制制一棵二二叉树的的方法p