当前位置: 首页 > article >正文

【数据结构】五分钟自测主干知识(十二)

上一讲,我们讲述了线索二叉树,今天,我们来进入“树”这一概念的最后一节——“树和森林”。


树的存储结构

双亲表示法

由树的定义,树中每一个结点至多有一个双亲(不是2个‘亲’啊)。则可以使用一个一维数组,让每个结点数据data指示他的双亲parent。

[data1:parent1;

data2:parent2;

...

dataN:parentN;]

用列表表示:

dataparent

双亲表示法的存储类型定义如下:

#define MaxSize 100
typedef struct{
    TElemType data;
    int parent;
}PTNode;
typedef struct {
    PTNode Nodes[MaxSize];
    int root;
    int n;
}FTree;

 结点双亲域的值为-1时,表示该结点没有双亲。示意图如下:

双亲表示法容易找一个结点的双亲,但找它的孩子需要遍历整个树。于是我们为了找孩子,订了孩子表示法。


孩子表示法

1.多重链表表示法

data$child_1$$child_2$\dotschild_M

其中M为树的度。而由于很多结点的度小于M,即它没有那么多子结点,这些空余的子结点都会设为NULL,很消耗空间。可能只有二叉树等特定结点的树才会这样表示。

具体内容略。我们将下一个更优方法。


2.孩子链表表示法

把每个结点后面的孩子,连接成一个单链表,称为孩子链表。

datafirstchild

链表firstchild中的孩子结点为:

childnext

存储类型定义如下:

#define MaxSize 100
typedef struct ChildNode{
    int child;
    struct ChildNode* next;
}ChildNode,*ChildPtr;
typedef struct {
    TElemType data;
    ChildPtr firstchild;
}CTNode;
typedef struct {
    CTNode nodes[MaxSize];
    int n;
    int root;
}CTree;

如下图:


孩子双亲表示法

拼接,无需多言。

dataparentfirstchild

孩子兄弟表示法

采用二叉链表来存储一棵树,又称为二叉树表示法,或二叉链表表示法。

每个结点的“长子”,每个孩子结点的“右邻兄弟”都是唯一的。于是我们给每个树结点设置两个指针域:firstchild,nextsibling。

firstchilddatanextsibling

存储类型定义如下:

typedef struct CSNode{
    TElemType data;
    struct CSNode* firstchild,*nextsibling;
}CSNode,*CSTree;

示例图如下:


树,森林,二叉树的转换

森林转换为二叉树

 森林的存储结构:一般采用孩子兄弟表示法

typedef struct CSNode {
  TElemType data;
  CSNode *firstchild, *nextsibling;
} *CSTree;

森林的遍历

先序:访问第一棵树的根、先序遍历第一棵树的子树、先序遍历其他树

中序:中序遍历第一棵树的子树、访问第一棵树的根、中序遍历其他树

例如上图森林:

先序遍历: ABCDEFGHIJ

中序遍历: BCDAFEHJIG

先根遍历树(孩子链表)

void PreOrderRecur(CTree T, int loc, void (*Visit)(TElemType)) {
  if (loc == -1) return;
  Visit(T.nodes[loc].data);
  ChildPtr p;
  for (p = T.nodes[loc].firstchild; p; p = p->next) {
    PreOrderRecur(T, p->child, Visit);
  }
}
void PreOrderTree(CTree T, void (*Visit)(TElemType)) {
  PreOrderRecur(T, T.root, Visit);
}

计算树的深度:

int TreeDepth(CSTree T) {
  if (!T) return 0;
  CSTree p; int maxh = 0;
  for (p = T->firstchild; p; p = p->nextsibling) {
    int h = TreeDepth(p);
    if (h > maxh) maxh = h;
  }
  return maxh + 1;

计算树的度:

int TreeDegree(CSTree T) {
  int degree = 0, k = 0;
  if (T) for (CSTree p = T->firstchild; p; p = p->nextsibling) {
    ++k;
    int d = TreeDegree(p); if (d > degree) degree = d;
  }
  if (k > degree) degree = k;
  return degree;
}

Huffman 编码

具体内容CSDN中已有非常详尽的介绍,可根据下文进行复习工作:

哈夫曼编码(Huffman Coding)原理详解-CSDN博客


下一讲,我们进行图论的介绍。附链接如下:未完待续

goodbye~


http://www.kler.cn/a/373199.html

相关文章:

  • 计算机科学与技术-毕业设计选题推荐
  • 状态机模型
  • DataSophon集成ApacheImpala的过程
  • Java 虚拟机是什么?——探秘 JVM 的核心机制!
  • go语言中流程控制语句
  • QT 中彻底解决中文乱码问题的指南
  • 两步GMM计算权重矩阵
  • HTML5新增属性
  • 蓝桥杯练习笔记(十九-质数筛)
  • Github 2024-10-27 php开源项目日报 Top10
  • 【verilog】模十计数器
  • 电商直播带货乱象频出,食品经销商如何规避高额损失?
  • Word 每次打开时都会弹出“要还原的文件”对话框
  • iframe视频宽度高度自适应( pc+移动都可以用,jq写法 )
  • Unity控制物体透明度的改变
  • Matplotlib 网格线
  • PostgreSQL 删除角色
  • 面向对象高级-static
  • 为什么选择 Spring data hadoop
  • 蓝牙BLE开发——红米手机无法搜索蓝牙设备?
  • 编程小白如何成为大神?大学新生的最佳入门攻略
  • QT 12.自定义信号、信号emit、信号参数注册_ev
  • 【Python · Pytorch】人工神经网络 ANN(中)
  • Agile敏捷方法
  • 内存马浅析
  • 关于深度学习方向学习的一些建议