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