树的存储结构及详细完整代码 |
您所在的位置：网站首页 › 叶子结点的双亲 › 树的存储结构及详细完整代码 |
树的存储结构及详细完整代码
|
文章目录
树的存储结构双亲表示法孩子表示法孩子兄弟表示法
树的存储结构
树的存储方式有多种，既可以采用顺序存储结构，又可以采用链式存储结构，但无论何种存储方式，都要求能够唯一的反映树中各结点之间的逻辑关系。 常用的存储结构主要有： 双亲表示法 孩子表示法 孩子兄弟表示法 双亲表示法采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。 如下图所示，根结点的下标为0，其伪指针域为-1。 这种双亲表示法的存储结构描述如下： #define MaxSize 100 //树中最多结点数 typedef struct{ //树的结点定义 char data; //数据元素 int parent; //双亲位置域 }PTNode; typedef struct{ //树的类型定义 PTNode nodes[MaxSize]; //双亲表示 int n; //结点数 }PTree;对于上图的完整代码实现如下： #include using namespace std; #define MaxSize 100 //树中最多的结点数 typedef struct{ //结点定义 char data; //数据 int parent; //双亲位置域 }PTNode; typedef struct{ PTNode nodes[MaxSize]; //双亲表示,存放树中所有结点 int n; //结点数 }PTree; //树的结点初始化 PTree InitPNode(PTree tree){ couttree.n; cout couta; //输入要查询的结点值 int flag = 0; for(int i=0; i flag = 1; if(i == 0){ //此时为根结点 cout PTree tree; tree = InitPNode(tree); FindParent(tree); return 0; } 运行结果为： 将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时n个结点就有n个孩子链表（叶子结点的孩子链表为空表），如下图所示。
特点：孩子表示法这种存储方式寻找子女的操作非常直接，而寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表。 树的孩子表示法采用的是**“顺序表+链表”**的组合结构，其存储过程为，从树的根结点开始，使用顺序表依次存储树中各个结点，并给每一个结点分配一个链表，用于存储各个结点的孩子结点位于顺序表中的位置。如果该结点没有孩子结点（即是叶子结点），则该结点的链表为空链表。 对于上图的完整实现代码如下： #include using namespace std; #define MaxSize 100 typedef struct ChildNode{ //链表中每个结点的定义 //链表中每个结点存储的不是数据本身，而是数据在数组中存储的位置下标 int child; struct ChildNode *next; }ChildNode; typedef struct{ //树中每个结点的定义 char data; //结点的数据类型 ChildNode *firstchild; //孩子链表头指针 }CHNode; typedef struct{ CHNode nodes[MaxSize]; //存储结点的数组 int n; }CTree; //树中结点初始化 CTree InitTree(CTree tree){ couttree.n; for(int i=0; i ChildNode *p = tree.nodes[i].firstchild; //p为操作指针 for(int j=0; j int flag = 0; for(int i=0; i cout cout char data; //数据域 struct CSNode *firstchild, *nextsibling; //第一个孩子和右兄弟指针 }CSNode, *CSTree;特点：孩子兄弟存储表示法比较灵活，其最大的优点是可以方便的实现树转换为二叉树的操作，易于查找结点的孩子等；缺点是从当前结点查找其双亲结点比较麻烦。 若为每一个结点增设一个parent域指向其父结点，则查找结点的父结点也很方便。 通过孩子兄弟表示法，任意一棵普通树都可以相应转化为一棵二叉树，也就是说，任意一棵普通树都有唯一一颗二叉树与之对应。 这种方式的代码实现与二叉树的操作大致相同，故不再给出。 |
【本文地址】
今日新闻 |
推荐新闻 |