文档介绍：1 树? 树? 二叉树? 二叉树的遍历? 线索二叉树? 树和森林 树树的定义: 树:T是n个结点构成的有限集合(n>0) ,其中有一个结点叫根,其余结点可划分为 m个互不相交的子集 T 1 ,T 2,……,T m (m ≥ 0),并且这 m个子集本身又构成树,称为 T的子树。注意:这里没给出空树的概念。从树的定义可以看出,树的逻辑结构: (1)树的根结点没有前驱结点,除根结点之外的所有结点有且只有一个前驱结点。(2)树中所有结点可以有零个或多个后继结点。 树树的表示形式: 图形表示法 ABDEFGIH C嵌套集合表示法 HI E DF BG C A凹入表表示法 ABC D E F G H I 广义表表示法( A ( B ( D, E ( H, I ), F ), C ( G ) ) ) 树树的有关概念: 1、孩子结点、双亲结点(父结点):某结点的子树的根为该结点的孩子结点,而该结点为其孩子结点的双亲结点。兄弟结点: 同一结点的孩子为兄弟结点。可延伸到祖先结点和后代结点。 2、一个结点的度:该结点的直接后继结点(孩子)的个数。树的度:树中最大的结点度。 3、叶子结点(终结点):结点度为 0。分支结点:结点度不为 0。根结点:无直接前驱结点。 树树的有关概念: 5、森林:多棵树。 4、一个结点的层次:根为 1,其余为父结点的层次数加 1。树的深度:最大的结点层次数。 6、有序树:树中各兄弟结点之间的排列次序是有关的。无序树:树中各兄弟结点之间的排列次序是无关的。 树树的基本运算: 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的所有或某个兄弟结点。 二叉树 二叉树的基本概念二叉树 T是n个结点的有限集合,其中 n≥ 0,当 n=0 时, 为空树,否则,其中有一个结点为根结点,其余结点划分为两个互不相交的子集 TL 、 TR ,并且 TL 、 TR 分别构成叫作左、右子树的二叉树。(即树中结点的最大度为 2,每个结点的孩子有左、右之分)。 ABDEFG IH C 结点 A的左子树结点 A的右子树 二叉树 二叉树的基本概念二叉树的五种不同形态: 空树? 单结点树右子树为空左子树为空左、右子树均不空 二叉树 二叉树的基本概念: 满二叉树: 每层都有最大数目结点的二叉树。满二叉树: 每层都有最大数目结点的二叉树。完全二叉树: 在满二叉树的最下层从右向左连续地删除若干个结点所得到的二叉树。(满二叉树是完全二叉树的一个特例) ADHI E BJK CL FM GON满二叉树 ADHI E BJK CL FM G完全二叉树 二叉树 二叉树的性质性质 1:在二叉树的第 i层上的结点个数≤ 2 i - 1 ( i>0 )。性质 2:深度为 k的二叉树的结点个数≤2 k -1( k>0 )。性质 3:对任一棵非空的二叉树 T,如果其叶子数为 n 0,度为2的结点数为 n 2,则有: n 0 = n 2 +1 。性质 4:有n个结点的完全二叉树(n>0) 的深度为 log 2 n+1 。性质 5:在编号的完全二叉树(根结点编号为 1,顺序按从上到下、从左到右进行编号)中,各结点编号之间的关系为: i 结点若有左孩子则其编号为 2i,若有右孩子则其编号为 2i+1 ,若有父结点则其编号为 i/2 。证明