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

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

article 2024/10/31 16:17:20

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

树的存储结构

双亲表示法

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

[data1:parent1;

data2:parent2;

...

dataN:parentN;]

用列表表示：

data

parent

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

#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$

$\dots$

$child_M$

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

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

2.孩子链表表示法

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

data	firstchild

链表firstchild中的孩子结点为：

child

存储类型定义如下：

#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;

如下图：

。

孩子双亲表示法

拼接，无需多言。

data

parent

firstchild

孩子兄弟表示法

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

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

firstchild

data

nextsibling

存储类型定义如下：

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;
}