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

树的存储结构

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

【方法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;  //指针域,分别指向第一个还结点和下一个兄弟结点。
}


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

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

分享给朋友:

相关文章

字符串的输入输出汇总

做字符串的题目的时候,经常会遇到输入输出不对的情况,这篇文章就简单总结一下字符串常见的输入输出。2.cin基本操作:#include<iostream> #include<cstd...

DEVC++中的断点调试

DEVC++中的断点调试

1.调试程序的两种方法编程的时候经常会遇到自己的输出结果跟标准结果或者预期的结果不一样,这个时候就要用到调试程序的功能。调试程序的目的有两个,一个是找出程序中的错误,另一个是监视变量的变化。2.DEV...

【数论】快速乘

【数论】快速乘

上一篇文章简单说了龟速乘的问题,有人觉得龟速乘还是太慢了,有没有什么办法再快一点,实际是有的,就是我们今天介绍的 快速乘。快速乘的原理和龟速乘不同,快速乘并不是基于二进制和位运算,严格来说,快速乘是利...

【数论】组合数学—容斥原理

【数论】组合数学—容斥原理

概念在计数时,必须注意没有重复,没有遗漏。为了使重叠部分不被重复计算,人们研究出一种新的计数方法,这种方法的基本思想是:先不考虑重叠的情况,把包含于某内容中的所有对象的数目先计算出来,然后再把计数时重...

【入门篇】>>> DEVC++下载、安装、简单使用

【入门篇】>>> DEVC++下载、安装、简单使用

什么是DEVC++    DEVC++是一款编程工具,是一个Windows环境下的一个适合于初学者使用的轻量级C/C++ 集成开发环境(IDE),它是一款自由软件,遵守G...

【算法】前缀和与差分(3)二维数组前缀和

【算法】前缀和与差分(3)二维数组前缀和

0.前言前面的一篇文章,介绍了一维数组的前缀和,这篇文章中,介绍一下二维数组的前缀和1.定义二维数组的前缀和就是按照二维数组求和。公式如下:那二维前缀和中一个f[i][j]表示的意思就是以(1,1)为...