当前位置:首页 > C++知识 > 正文内容

树的存储结构

亿万年的星光4年前 (2021-11-27)C++知识20602

【方法1:数组】称为父亲表示法

const int m=10;                 //树的结点数
struct node{ 
    int data,parent;            //数据域,指针域
};
node tree[m];

优缺点:利用了数中除根结点外每个结点都有唯一的父结点这个性质。很容易找到数根。但是找孩子时需要遍历整个线性表。


【方法2:树形单链表结构】称为孩子表示法

每个结点包括一个数据域和一个指针域(指向若干子结点),称为“孩子表示法”。假设数的高度为10,数的结点仅存放字符,则这棵树的数据结构定义如下:

const int m=10;
typedef struct node;
typedef node * tree;
struct node
{
    char data;   //数据域
    tree child[m];  //指针域,指向若干孩子结点
};
tree t;

缺陷:只能从根(父)结点遍历到子结点,不能从某个子结点返回到它的父结点。但程序中确实需要从某个结点返回到它的父结点时,就需要在结点中多定义一个指针变量存放父结点的信息。这种结构又叫做带逆序的树型结构。

【方法3:树形双链表结构】称为父亲孩子表示法

每个结点包括一个数据域和两个指针域(一个指向若干子结点,一个指向父结点)。假设树的度为10,树的结点仅存放字符,则这棵树的数据结构定义如下:

const int m=0;
typedef struct node;
typedef node * tree;  //声明tree是指向node的指向类型
struct node
{
    char data;          //数据域
    tree child[m];      //指针域,指向若干孩子结点
    tree father;        //指针域,指向父结点
};
tree t;

【方法4:二叉树型表示法】称为孩子兄弟表示法

它是一种双链表结构,但每个结点包括一个数据域和一个指针域(一个指向该结点的第一个孩子结点,一个指向该结点的下一个兄弟结点)。假设树的高度为10,树的结点仅存放字符,则这棵树的数据结构定义如下:

typedef struct node;
typedef struct * tree;
struct node
{
    char data;  //数据域
    tree firstchild, next;  //指针域,分别指向第一个还结点和下一个兄弟结点。
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【入门篇】C++ 中变量的简单使用

【入门篇】C++ 中变量的简单使用

1.什么是变量”变量“通俗来讲就是能变的量。在程序设计中,变量是一个个不同类型的盒子,当盒子里装了苹果时,盒子就代表苹果,当然,我们需要给一个个盒子起不同的名字。像下面的图片一样,一个盒子,给他取一个...

C++中箭头指针的含义及用法

C++中箭头指针的含义及用法

0.前言c++中我们在一些程序中看到箭头 p—>stu 类似于这样的表示。今天就简单来解释一下点运算和箭头运算。1.点运算常见的点一般出现在结构体中,比如下面的代码:#include<io...

C++将数据写入磁盘文件

0.前言要求:在任意路径下新建一个文本文档,向该文档中写入数据。以'#'结束字符串的输入。关键技术:ch=fputc(ch,fp);该函数的作用是把一个字符写到磁盘文件(fp所指的磁盘...

符号与快捷键

符号与快捷键

一、键盘二、符号与快捷键1.常见符号加号:shift 加 =减号:-乘号:shift 加 8  (*)除号:/取余(模):shift 加 5    (%)【示例】#inc...

STL入门——容器1:vector (不定长度数组)

一、定义     vector是一个不定长度数组。不仅如此,它把一些常用操作“封装”在了 vector 类型内部。    ...

C++读取磁盘文件

0.前言简单介绍一下C++读取文件的基本操作。关键技术:freopen() 文件的打开函数 FILE *fp fp=fopen(文件名,使用文件方式) 例如: fp...