精华内容
下载资源
问答
  • 树存储结构的几种表示方法

    万次阅读 2017-12-03 16:31:49
    名称:树存储结构的几种表示方法 说明:对于树的存储结构,一般有以下三种表示方法。 (1)、双亲表示法。这种存储方式采用一组连续的空间来存储每个结点,同时在每个结点中增设一个伪指针, 指示其双亲在结点...

    /*
    名称:树存储结构的几种表示方法
    说明:对于树的存储结构,一般有以下三种表示方法。
    (1)、双亲表示法。这种存储方式采用一组连续的空间来存储每个结点,同时在每个结点中增设一个伪指针,
    指示其双亲在结点中的位置。这种方式比较容易找到双亲,但是不容易找到孩子。
    (2)、孩子表示法。这种方法是将每个结点的孩子结点都用链表链接起来形成一个线性结构。这种方式比较
    容易找到结点的孩子,但是不容易找到其双亲。
    (3)、孩子兄弟表示法。这种方式通俗的说是:“左结点是第一个孩子,右结点是下一个兄弟”。这种方式比较灵活,因为其可以转化为二叉树,对其的操作一般都能转化为二叉树的相关操作。

    总之,选用不同的存储结构要根据具体的用途。(这当然是废话)。想说的是,在做一些题的时候,如果可以不用
    选用二叉树这种相对复杂的存储结构,那就选择线性的结构。对我来说,线性结构比二维的树的结构用的顺手。

    */

    //树的存储结构之双亲表示法
    
    //树的结点定义
    typedef struct
    {
        int data;   //数据元素
        int parent;     //双亲的位置
    }PTNode;
    
    //树的类型定义
    typedef struct
    {
        //PTNode nodes[MAXSIZE];      //双亲表示
        int n;                  //结点数
    }PTree;
    
    
    //树的存储结构之孩子表示法
    
    //链表中孩子结点表示
    typedef struct CHNode
    {
        int pos;   //孩子的位置
        CHNode *next;    //指向下一个孩子的指针
    }CHNode;
    
    
    //数组中双亲结点表示
    typedef struct CHNode1
    {
        int data;       //数据元素
        CHNode *firChild;   //指向第一个孩子的指针
    
    }CHNode1;
    
    //树的类型表示
    typedef struct
    {
        CHNode1 nodes[MAXSIZE];     //所有的结点
        int n;      //节点的个数
    }CHTree;
    
    
    
    //树的存储结构之孩子兄弟表示法
    typedef struct CSNode
    {
        int data;   //结点的数据
        CSNode *firstchild,*nextbling;   //第一个孩子和下一个兄弟
    
    }CSNode,*CSTree;
    
    
    
    
    展开全文
  • 线索二叉树及树存储结构

    千次阅读 2018-09-03 21:13:43
    由于二叉链表作为存储结构时,只能找到结点的左右孩子信息,而不能直接得到结点在任一序列的直接前趋和直接后继信息,另一方面,在有n个结点的二叉链表中必定存在n+1个空链域(证明:对于除了根结点以外,其他每个...

    线索二叉树

    由于二叉链表作为存储结构时,只能找到结点的左右孩子信息,而不能直接得到结点在任一序列的直接前趋和直接后继信息,另一方面,在有n个结点的二叉链表中必定存在n+1个空链域(证明:对于除了根结点以外,其他每个结点都有一个父结点,所以一共有n-1个指针指向某个结点,一共有2n个空链域,故2n-(n-1)=n+1)),为了利用这些空链域来存放结点的前趋、后继信息,于是有了线索二叉树。

    规定如下:在原来二叉树结点的结构上增加两个标志域,如图

    Lchild LTag data RTag

    Rchild

    其中:

    Ltag=0 ,Lchild域指向结点的左孩子;

    Ltag=1 ,Lchild域指向节点的前趋;

    Rtag=0 ,Rchild域指向结点的右孩子;

    Rtag=1 ,Rchild域指向节点的后继;

    这种结点结构构成的二叉链表称为线索链表,其中指向结点前趋和后继的指针,叫作线索,加上线索的二叉树叫做线索二叉树,对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化

    树的存储结构

    通常有三种链表结构来表示树,分别是:双亲表示法,孩子表示法,孩子兄弟表示法。

    双亲表示法:

    data parent

    data是该结点的数据域,parent是指针域,指向其父结点,这种存储结构利用了每个结点(除根结点外)只有唯一的双亲性质,

    这样的存储结构,我们可以根据结点的parent指针很容易找到它的双亲结点,所用的时间复杂度为O(1),但求节点的孩子时,却需要遍历整个结构。

    孩子表示法:

    孩子表示法分为两种情况:

    情况一:

    data child1 child2 ... childd

    data表述数据域,child表示指向孩子的指针域

    d表示树的度,即各个结点度的最大值,由于树中很多结点小于d,所以链表中有很多空域,空间较浪费,因此有情况二来改善。

    情况二:

    data degree child1 ...

    childd

    data表示数据域,degree表示度域,child表示指针域。

    这种方法提高了空间的利用率,但是由于各个结点的结构不同,同时加上要运算各个结点的度,会在运算上造成时间浪费。

    很明显,可以看出,孩子法与双亲法优缺点恰好相反,孩子法便于那些涉及孩子的操作的实现。

    孩子兄弟表示法:

    data firstchild first right child

    data数据域,firstchild从左到右第一个孩子指针域,first right child右边第一个孩子指针域,这种存储结构易于找孩子,如果为了方便找父结点,则可以在每个节点增加一个父指针。其实这也是树与二叉树的一种转换方法。

     赫夫曼树:

    赫夫曼树又称最优树,是一类带权路径长度最短的树。

    首先介绍几个概念:

    路径长度:从树的一个结点到另一个结点之间的分支构成这两个结点之间的路径,路径的分支数目就称作路径长度。树的路径长度是从树根到每一个结点的路径长度之和。

    推广到一般情况,考虑带权的结点,结点的带权路径长度为从该结点到根结点的路径长度乘以该结点上的权。树的带权路径长度即各结点带权路径长度之和,

     

    算法思想:

    (1) 以权值分别为W1,W2...Wn的n各结点,构成n棵二叉树T1,T2,...Tn并组成森林F={T1,T2,...Tn},其中每棵二叉树 Ti仅有一个权值为 Wi的根结点;

    (2) 在F中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树,并且置新二叉树根结点权值为左右子树上根结点的权值之和(根结点的权值=左右孩子权值之和,叶结点的权值= Wi)

    (3) 从F中删除这两棵二叉树,同时将新二叉树加入到F中;

    (4) 重复(2)、(3)直到F中只含一棵二叉树为止,这棵二叉树就是Huffman树。


    图是一种较线性表和树更为复杂的数据结构,在线性表中,数据元素之间仅有线性关系,每个数据只有一个直接前趋和一个直接后继,在树形结构中,数据元素之间有着明显的层次关系,且每一层数据元素可能和下一层的多个元素相关,但只能和上一层中的一个元素相关,在图形结构中,结点之间的关系可以是任意的,图中任意俩个元素之间都可能相关。

    展开全文
  • 存储结构

    千次阅读 2016-08-24 15:46:15
    ---- 中某个结点的孩子可以有多个,这就意味着,无论按何种(顺序存储结构)顺序将中所有结点存储到数组中,结点的 存储位置都无法直接反映逻辑关系。所以简单的顺序存储结构是不能满足的实现要求的。 ---- ...

    1、顺序存储结构:用一段地址连续的存储单元依次存储数据元素。

    ---- 树中某个结点的孩子可以有多个,这就意味着,无论按何种(顺序存储结构)顺序将树中所有结点存储到数组中,结点的

    存储位置都无法直接反映逻辑关系。所以简单的顺序存储结构是不能满足树的实现要求的

    ---- 可以充分利用顺序存储和链式存储结构的特点,实现对树的存储结构的表示。

    ---- 目前主要有3种不同的树的存储结构:双亲表示法、孩子表示法、孩子兄弟表示法。

    2、双亲表示法

    ---- 树这种结构:除了根结点外,其余每个结点,它不一定有孩子,但是有且仅有一个双亲。

    ---- 双亲表示法是以一组连续的存储空间存储树的结点,同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置

    这种存储结构利用率每个结点(根结点除外)只有唯一的双亲的性质。约定根结点的指针域设置为-1.

    ---- 结构如下图所示:

       

    ---- 其中data是数据域,存储结点的数据信息。而parent是指针域,存储该结点的双亲在数组中的下标

    ---- 双亲表示法结点结构定义代码:

    #define MAX_TREE_SIZE 100
    typedef int TElemType;
    typedef struct PTNode //结点结构
    {
    	TElemType data;//结点数据
    	int parent; //双亲位置
    } PTNode;
    typedef struct  //树结构
    {
    	PTNode nodes[MAX_TREE_SIZE];//结点数组
    	int r,n;	//根的位置和结点数
    } PTree;
    下图中展示了树的结构和树的双亲表示:

           

    ---- 这样的存储结构,我们可以根据结点的parent指针很容易找到它的双亲结点,但找孩子结点难。

    3、孩子表示法

    ---- 由于树中每个结点可能有多棵子树,因此可以使用多重链表,即每个结点包含多个指针域,其中每个指针指向一棵子树的

    根结点,我们把这种方法叫做多重链表表示法。不过,树的每个结点的度(结点的孩子个数)是不同的。两种方案:

    --1)每个结点的指针域的个数等于树的度d。

    其结构如下表所示:

        

    树的度是各个结点的度的最大值,这种方法对于树中各结点的度相差很大时,空间浪费严重(有很多结点的度小于d),出现许多

    空的指针域。如果树的各结点度相差很小时,开辟的空间被充分利用了,这时存储结构的缺点就变成了优点。

    --2)每个结点指针域的个数等于该结点的度。

    需要专门设置一个位置来存储结点指针域的个数,其结构如下表所示:

        

    其中data为数据域,degree为度域,就是存储该结点的孩子结点的个数,child1到childd为指针域,指向该结点的各个孩子的结点。

    这种方法克服了浪费空间的缺点,但是由于各个结点的链表是不同的结构,还要维护结点的度的数值,运算上损耗时间。

    ---- 孩子表示法的具体办法是:把每个结点的孩子结点排列起来,以单链表作为存储结构,则n个结点有n个孩子链表,如果是叶子

    结点则此单链表为空。然后n个头指针又组成一个线性表,采用顺序存储结构,存放进一个一维数组中。

         

    为此,设计两种结点结构,一个是孩子链表的孩子结点,如下图所示:

                                   

    ---- 其中child是数据域,用来存储某个结点在表头数组中的下标,next是指针域,用来存储指向某结点的下一个孩子结点的指针。

    另一个是表头数组(线性表)的表头结点,如下表所示:

                                 

    ---- 其中data是数据域,存储某结点的数据信息。firstchild是头指针域,存储该结点的孩子链表的头指针。

    孩子表示法的结构定义代码如下:

    #define MAX_TREE_SIZE 100
    typedef int TElemType;
    typedef struct CTNode //孩子结点
    {
    	int child;//孩子结点所在下标
    	struct CTNode * next;
    } *ChildPtr;
    typedef struct	//表头结构
    {
    	TElemType data;
    	ChildPtr firstchild; //指向孩子结点的指针
    } CTBox;
    typedef struct  //树结构
    {
    	CTBox nodes[MAX_TREE_SIZE];//结点数组
    	int r,n;	//根的位置和结点数
    } PTree;
    ---- 这样的结构对于我们要查找某个结点的某个孩子,或者找某个结点的兄弟,只需要查找这个结点的孩子单链表即可。

    对于遍历整棵树也是很方便的,对头结点的数组循环即可。

    ---- 特点:找双亲难,可以在上面的表头结构中加入结点对应的双亲所在的数组下标。

    4、孩子兄弟表示法

    ---- 孩子兄弟表示法又称作二叉树表示法或二叉链表表示法,即以二叉链表作为树的存储结构。

    链表中结点的两个指针分别指向该结点的第一个孩子下一个兄弟结点,结点结构如下表:

               

    ---- 其中data是数据域,firstchild为指针域,存储该结点的第一个孩子结点的存储地址(指向第一个孩子结点)。

    rightsib是指针域,存储该结点的第一个孩子的右兄弟结点的存储地址(指向该兄弟结点)。

    ---- 结构定义代码如下;

    typedef int TElemType;
    typedef struct CSNode 
    {
    	TElemType data;
    	struct CSNode * firstchild,*rightsib;
    } CSNode,*CSTree;
    这种方法实现的示意图如下图所示:

            



    展开全文
  • 通用存储结构

    千次阅读 2016-03-13 20:57:37
    存储结构难点:无法直接用数组表示的逻辑结构 但是却可以设计结构体数组对结点间的关系进行表述 如下图:(用一个表格描述图中的) 那么问题来了: 1. 结构需要添加和删除结点,数组存储是否足够灵活? ...

    树的存储结构难点:无法直接用数组表示树的逻辑结构

    但是却可以设计结构体数组对结点间的关系进行表述

    如下图:(用一个表格描述图中的树)


    那么问题来了:

    1. 树结构需要添加和删除结点,数组存储是否足够灵活?

    答:树经常需要动态的插入和删除结点,数组存储肯定不够灵活。

    2. 每个结点的子节点可以有多个,如何存储?

    答:看下面


    树的存储结构:

    1. 利用链表组织树中的各个结点

    2. 链表中的前后关系不代表结点间的逻辑关系

    3. 结点的逻辑关系由child数据域描述

    4. child数据域保存其他结点的存储地址


    树结点结构体:

    typedef   struct   _tag_GTreeNode   GTreeNode;

    struct _tag_GTreeNode

    {

    GTreeData* data;//用于保存数据

    GTreeNode* parent;//指向双亲的指针

    LinkList* child;//链表用于存储多个孩子的地址,

    };


    链表结点结构体:

    typedef   struct   _tag_TLNode   TLNode;

    struct _tag_TLNode

    {

    LinkListNode header;

    GTreeNode* node;//一个指向树结点的指针

    } ;


    链表的结构体定义:

    typedef   void   LinkList;
    typedef   struct   _tag_LinkListNode   LinkListNode;
    struct _tag_LinkListNode
    {
        LinkListNode* next;//链表指针域
    };

    typedef   struct   _tag_LinkList
    {
        LinkListNode header;//链表头
        int length;//链表长度
    } TLinkList;


    要维护每一个结点和双亲之间的连接,对于每一个新加进来的树节点都必须将它的parent指针指向它的双亲结点

    下图中红色箭头标识部分。

    图示:


    链表表示形式图示:(蓝色的线)

    通过蓝色线的图示部分是可以访问树中的每一个结点

    那么怎么表示图中的绿色线表示的部分呢?



    详细架构图:

    先看最下边的是一个组织链表,组织链表里面的每个元素都有一个指针指向一个树结点

    第0个元素的指针指向了根节点A,第1个元素的指针指向了结点B,第2个元素的指针

    指向了结点C......

    结点之间的关系如何真实的表现?

    看蓝色的箭头,A的child链表有三个元素,每个元素保存的是A结点的孩子的地址(也就是指向BCD的指针)

    通用树结构实现的一种模型!是不是很神奇!反正第一个想出这样的人真的好牛逼啊!





    最后总结:1. 上面的树结构是一种通用树的数据结构

      2. 利用链表组织树结点能够便利的存取结点,但是链表的维护具有一定的复杂性

      3.  树结构的非线性特性和递归定义的特性是树结构难度较大的根本原因






    展开全文
  • 数据结构(C语言)存储结构

    千次阅读 2020-07-08 21:01:24
    存储结构 1、双亲表示法 实现 :定义结构数组,存放的结点,每个结点包含两个域: 数据域 :存放结点本身信息 双亲域 :指示本结点的双亲结点在数组中的位置 存储结构 数组下标 data parent 0 R...
  • 存储结构(双亲表存储结构

    千次阅读 2014-08-24 22:56:26
    c6-4.h(见图627 所示)是用顺序结构存储的。它是定长的(100 个结点),由n 来 确定有效结点数。parent 域的值为-1 的是根结点。图628 是教科书中图6.13 所示之 及其双亲表存储结构
  • redis存储树结构数据

    千次阅读 2019-10-03 08:00:51
    本文主要讲解两方面内容:1.redis如何存储树结构数据。2.java操作redis时选取哪种序列化器。 redis如何存储树结构数据 先抛出结论,树结构数据在redis中的存储顺序如下: ...
  • 及二叉树的存储结构

    千次阅读 2014-06-09 21:39:21
    一般存储结构: 1.
  • Java数据结构-存储结构

    千次阅读 2015-07-23 00:06:45
    的定义:n(n>=0)个节点的有限集。 n=0时称为空。 n!=0时为非空,有且仅有一个特定的节点——根;n>1时,其它节点可以分为m(m>0)个互不相交的有限集T1~Tm,其中每一个集合本身又是一棵,并且称为根的子树...
  • 存储结构 和 代码实现

    千次阅读 2017-02-16 21:54:37
    存储结构 和 代码实现
  • 存储结构-双亲表示法-代码

    千次阅读 2017-05-09 10:19:45
    存储结构:双亲表示法
  • 先分别说下三种不同的表示法:双亲表示法、孩子表示法、孩子兄弟表示法 ...的节点结构那么存储起来就是这样的 双亲节点结构定义代码 #define MAX_TREE_SIZE 100 typedef char ElementType; // 的节点 ...
  • 的三种存储结构

    万次阅读 多人点赞 2017-03-19 19:46:38
    之前我们一直在谈的是一对一的线性结构,可现实中,还有很多一对多的情况需要处理,所以我们需要研究这种一对多的数据结构----"",考虑它的各种特性,来解决我们在编程中碰到的相关问题。 (Tree)是n(n>=0)个...
  • 数据结构之的三种存储结构

    万次阅读 2014-04-28 23:36:21
    说道存储结构,我们就会
  • 一般存储结构 森林的存储结构 的基本术语 1)结点:中的一个独立单元,包括数据域(存储数据元素信息)和一个或若干个指针域(如存储直接后继位置的域)。 /*-------结点的数据结构-------*/ typedef...
  • 存储结构: 孩子表示法:把每个结点的孩子结点排列起来,以单链表作存储结构,则n个结点有n个孩子链表,如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表,采用顺序存储结构,存放进一个一维数组中...
  • 存储结构以及各自优缺点

    千次阅读 2016-02-29 07:54:07
    存储结构主要有:双亲表示法,孩子表示法,双亲孩子表示法和孩子兄弟表示法。 双亲表示法:该种方法寻找一个节点的双亲结点比较方便,但是对于寻找一个节点的孩子节点操作实现却不太方便。 孩子表示法:该方法...
  • 的顺序存储结构

    千次阅读 2019-01-25 17:20:05
     用一组连续的存储空间存储树的结点,同时再每个结点中,用一个变量存储该结点的双亲结点在数组中的位置 #define MaxSize 50 typedef int Elemtype; typedef struct TNode { Elemtype data; //结点数据 int ...
  • mysql存储树结构的数据

    万次阅读 2017-12-03 23:46:58
    JSON格式的结构数据需要保存到mysql中。 形图如下: 分析成文本如图: 存到表中的结构为: 需求 一般结构的数据使用需求有两点: 显示整棵的数据 select * from treeNodes 给出某个点,显示...
  • 系列之二:存储结构

    万次阅读 2012-03-19 15:09:11
    一:存储结构   1 双亲表示法     // 双亲表示法 // 找双亲易,找孩子难 template class TreeNode { public: TreeNode(Type i=0,int pa=0):data(i),parent(pa) { } private: ...
  • 的孩子兄弟存储结构

    千次阅读 2010-06-14 20:44:00
    ,孩子兄弟存储结构
  • 之前已经谈过了存储结构,并且说到顺序存储对这一种一对多的关系的结构实现起来比较困难。但是二叉树是一种特殊的,由于它的特殊性,使得用顺序存储结构也可以实现。 二叉树的顺序存储结构 二叉树的顺序...
  • 许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。   二叉树特点是每个结点最多只能有两棵子树,且有...
  • 是一种非线性的数据结构,可以使用链表组织的各个节点,描述的一些常用操作。双亲孩子表示法是指每个结点都有一个指向其双亲的指针,每个结点都有若干个指向其孩子的指针。
  • 结构-结构的数据存储与数据库表设计结构一般用于无限级分类,无论你使用Java,.Net,PHP,Python等语言平台进行开发应用,结构都是很常用的结构设计之一。本文主要解决结构的数据存储和数据库表...
  • 参考了《大话数据结构》中的定义:typedef struct CTNode{//孩子结点 int child; struct CTNode *next; } *ChildPtr;typedef struct{//表头结构 char data; ChildPtr firstchild; }CTBox;typedef str
  • 哈希存储引擎 B树存储引擎 LSM树存储引擎 并发控制 存储快照实现原理
  • 结构数据存储方案之闭包表

    千次阅读 2019-03-13 19:05:50
    本人目前的项目是微信公众号的一个小型电商系统,需要将邀请好友模块优化成5级分销流程,参考此文章,我选用【闭包表】模式,结构数据存储方案全部介绍见另一篇文章。待本人项目完成奉上自己的项目流程及数据库...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 409,032
精华内容 163,612
关键字:

树的存储结构