《树的基础知识》PPT课件.ppt
《《树的基础知识》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《树的基础知识》PPT课件.ppt(44页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、1 树树l 1.1 树l 1.2 二叉树l 1.3 二叉树的遍历l 1.4 线索二叉树l 1.5 树和森林1.1 树树树的定义:树树:T是n个结点构成的有限集合(n0),其中有一个结点叫根根,其余结点可划分为m个互不相交的子集T1,T2,Tm(m0),并且这m个子集本身又构成树,称为T的子树的子树。注意:这里没给出空树的概念。从树的定义可以看出,树的逻辑结构:(1)树的根结点没有前驱结点,除根结点之外的所有结点有且只有一个前驱结点。(2)树中所有结点可以有零个或多个后继结点。1.1 树树树的表示形式:图形表示法 ABDEFGIHC嵌套集合表示法 HIE DFBGCA凹入表表示法 ABCD E
2、F G H I 广义表表示法 (A(B(D,E(H,I),F),C(G)1.1 树树树的有关概念:1、孩子结点、双亲结点孩子结点、双亲结点(父结点父结点):某结点的子树的根为该结点的孩子结点,而该结点为其孩子结点的双亲结点。兄弟结点:兄弟结点:同一结点的孩子为兄弟结点。可延伸到祖先结点祖先结点和后代结点后代结点。2、一个结点的度一个结点的度:该结点的直接后继结点(孩子)的个数。树的度树的度:树中最大的结点度。3、叶子结点叶子结点(终结点终结点):结点度为0。分支结点分支结点:结点度不为0。根结点根结点:无直接前驱结点。1.1 树树树的有关概念:5、森林森林:多棵树。4、一个结点的层次一个结点的
3、层次:根为1,其余为父结点的层次数加1。树的深度树的深度:最大的结点层次数。6、有序树有序树:树中各兄弟结点之间的排列次序是有关的。无序树无序树:树中各兄弟结点之间的排列次序是无关的。1.1 树树树的基本运算:1、初始化树initial_tree(T):建立树的初始结构。2、插入子树insert_tree(T,S):将以S为根的子树作为T的第一个子树插入到树中。3、插入兄弟结点insert_sigling(T,S):将以S为根的树作为T的兄弟子树插入到树中。4、查询根结点rootof(T):查询结点T所在树的根结点。5、查询父结点fatherof(T):查询结点T的父结点。6、查询孩子结点ch
4、ildof(T):查询结点T的所有或某个孩子结点。7、查询兄弟结点siblingof(T):查询结点T的所有或某个兄弟结点。1.2 二叉树二叉树1.2.1 二叉树的基本概念 二叉树二叉树T是n个结点的有限集合,其中n0,当n=0时,为空树空树,否则,其中有一个结点为根结点,其余结点划分为两个互不相交的子集TL、TR,并且TL、TR分别构成叫作左、右子树左、右子树的二叉树。(即树中结点的最大度为2,每个结点的孩子有左、右之分)。ABDEFGIHC结点A的左子树结点A的右子树1.2 二叉树二叉树1.2.1 二叉树的基本概念 二叉树的五种不同形态:空树单结点树右子树为空左子树为空左、右子树均不空1.
5、2 二叉树二叉树1.2.1 二叉树的基本概念:满二叉树:满二叉树:每层都有最大数目结点的二叉树。满二叉树:满二叉树:每层都有最大数目结点的二叉树。完全二叉树:完全二叉树:在满二叉树的最下层从右向左连续地删除若干个结点所得到的二叉树。(满二叉树是完全二叉树的一个特例)ADHIEBJKCLFMGON满二叉树ADHIEBJKCLFMG完全二叉树1.2 二叉树二叉树1.2.2 二叉树的性质性质性质1:在二叉树的第i层上的结点个数2 i-1(i0)。性质性质2:深度为k的二叉树的结点个数2k-1(k0)。性质性质3:对任一棵非空的二叉树T,如果其叶子数为n0,度为2的结点数为n2,则有:n0=n2+1。
6、性质性质4:有n个结点的完全二叉树(n0)的深度为log2n+1。性质性质5:在编号的完全二叉树(根结点编号为1,顺序按从上到下、从左到右进行编号)中,各结点编号之间的关系为:i结点若有左孩子则其编号为2i,若有右孩子则其编号为2i+1,若有父结点则其编号为i/2。证明1.2 二叉树二叉树性质性质1证明:证明:用数学归纳法证明。性质性质2 2证明:证明:结点个数n20+21+22+2k-1=2k-1。性质性质3证明:证明:设T的总结点数为n,度为1的结点数为n1,则T的结点数满足关系式:n=n0+n1+n2 (a)从T的分支数来看:在这n个结点中,除根以外,每个结点有一个分支进入,因此其总分支
7、数为n-1。而这些分支仅从度为1和2的结点发出,则有:n-1=n1+2n2 (b)由(a)和(b)得:n0=n2+1性质性质4 4证明:证明:设树深为k,则结点数满足:2k-1-1n2k-1;2k-1n2k;k-1log2nltag为0),则其左子树PL中的第一个元素就是*P的后继,而PL中的先序序列的第一个结点即是其根结点,即P的左孩子(指针为P-lchild)。1、先序线索二叉树中求解后继(2)否则,若*P有右孩子,则其右孩子就是其后继,其指针为P-rchild。按先序遍历,以*P为根的子树的遍历次序是*P、PL、PR,由此顺序可得:(3)否则,P-rchild即是后继线索。1.4 线索二
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 树的基础知识 基础知识 PPT 课件
限制150内