当前位置：首页 > news >正文

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

news 2025/7/7 1:28:24

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);}}
}