09年自考《数据结构》各章要点二[1]

第六章 树

树是n个结点的有限集合非空时必须满足只有一个称为根的结点其余结点形成m个不相交的子集并称根的子树

根是开始结点结点的子树数称度度为的结点称叶子(终端结点)度不为的结点称分支结点(非终端结点)除根外的分支结点称内部结点

有序树是子树有左右之分的树无序树是子树没有左右之分的树森林是m个互不相交的树的集合

树的四种不同表示方法

·树形表示法

·嵌套集合表示法

·凹入表示法

·广义表表示法

二叉树的定义是n≥个结点的有限集它是空集(n=)或由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成

二叉树不是树的特殊情形与度数为的有序树不同

二叉树的个重要性质

·二叉树上第i层上的结点数目最多为^(i)(i≥)

·深度为k的二叉树至多有(^k)个结点(k≥)

·在任意一棵二叉树中若终端结点的个数为n度为的结点数为n则n=n+

·具有n个结点的完全二叉树的深度为int(logn)+

[] [] [] [] [] [] [] [] [] [] [] []