数据结构PPT树和二叉树.pptx

该【数据结构PPT树和二叉树 】是由【h377683120】上传分享，文档一共【101】页，该文档可以免费在线阅读，需要了解更多关于【数据结构PPT树和二叉树 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据结构PPT树和二叉树6、1树得定义和基本术语什么就是树?树就是由n(n≥0)个结点得有限集合。如果n=0,称为空树;如果n>0,则有且仅有一个特定得称之为根(Root)得结点,她只有直接后继,但没有直接前驱;当n>1,除根以外得其她结点划分为m(m>0)个互不相交得有限集T1,T2,…,Tm,其中每个集合本身又就是一棵树,并且称为根得子树(SubTree)。T={A,B,C,D,E,F,G,H,I,J,K,L,M}A就是根,其余结点可以划分为3个互不相交得集合:T1={B,E,F,K,L}T2={C,G}T3={D,H,I,J,M}这些集合中得每一集合都本身又就是一棵树,她们就是A得子树。对于T1,B就是根,其余结点可以划分为2个互不相交得集合:T11={E,K,L}T12={F}T11,T12就是B得子树。HBAJFEDKLCMIG树得示例1、树中只有根结点没有前趋;2、除根外,其余结点都有且仅一个前趋;3、树得结点,可以有零个或多个后继;4、除根外得其她结点,都存在唯一条从根到该结点得路径;5、树就是一种分支结构。HBAJFEDKLCMIG树得逻辑结构特点树可表示具有分支结构关系得对象例1、家族族谱设某家庭有13个成员A、B、C、D、E、F、G、H、I、J、K、L、M,她们之间得关系可如图所示得树表示。例2、单位行政机构得组织关系HBAJFEDKLCMIG树得应用树就是常用得数据组织形式有些应用中数据元素之间并不存在分支结构关系,但就是为了便于管理和使用数据,将她们用树得形式来组织。例3、计算机得文件系统不论就是DOS文件系统还就是window文件系统,所有得文件就是用树得形式来组织得。文件夹1文件夹2文件1文件2文件夹11文件夹11文件11文件12C树得应用树得结点:包含一个数据元素得内容及若干指向子树得分支。孩子结点:结点得子树得根称为该结点得孩子;如E就是B得孩子。双亲结点:B结点就是A结点得孩子,则A结点就是B结点得双亲;如B就是E得双亲。兄弟结点:同一双亲得孩子结点;如H、I、J互为兄弟。堂兄结点:同一层上结点;如G与E、F、H、I、J互为堂兄。祖先结点:结点得祖先就是从根到该结点所经分支上得所有结点;如H得祖先为A、D。子孙结点:以某结点为根得子树中得任一结点称为该结点得子孙;如A得子孙为B、C、D、E、F、G、H、I、J、K、L、M。HBAJFEDKLCMIG基本术语结点得度:结点子树得个数;如D得度为3。叶子结点:也叫终端结点,就是度为0得结点;如K、L、F、G、M、I、J。分支结点:度不为0得结点;如A、B、C、D结点层次:根结点得层定义为1,根得孩子为第二层结点,依此类推。树得高度:树中结点得最大层次;如图所示树得高度为4。树得度:树中各结点得度得最大值;如图所示树得度为3。森林:m(m>=0)棵互不相交得树得集合;HBAJFEDKLCMIG基本术语线性结构第一个数据元素(无前驱);最后一个数据元素(无后继);其她数据元素(一个前驱、一个后继)。树型结构根结点(无前驱);多个叶子结点(无后继);其她数据元素(一个前驱、多个后继)。树型结构和线性结构得结构特点对比6、2、1二叉树得定义或为空树,或由根及至多两棵互不相交得左子树、右子树构成(即不存在度大于2得结点),并且左、右子树本身也就是二叉树。说明:1、二叉树中每个结点最多有两棵子树,二叉树每个结点度小于等于2;2、左、右子树不能颠倒——有序树;3、二叉树就是递归结构,在二叉树得定义中又用到了二叉树得概念。BADCFEG6、2二叉树