苏州大学数据结构05.ppt

1第五章树与二叉树数据结构电子教案殷人昆 2第五章树与二叉树??树和森林的概念树和森林的概念??二叉树二叉树??二叉树遍历二叉树遍历??二叉树的计数二叉树的计数??线索化二叉树线索化二叉树??树与森林树与森林??堆堆?? Huffman Huffman 树树 3树和森林的概念?两种树:自由树与有根树。?自由树: 一棵自由树 T f可定义为一个二元组 T f = ( V, E)其中 V = { v 1, ..., v n}是由 n (n> 0) 个元素组成的有限非空集合,称为顶点集合。 E = {( v i, v j ) | v i, v j?V, 1≤i, j≤n}是n-1个序对的集合, 称为边集合, E中的元素(v i, v j)称为边或分支。 4自由树?有根树: 一棵有根树 T,简称为树,它是 n (n≥0)个结点的有限集合。当 n = 0 时, T 称为空树; 否则, T是非空树,记作 5 ? r 是一个特定的称为根(root) 的结点,它只有直接后继,但没有直接前驱; ?根以外的其他结点划分为 m (m? 0) 个互不相交的有限集合 T 1, T 2, …, T m,每个集合又是一棵树,并且称之为根的子树。?每棵子树的根结点有且仅有一个直接前驱, 但可以有 0个或多个直接后继。??????0 0n,T ,..., T,T r, n ,T m 21}{ Φ6树的基本术语?子女:若结点的子树非空,结点子树的根即为该结点的子女。?双亲:若结点有子女,该结点是子女双亲。 1层 2层 4层 3层 depth = 4 D ACBIJH G F EM L K height = 3 7 ?兄弟:同一结点的子女互称为兄弟。?度:结点的子女个数即为该结点的度;树中各个结点的度的最大值称为树的度。?分支结点:度不为 0的结点即为分支结点, 亦称为非终端结点。?叶结点:度为 0的结点即为叶结点,亦称为终端结点。?祖先:某结点到根结点的路径上的各个结点都是该结点的祖先。?子孙:某结点的所有下属结点,都是该结点的子孙。 8 ?结点的层次:规定根结点在第一层,其子女结点的层次等于它的层次加一。以下类推。?深度:结点的深度即为结点的层次;离根最远结点的层次即为树的深度。1层 2层 4层 3层 depth = 4 D ACBIJH G F EM L K height = 4 9 ?高度:规定叶结点的高度为 1,其双亲结点的高度等于它的高度加一。?树的高度:等于根结点的高度,即根结点所有子女高度的最大值加一。?有序树:树中结点的各棵子树 T 0, T 1, …是有次序的,即为有序树。?无序树:树中结点的各棵子树之间的次序是不重要的,可以互相交换位置。?森林:森林是 m(m≥0)棵树的集合。 10 树的抽象数据类型 template <class T> class Tree { //对象: 树是由 n ( ≥ 0) 个结点组成的有限集合。在//类界面中的 position 是树中结点的地址。在顺序//存储方式下是下标型, 在链表存储方式下是指针//型。 T 是树结点中存放数据的类型, 要求所有结//点的数据类型都是一致的。 public: Tree () ;~ Tree () ;