学习主题：数据结构之树及树的遍历（一）
基本概念
树的定义：树是n个结点的集合，集合中有一个成为根的特殊结点，在根结点下分布着一些互不相交的集合，每个集合又是一个树，这些树成为根结点的子树。如图1-1所示。
图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-2
在树中，有且仅有一个结点没有父结点，即该树的根结点；除了根结点之外的其余结点，每个结点有且仅有一个父结点，但该结点可以有无数的子结点。如图1-3和图1-4，这两张图都不是树。
图1-3
图1-4
特殊的树
1、空树：若一棵树没有结点，则该树为空树。
2、若一个树有且仅有一个结点，则该结点为根结点。
3、斜树：所有节点只有左节点或右节点，如图1-5所示。
图1-5
4、二叉树：二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。如图1-6所示。
图1-6
5、B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。
6、Trie树，又称字典树，单词查找树或者前缀树，是一种用于快速检索的多叉树结构，如英文字母的字典树是一个26叉树，数字的字典树是一个10叉树。
重点学习二叉树、B树和Trie树及其遍历。
树的表示法
1、双亲表示法：每个结点存储该结点的数据及其父结点在数组中的下标。
2、孩子表示法：全部结点组成一个数组，每个数组指向一个单链表，存放其子结点。如图1-7所示。
图1-7
3、双亲孩子表示法：如图1-8所示。
图1-8
4、孩子兄弟表示法：如图1-9所示。
图1-9
此方法的好处在于能够将一个多叉树（即拥有子结点个数大于2的结点）转换成一个二叉树，是将复杂的树转换成二叉树的很好的一个办法。
网友评论