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