树的基础知识.课件.pptVIP

1树1.1树1.2二叉树1.3二叉树的遍历1.4线索二叉树1.5树和森林

1.1树树的定义：树：T是n个结点构成的有限集合(n0)，其中有一个结点叫根，其余结点可划分为m个互不相交的子集T1，T2，……，Tm(m≥0)，并且这m个子集本身又构成树，称为T的子树。注意：这里没给出空树的概念。从树的定义可以看出，树的逻辑结构：（1）树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。（2）树中所有结点可以有零个或多个后继结点。

1.1树树的表示形式：图形表示法ABDEFGIHC嵌套集合表示法HIEDFBGCA凹入表表示法ABCDEFGHI广义表表示法(A(B(D,E(H,I),F),C(G)))

1.1树树的有关概念：1、孩子结点、双亲结点(父结点)：某结点的子树的根为该结点的孩子结点，而该结点为其孩子结点的双亲结点。兄弟结点：同一结点的孩子为兄弟结点。可延伸到祖先结点和后代结点。2、一个结点的度：该结点的直接后继结点(孩子)的个数。树的度：树中最大的结点度。3、叶子结点(终结点)：结点度为0。分支结点：结点度不为0。根结点：无直接前驱结点。

1.1树树的有关概念：5、森林：多棵树。4、一个结点的层次：根为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、查询孩子结点childof(T)：查询结点T的所有或某个孩子结点。7、查询兄弟结点siblingof(T)：查询结点T的所有或某个兄弟结点。

1.2二叉树1.2.1二叉树的基本概念二叉树T是n个结点的有限集合，其中n≥0,当n=0时，为空树，否则，其中有一个结点为根结点，其余结点划分为两个互不相交的子集TL、TR，并且TL、TR分别构成叫作左、右子树的二叉树。（即树中结点的最大度为2，每个结点的孩子有左、右之分）。ABDEFGIHC结点A的左子树结点A的右子树

1.2二叉树1.2.1二叉树的基本概念二叉树的五种不同形态：空树?单结点树右子树为空左子树为空左、右子树均不空

1.2二叉树1.2.1二叉树的基本概念：满二叉树：每层都有最大数目结点的二叉树。满二叉树：每层都有最大数目结点的二叉树。完全二叉树：在满二叉树的最下层从右向左连续地删除若干个结点所得到的二叉树。（满二叉树是完全二叉树的一个特例）ADHIEBJKCLFMGON满二叉树ADHIEBJKCLFMG完全二叉树

1.2二叉树1.2.2二叉树的性质性质1：在二叉树的第i层上的结点个数≤2i-1（i0）。性质2：深度为k的二叉树的结点个数≤2k-1（k0）。性质3：对任一棵非空的二叉树T，如果其叶子数为n0，度为2的结点数为n2，则有：n0=n2+1。性质4：有n个结点的完全二叉树(n0)的深度为log2n+1。性质5：在编号的完全二叉树(根结点编号为1，顺序按从上到下、从左到右进行编号)中，各结点编号之间的关系为：i结点若有左孩子则其编号为2i，若有右孩子则其编号为2i+1，若有父结点则其编号为i/2。证明

1.2二叉树性质1证明：用数学归纳法证明。性质2证明：结点个数n≤20+21+22+┅+2k-1=2k-1。性质3证明：设T的总结点数为n，度为1的结点数为n1，则T的结点数满足关系式：n=n0+n1+n2(a)从T的分支数来看：在这n个结点中，除根以外，每个结点有一个分支进入，因此其总分支数为n-1。而这些分支仅从度为1和2的结点发出，则有：n-1=n1+2n2(b)由(a)和(b)得：n0=n2+1性质4证明：设树深为k，则结点数满足：2k-1-1n≤2k-1；2k-1≤n2k；k-1≤log2nk；k=log2n+1。返回

1.2二叉树1.2