树形结构是一类重要的非线性数据结构。在客观世界中广泛存在的各种层次结构都可用树形结构来表示,如社会组织机构、人类社会的族谱等。本章首先引入树和二叉树的基本概念,重点介绍二叉树的存储结构及其各种操作,研究树和森林与二叉树的转换关系,并讨论树的典型应用问题。
目录
树的定义和术语
直观地看,树形结构是数据元素(结点)之间有分支,并且具有层次关系的结构,可用于表示数据元素之间存在的一对多关系。
1. 树的定义
树是由n(n>=0)个结点构成的有限集合,当n=0时称为空树。若树非空,则具有以下两个性质:
(1)有且仅有一个特定的结点,称为根。
(2)其余的结点可分为m个互不相交的集合T1,T2,……,Tm,其中每一个集合都是一棵树,并且称为根的子树。
2. 树的基本术语
树结点:树中一个独立单元。包含一个数据元素及若干指向其子树的分支。
树根:树中唯一没有前驱的结点。
结点的度:结点拥有的子树数,称为结点的度。
数的度:树中各结点的度的最大值。
树叶:度为0的结点。
双亲和孩子:把一个树结点的直接前驱称为该结点的双亲;反之,把一个树结点的所有直接后继称为该结点的孩子。
兄弟:同一双亲的孩子之间互称兄弟。
树的层次和深度:从根算起,根为第一层,根的孩子为第二层,树中任一结点的层次等于它的双亲的层次加1。树中各结点层次的最大值称为树的深度或高度。
有序树和无序树:如果树中结点的各子树可看成从左至右是有次序的(即不能互换),则称该树为有序树,否则称为无序树。在有序树最左边子树的根称为第一孩子,最右边子树的根称为最后一个孩子。
森林:m(m>=0)棵互不相交的树的集合。对树中每个结点而言,其子树的集合即为森林。由此也可以以森林和树的相互递归定义来描述树。
3. 树的表示
树除了可以用图形表示之外,还有多种表示方法:广义表表示法、层号表示法、凹入表示法、以嵌套集合表示法等
4. 树的遍历
在树的应用中,经常会要求对树中的所有结点进行访问,且每个结点仅访问一次,这就是树的遍历。可把对结点的访问看成打印结点的关键字、数据项或结点编号,把遍历看成是按序输出结点表。对于树结构来说,就需要按照某种特定次序来规范对树中所有的结点进行访问。具体的遍历方式有先序遍历和后序遍历两种。
下面用递归方式定义这两种遍历:
(1)若T是一棵空树,那么对T进行先根和后根遍历所得到的结果都是空。
(2)若T是一棵单节点树,那么对该树进行先根和后根访问所得到的结果是该结点本身。
(3)若T是由一个根结点n和m棵不相交的子树构成,则:
① 树的先根遍历:首先访问根结点n;其次依次按先根遍历T1,按先根遍历T2……直到最后先根遍历Tm。
② 树的后根遍历:先按后根遍历n的所有子树,最后访问根结点n。