织梦网站动态,国家企业信息系统查询系统,ftp网站备份,怎么做公司网站制作1.知识总览 一般的树会有多个孩子#xff0c;所以存储结构也会与二叉树略有不同。 一般树的遍历。
2.双亲表示法 双亲表示法#xff0c;也是父亲表示法#xff0c;即每个节点中都存储了其父节点的地址信息。 特性#xff1a;可以轻易地找到父节点#xff0c;但寻找孩子节…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.总结图
