当前位置:   article > 正文

数据结构(5.4_1)——树的存储结构

数据结构(5.4_1)——树的存储结构

树的逻辑结构

双亲表示法(顺序存储)

每个结点中保存指向双亲的“指针”

  1. #define MAX_TREE_SIZE 100//树中最多结点
  2. typedef struct {//树的结点定义
  3. int data;//数据元素
  4. int parent;//双亲位置域
  5. }PTNode;
  6. typedef struct {//树的类型定义
  7. PTNode nodes[MAX_TREE_SIZE];//双亲表示
  8. int n;//结点数
  9. }PTree;

增加结点操作 

新增数据元素无需按逻辑上的次序存储,之家在上一个结点后添加新结点,并记录双亲结点

 

删除叶结点操作 

1、删除结点数据域                           

2、将尾部数据移动至删除结点位置填充空缺

删除非叶结点操作  

寻找其双亲结点相同的结点

孩子表示法 (顺序+链式存储)

顺序存储各个节点,每个结点中保存孩子的链表头指针

  1. #define MAX_TREE_SIZE 100//树中最多结点
  2. struct CTNode {
  3. int child;//孩子在结点数组中的位置
  4. struct CTNode* next;//下一个孩子
  5. };
  6. typedef struct {
  7. int data;
  8. struct CTNode* firstChild;//第一个孩子
  9. }CTBox;
  10. typedef struct {
  11. CTBox nodes[MAX_TREE_SIZE];
  12. int n, r;//结点数和根的位置
  13. }CTree;

孩子兄弟表示法(链式存储) 

 

  1. /树的存储——孩子兄弟表示法
  2. typedef struct CSNode {
  3. int data;
  4. struct CSNode* firsitchild, * nextsilbling;//第一个孩子和右兄弟指针
  5. }CSNode,*CSTree;
  6. int main() {
  7. return 0;
  8. }

树和二叉树的转化:

使用孩子兄弟表示法

 

森林和二叉树的转化 

森林—>二叉树

二叉树—>森林

 

总结: 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/煮酒与君饮/article/detail/921822
推荐阅读
相关标签
  

闽ICP备14008679号