树形结构展示的数据缓存到redis 树形结构存储

admin2024-05-30  27

12黑马笔记之树的存储结构

1 树的存储结构也分与线性存储一样,分为顺序存储和链式存储。

2 树的顺序存储:
1)可规定为,从上至下、从左至右将树的结点依次存入内存。
2)重大缺陷:复原困难(不能唯一复原就没有实用价值)。
例如双亲表示法。定义一个结构体,将数据放进结构体中,然后将节点存进数组中。

//双亲表示法
typedef struct SNODE{
     int data;
     int parent_pos;//双亲表示法,记录节点的双亲
}

上面可以看出,知道一个节点,只能知道他的双亲,而不知道他的儿子们,所以复原困难,必须遍历整个数组,浪费时间精力。

3 树的链式存储:
可用多重链表:一个前趋指针,n 个后继指针。
细节问题:树中结点的结构类型样式该如何设计?
即应该设计成“等长”还是“不等长”?
缺点:等长结构太浪费(每个结点的度不一定相同);不等长结构太复杂(要定义好多种结构类型)。

例如,抛开前趋指针,用孩子表示法为例。利用结构体存放数据,使用指针记录每个节点的所有孩子。假设使用等长,即以最多的孩子节点设置多个指针,但是少孩子的那不是很浪费吗?所以又假设使用不等长,指针只需要一个,即当成链表,将所有孩子连接起来,但是操作起来又非常麻烦。所以我们存储之前先将普通树转化为简单的树存储。就是利用左孩子右兄弟表示法,将多个后继的树转为只有两个后继的简单二叉树。

//孩子表示法
typedef struct SNODE{
      int data;
      SNODE Child1;
      SNODE Child2; //到底需要多少个呢?
      //...
}Snode;

4 比较重要的左孩子右兄弟表示法:

直接看图。

1)一棵普通的具有多个后继的树。

树形结构展示的数据缓存到redis 树形结构存储,树形结构展示的数据缓存到redis 树形结构存储_数据结构,第1张

2)通过左孩子右兄弟表示法后,将其转化成简单的二叉树。极大的方便了我们的存储树的节点数据。

树形结构展示的数据缓存到redis 树形结构存储,树形结构展示的数据缓存到redis 树形结构存储_数组_02,第2张


本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!