学习主题:数据结构之树及树的遍历(一)
基本概念
树的定义:树是n个结点的集合,集合中有一个成为根的特殊结点,在根结点下分布着一些互不相交的集合,每个集合又是一个树,这些树成为根结点的子树。如图1-1所示。
从树的定义中不难看出其中采用了递归的描述,换一个说法就是子树和根结点构成一个新的树,树的子树也还是树。
父结点,子结点,兄弟结点:
每个结点的子树成为该结点的子结点(儿子),相应的该结点成为子结点的父结点(父亲),具有同一父结点的结点成为兄弟结点,如图1-2所示,B是A的子结点,A是B的父结点,B与C是兄弟结点。
叶结点:一个结点若没有子结点,则称该结点为叶结点,图1-2中的叶结点有D,E,F,G,I,K。(自己写的)
结点的度:一个结点的子树的数量称为结点的度,如图1-2,结点A有B,C,D三个子结点,则A的度为3。
树的度:树中任意结点的度的最大值,如图1-2,结点A和结点C的度最大,为3,则该树的度为3。
树的深度:指的是树的最大层数,如图1-2,该树的深度为4?5??有待考证?
层:根结点在第一层,以此类推,如图1-2,结点H在第三层。
高度:叶结点的高度为1,以此类推,根结点的高度最高。
森林:多个树组成的为森林,即将图1-1和图1-2放在同一张图中,但并不相连。
在树中,有且仅有一个结点没有父结点,即该树的根结点;除了根结点之外的其余结点,每个结点有且仅有一个父结点,但该结点可以有无数的子结点。如图1-3和图1-4,这两张图都不是树。
特殊的树
1、空树:若一棵树没有结点,则该树为空树。
2、若一个树有且仅有一个结点,则该结点为根结点。
3、斜树:所有节点只有左节点或右节点,如图1-5所示。
4、二叉树:二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。如图1-6所示。
5、B树(B-tree)是一种树状数据结构,它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树,概括来说是一个节点可以拥有多于2个子节点的二叉查找树。
6、Trie树,又称字典树,单词查找树或者前缀树,是一种用于快速检索的多叉树结构,如英文字母的字典树是一个26叉树,数字的字典树是一个10叉树。
重点学习二叉树、B树和Trie树及其遍历。
树的表示法
1、双亲表示法:每个结点存储该结点的数据及其父结点在数组中的下标。
2、孩子表示法:全部结点组成一个数组,每个数组指向一个单链表,存放其子结点。如图1-7所示。
3、双亲孩子表示法:如图1-8所示。
4、孩子兄弟表示法:如图1-9所示。
此方法的好处在于能够将一个多叉树(即拥有子结点个数大于2的结点)转换成一个二叉树,是将复杂的树转换成二叉树的很好的一个办法。