大连理工大学的数据结构6章课件.pdf

S1 S2 S3 S4 第六章树和二叉树 S5 S6 层次 （树型）结构，一对多 S7 一个数据元素若有直接前驱，只能有一个直接前驱 一个数据元素若有直接后继，可以有多个直接后继 6.1 树的基本概念和术语  树 ：具有相同特性的n个结点 （数据元素）的有限集合。  若n=0 ，则称为空树 。否则:  存在唯一的称为根的结点root ；  当n1 时，其余结点可分为m (m0)个互不相交的有限集 T , T , …, T ，其中每一棵子集本身又是一棵符合本定义 1 2 m 的树，称为根root 的子树。  m棵 子树的根结点为根root 的直接后继 例如: A B C D E F G H I J K L M A( B(E, F(K, L)), C(G), D(H, I, J(M)) ) 树根 T T T 1 2 3 线性结构 树型结构 第一个数据元素 根结点 (无前驱) (无前驱) 最后一个数据元素 多个叶子结点 (无后继) (无后继) 其它数据元素 其它数据元素 (一个前驱、 (一个前驱、 一个后继) 多个后继) 6.1 树的基本概念和术语  结点 ：数据元素+若干指向子树的分支  结点的度：分支的个数，子树的个数  树的度 ：树中所有结点的度的最大值  叶子结点 ：度为零的结点  分支结点 ：度大于零的结点 D H I J M 6.1 树的基本概念和术语  结点路径：由从根到该结点所经分支和结点构成  孩子结点、双亲结点、兄弟结点、堂兄弟、祖先 结点、子孙结点  结点的层次：假设根结点的层次为1 ，第k层的结 点的子树根结点的层次为k+1  树的深度 ：树中叶子结点所在的最大层次