|
|
|
|
|
树型结构是一类重要的非线性数据结构，其中以树和二叉树最为常用。
|
|
|
|
树是由一个或多个节点组成的有限集T，它满足以下两个条件：有一个特定的节点称为根节点；其余的节点分成m个互不相交的有限集T1, T2, …, Tm，其中每个集又都是一棵树，称T1, T2, …, Tm为根节点的子树。
|
|
|
|
可见树的定义是递归的，即一棵树由子树构成，子树又由更小的子树构成。
|
|
|
|
|
|
|
|
|
|
|
|
若将树中节点的各子树看成是从左到右具有次序的，即不能交换，则称该树为有序树，否则称为无序树。
|
|
|
|
|
|
在应用树结构时，常要求按某种次序获得树中全部节点的信息，这可通过树的遍历操作来实现，常用的遍历方法如下。
|
|
|
|
.前序：先访问根节点，然后从左到右遍历根节点的各棵子树。
|
|
|
|
.后序：先从左到右遍历根节点的各棵子树，然后访问根节点。
|
|
|
|
.层序：先访问处于1层上的节点，然后从左到右依次访问处于2层、3层上的节点，即从上到下、从左到右逐层访问树中各层上的节点。
|
|
|
