数据结构笔记（其八）--一般树的存储及其遍历

1.知识总览

        一般的树会有多个孩子，所以存储结构也会与二叉树略有不同。

        一般树的遍历。

2.双亲表示法

        双亲表示法，也是父亲表示法，即每个节点中都存储了其父节点的地址信息。

        特性：可以轻易地找到父节点，但寻找孩子节点麻烦。

        顺序储存，每个节点都储存有其对应的父节点数组下标，根节点默认为-1（且在顺序表中，只有下标为0，其内存有-1的节点是根结点）。

        i.代码

//定义树最多有多少节点
# define MAX 10
//定义树的节点
class PTNode
{
public://数据元素int data;//父节点位置域int parent;
};
//定义树
class PTree
{
public:PTNode nodes[MAX];//指示当前节点个数int n;
};

        删除节点的思路：

        法一，将待删除节点储存的父节点下标设置为-1，意指该节点为空。

        法二，将数组最末尾的节点覆盖到待删除节点的位置，该法更优，可以保证前n个节点都是有意义的。

        在删除过程中，如果删除的节点还有孩子，那么，其实是在删除以它为根的子树，此时就需要查询到这个子树包含的所有节点，很显然，这需要非常麻烦的遍历，非必要不用顺序存储。

3.孩子表示法

        顺序+链式存储，用数组储存所有节点，在节点内部用链式结构储存与它直接相连的孩子节点下标（没有孩子的孩子，没有孙子辈的）。

        特性：找孩子简单，找父亲难。

        i.代码

//链表节点的结构
class CTNode
{
public://孩子节点在数组中的位置int child;//下一个节点（下一个儿子，不是孙子）CTNode* next;
};
//包含链表的节点
class CTBox
{
public://数据int data;//第一个孩子CTNode* firstChild;
};
//树
class CTree
{
public:CTBox nodes[MAX];//指示已有节点数和根节点的位置int n, r;
};

        同样也有一个弊端，就是难以找到双亲。

4.孩子兄弟表示法

        此法为链式存储，旨在把一般树转化为二叉树存储，这也是最重要的方法。

        节点中，有两个指针，一个指示自己的第一个孩子（是否有孩子），一个指示自己的兄弟（是否有兄弟）。

        通过这种遍历，就将一般树转化为二叉树存储

        i.代码

class CSNode
{
public:int data;//第一个孩子和右兄弟指针CSNode* firstchild,* nextbrother;
};
using CSTree = CSNode*;

        此法可以用来存储森林，每个树都转为二叉树，每个根节点都是平级的，可以看着兄弟结点。

5.树的先根遍历（深度优先遍历）

        先根：先访问根节点，再依次对子树进行先根遍历。

        在孩子兄弟表示法中，对一般树的先根遍历，与其对应的二叉树的先序遍历相同。

        代码中的部分内容会因为选择的存储结构的不同而有差异。

        i.代码

        以下，用孩子兄弟表示法作为存储结构，

class CSNode
{
public:int data;//第一个孩子和右兄弟指针CSNode* firstchild,* nextbrother;
};
using CSTree = CSNode*;//先根遍历
void PreOrder(CSTree p)
{if (p != nullptr){//访问（子树的）根节点visit(p);//如果该节点还有孩子，则去访问孩子if (p->firstchild != nullptr){CSNode* n = p->firstchild;PreOrder(n);}//如果该节点还有兄弟，则再去访问if (p->nextbrother != nullptr){CSNode* m = p->nextbrother;PreOrder(m);}}
}

6.树的后根遍历（深度优先遍历）

        后根：其逻辑与后序遍历类似，但是在孩子兄弟表示法中，出现了不同，一般树的后根遍历，与其对应的二叉树的中序遍历相同，这很反直觉。

        

7.树的层次遍历（广度优先遍历）

        即，逐层遍历，与二叉树的层序遍历逻辑基本相同，使用队列来辅助实现。

        · 队列为空，根节点入队

        · 队列非空，队头出队（并访问），同时队头如果有孩子，则其孩子依次入队。

        依次重复以上两个步骤，直到队列再次为空。

8.森林的先序遍历（中序遍历也是同理的）

        将森林转换为二叉树，再进行先序遍历，就是森林的先序遍历。

9.总结图