|
树是非线性结构,存储树时,须把树中结点之间存在的关系反映在树的存储结构中。树有很多存储结构,这里仅介绍最常用的两种。
|
|
|
|
树的标准存储结构由结点的数据和指向子结点的指针数组组成;对于度为M的树,其指针数组中的元素个数为M。
|
|
|
|
由于树的带逆存储结构需要一个从子结点指向父结点的指针,因而该结构在标准存储结构的基础上,需要在树的结点中增加一个指向其双亲结点位置的指针。
|
|
|
树的遍历是树的基本操作之一,也是最重要的操作之一。树的遍历含义是指:按照某种要求依次访问树中的每个结点,每个结点均被访问一次且仅被访问一次。常用的树的遍历方法可分为前序遍历、后序遍历和中序遍历。
|
|
|
(1)树的前序遍历。首先访问根结点,然后从左到右前序遍历根结点的各棵子树。树的前序遍历递归算法如下:
|
|
|
|
若利用栈来记录当前未访问完的子树的根结点指针,则前序遍历的非递归算法如下:
|
|
|
|
(2)树的后序遍历。树的后序遍历的基本思想是:先依次遍历每棵子树,然后访问根结点,与后序遍历二叉树相同。树的后序遍历递归算法如下:
|
|
|
|
(3)树的中序遍历。树的中序遍历的基本思想是:先左子树,遍历根结点,然后依次遍历其他各棵子树,类似二叉树的中序遍历。树的中序遍历递归算法如下:
|
|
|
|