数据结构之树

《数据结构之树》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构之树CSDN博客频道搬家功能改版正式上线！【免费】解读海外市场营销奥秘CSDN博客频道推出TAG功能数据结构之树-树的相关概念分类：数据结构2010-12-1721:12136人阅读评论（0）收藏举报树是一种非线性的层次聚集，由n（n>=0）个节点组成。n=0时成为空树，n>0时：有一个特定的称之为根（root）的节点，根节点只有直接后继,没有直接前驱；除根以外的其他节点可以划分为m个互不相交的集合，每个集合又是一棵树，他们称之为根的子树。每个子树的根节点仅有一个直接前驱，但是可以有一个或多个直接后继。树的相关概念:节点（node）

2、:节点包括数据项及指向其他节点的引用；节点的度（degree）:节点拥有的子树的个数称之为节点的度;节点的层次（level）：从根节点到此节点所经路径上的分支条数。以下约定根节点的层次为0；叶子节点（leaf）:没有子树的节点称之为叶子节点或终端节点，即度为0的节点；分支节点（branch）：有子树的节点称之为分支节点或非非终端节点；子女节点（child）:节点的子树的根节点称之为节点的子女节点；双亲节点（parent）:若节点有子女，则节点为其子女的双亲节点；兄弟节点（slibing）:同一双亲的子女节点互为许多节点；祖先节点（ancestor）:从

3、根节点到此节点所经分支的所有节点称之为此节点的祖先节点；子孙节点（descendant）:节点的子女及子女的子女都是该节点的子孙节点；树的高度（depth）:书中节点的最大层次。以下约定：空树的高度为畀，只有一个节点的树的高度为0树的度（degree）:树中的节点的度的最大值。数据结构之树-树的抽象接口分类：数据结构2010-12-1721:1662人阅读评论（0）收藏举报根据前一节树的特点，树接口定义如下:节点抽象接口:*desc:*树节点<br>*ver.datewhowhat*0.0.12010-12-8leisoreaddpacka

4、gecn.leisore.dsa.ds_tsinghua.ch06・sec01;importjava.util.Iterator;*TreeNode**@authorleisore*@sinceversion0.0.1publicinterfaceTreeNode<T>{*得到节点的度**©return*/intGetDegree();*得到节点的层(根节点在0层)**@returnintGetLevelQ;*是否是叶子节点**@return*/booleanlsLeaf();*得到节点的双亲**@returnTreeNode<T&g

5、t;GetParent();*得到节点的子女节点**@returnlterator<T>GetChildren();*得到节点的兄弟节点**©return*/lterator<T>GetSibling();*得到节点的祖先节点*lterator<T>GetAncestor();*得到节点的子孙节点*@returnlterator<T>GetDescendant();*desc:**树节点&t;br>*ver.*datewhowhat*0.0.12010-12-8leisoreadd**/packag

6、ecn.leisore.dsa.ds_tsinghua.ch06.sec01;importjava.util.Iterator;*TreeNode*@authorleisore*©sinceversion0.0.17publicinterfaceTreeNode<T>{*得到节点的度*@return*/intGetDegreeQ;*得到节点的层（根节点在0层）*©return7intGetLevel();*是否是叶子节点booleanlsLeaf();*得到节点的双亲*@return*/TreeNode<T>GetParent(

7、);*得到节点的子女节点*@return7lterator<T>GetChildrenQ;*得到节点的兄弟节点**©return7lterator<T>GetSiblingQ;*得到节点的祖先节点*@return*/lterator<T>GetAncestor();*得到节点的子孙节点**©return7lterator<T>GetDescendant();}树抽象接口：*desc:*XXX<br>ver.datewhowhat*0.0.12010-12-8leisoreadd*/packag

8、ecn.leisore.dsa.ds_tsinghua.ch06・sec01;*Tree**©