Java数据结构之树与二叉树.ppt

《Java数据结构之树与二叉树.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

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

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

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

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

5、urndata;}publicvoidsetLeft(TreeNodeleft){this.left=left;}publicTreeNodegetLeft(){returnleft;}二叉树类节点publicTreeNodesetRight(TreeNoderight){returnthis.right=right;}publicTreeNodegetRight(){returnright;}//测试一个节点是否是叶子节点publicbooleanisLeaf(){returnleft==null&&right=

6、=null;}//如何从最左节点或最右节点获取数据？二叉树类节点//从最左节点或最右节点获取数据publicObjectgetLeftmostData(){if(left==null){returndata;}else{returnleft.getLeftmostData();}}//如何删除最左节点或最右节点？提示：二叉树类节点//删除最左或最右节点publicTreeNoderemoveLeftmost(){if(left==null){//最左节点是根节点，因为它没有左孩子returnright;}else{

7、//一个递归调用删除左子树的最左节点left=left.removeLeftmost();returnthis;}}练习提供复制一棵二叉树的方法publicstaticTreeNodetreeCopy(TreeNodesource)练习编写程序，求寻找最右边节点的方法。编写程序，求删除最右边节点的方法。