第6章树和二叉树 从对线性结构的研究过渡到对树形 结构的研究,是数据结构课程学习的 次跃变
从对线性结构的研究过渡到对树形 结构的研究，是数据结构课程学习的一 次跃变
6树的定义和基本术语 1树的定义 树是由n(n≥0个结点组成的有限集合。 如果n=0,称为空树 如果n>0,则 有一个特定的称之为根(roo的结点,它只有 后继,但没有前驱; 除根以外的其它结点划分为m(m≥0)个互不 相交的有限集合T,T,…,Tm1,每个集合本身又 是一棵树,并且称之为根的子树( subTree每棵 子树的根结点有且仅有一个直接前驱,但可以有 0个或多个后继
6.1 树的定义和基本术语 1. 树的定义 树是由n (n 0)个结点组成的有限集合。 如果n = 0，称为空树； 如果n > 0，则: ▪ 有一个特定的称之为根(root)的结点，它只有 后继，但没有前驱； ▪ 除根以外的其它结点划分为m (m 0)个互不 相交的有限集合T0 , T1 , …, Tm-1，每个集合本身又 是一棵树，并且称之为根的子树(subTree)。每棵 子树的根结点有且仅有一个直接前驱，但可以有 0个或多个后继
root Level 1 mlevel 2 level 3 eve
E BF Q/(@c J K D H A(B(E, FO, K)G)C, D(H D) (b) (a)嵌套集合表示法(b)括号表示法()凹入表示法
(a)嵌套集合表示法 (b)括号表示法 (c)凹入表示法
2树的基本术语 1)度(次数、级) (1)结点的度:一个结点所拥有的子数的个数 (2)树的度:树内各结点的度的最大值 2)描述上下及左右的关系 孩子和双亲结点:某个结点的子树的根称为该结点的 孩子,相应的,该结点称为其孩子的双亲。 兄弟结点:同一个双亲的孩子之间互称兄弟 祖先:结点的祖先是从根到该结点所经分支上的 所有结点。 子孙:以某结点为根的子树中的任一结点都称为该结 点的子孙
1）度（次数、级） （1）结点的度：一个结点所拥有的子数的个数 （2）树的度：树内各结点的度的最大值 2）描述上下及左右的关系 孩子和双亲结点：某个结点的子树的根称为该结点的 孩子，相应的，该结点称为其孩子的双亲。 兄弟结点：同一个双亲的孩子之间互称兄弟 祖先：结点的祖先是从根到该结点所经分支上的 所有结点。 子孙：以某结点为根的子树中的任一结点都称为该结 点的子孙。 2. 树的基本术语