【数据结构】树与二叉树（十八）：树的存储结构——Father链接结构、儿子链表链接结构

5.1 树的基本概念

5.1.1 树的定义

• 一棵树是结点的有限集合T：
  • 若T非空，则：
    • 有一个特别标出的结点，称作该树的根，记为root(T)；
    • 其余结点分成若干个不相交的非空集合T1, T2, …, Tm (m>0)，其中T1, T2, …, Tm又都是树，称作root(T)的子树。
  • T 空时为空树，记作root(T)=NULL。

5.1.2 森林的定义

  一个森林是0棵或多棵不相交（非空）树的集合，通常是一个有序的集合。换句话说，森林由多个树组成，这些树之间没有交集，且可以按照一定的次序排列。在森林中，每棵树都是独立的，具有根节点和子树，树与树之间没有直接的连接关系。
  森林是树的扩展概念，它是由多个树组成的集合。在计算机科学中，森林也被广泛应用于数据结构和算法设计中，特别是在图论和网络分析等领域。

5.1.3 树的术语

• 父亲（parent）、儿子（child）、兄弟（sibling）、后裔（descendant）、祖先（ancestor）
• 度（degree）、叶子节点（leaf node）、分支节点（internal node）
• 结点的层数
• 路径、路径长度、结点的深度、树的深度

参照前文：【数据结构】树与二叉树（一）：树（森林）的基本概念：父亲、儿子、兄弟、后裔、祖先、度、叶子结点、分支结点、结点的层数、路径、路径长度、结点的深度、树的深度

5.2 二叉树

5.3 树

5.3.1 树的存储结构

1. 理论基础

1. Father链接结构:

   • 在这种结构中，每个节点除了存储数据外，还包含一个指向其父节点的指针。
   • 这种结构使得查找父节点很容易，但对于查找子节点则较为困难，因为需要遍历整个树。
   • 在二叉树中，每个节点最多有一个父节点，但在一般的树中，节点可以有多个父节点。

2. 儿子链表链接结构:

   • 在这种结构中，每个节点包含一个指向其第一个子节点的指针，以及一个指向其下一个兄弟节点的指针。
   • 这种结构使得查找子节点很容易，但查找父节点较为困难，可能需要遍历兄弟节点链表直到找到相应的父节点。

3. 左儿子右兄弟链接结构:

   • 也称为孩子兄弟表示法，每个节点包含一个指向其第一个子节点的指针，以及一个指向其下一个兄弟节点的指针。
   • 在这种结构中，树的每一层被表示为一个单链表，子节点通过左链连接，兄弟节点通过右链连接。
   • 这种结构既方便查找父节点，又方便查找子节点和兄弟节点，被广泛用于一般的树的表示。

  选择合适的树的存储结构通常取决于具体应用的需求。 Father链接结构适合于查找父节点的操作频繁，而儿子链表链接结构和左儿子右兄弟链接结构适用于频繁查找子节点的情况。

2. 典型实例

1. Father链接结构:
   • A节点：父指针为null（A为根节点）
   • B节点：父指针指向A
   • C节点：父指针指向A
   • D节点：父指针指向A
   • E节点：父指针指向C
   • F节点：父指针指向C
2. 儿子链表链接结构:
   • A节点：子节点链表为B、C、D
   • B节点：子节点链表为null
   • C节点：子节点链表为E、F
   • D节点：子节点链表为null
   • E节点：子节点链表为null
   • F节点：子节点链表为null
3. 左儿子右兄弟链接结构:
   • A节点：左儿子为B，右兄弟为null
   • B节点：左儿子为null，右兄弟为C
   • C节点：左儿子为E，右兄弟为D
   • D节点：左儿子为null，右兄弟为null
   • E节点：左儿子为null，右兄弟为F
   • F节点：左儿子为null，右兄弟为null

5.3.2 Father链接结构

a. 定义树节点结构

typedef struct TreeNode {char data;              // 节点数据struct TreeNode* parent; // 指向父节点的指针
} TreeNode;

b. 创建新节点

TreeNode* createNode(char data) {TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));if (newNode == NULL) {fprintf(stderr, "Memory allocation failed\n");exit(EXIT_FAILURE);}newNode->data = data;newNode->parent = NULL;return newNode;
}

c. 主函数

int main() {// 创建节点TreeNode* nodeA = createNode('A');TreeNode* nodeB = createNode('B');TreeNode* nodeC = createNode('C');TreeNode* nodeD = createNode('D');TreeNode* nodeE = createNode('E');TreeNode* nodeF = createNode('F');// 构建树结构，设置父指针nodeB->parent = nodeA;nodeC->parent = nodeA;nodeD->parent = nodeA;nodeE->parent = nodeC;nodeF->parent = nodeC;// 打印每个节点及其父节点printf("Node %c, Parent: %c\n", nodeA->data, (nodeA->parent ? nodeA->parent->data : 'N'));printf("Node %c, Parent: %c\n", nodeB->data, (nodeB->parent ? nodeB->parent->data : 'N'));printf("Node %c, Parent: %c\n", nodeC->data, (nodeC->parent ? nodeC->parent->data : 'N'));printf("Node %c, Parent: %c\n", nodeD->data, (nodeD->parent ? nodeD->parent->data : 'N'));printf("Node %c, Parent: %c\n", nodeE->data, (nodeE->parent ? nodeE->parent->data : 'N'));printf("Node %c, Parent: %c\n", nodeF->data, (nodeF->parent ? nodeF->parent->data : 'N'));// 释放内存free(nodeA);free(nodeB);free(nodeC);free(nodeD);free(nodeE);free(nodeF);return 0;
}

d. 代码整合

#include <stdio.h>
#include <stdlib.h>// 定义树节点结构
typedef struct TreeNode {char data;              // 节点数据struct TreeNode* parent; // 指向父节点的指针
} TreeNode;// 创建新节点的函数
TreeNode* createNode(char data) {TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));if (newNode == NULL) {fprintf(stderr, "Memory allocation failed\n");exit(EXIT_FAILURE);}newNode->data = data;newNode->parent = NULL;return newNode;
}int main() {// 创建节点TreeNode* nodeA = createNode('A');TreeNode* nodeB = createNode('B');TreeNode* nodeC = createNode('C');TreeNode* nodeD = createNode('D');TreeNode* nodeE = createNode('E');TreeNode* nodeF = createNode('F');// 构建树结构，设置父指针nodeB->parent = nodeA;nodeC->parent = nodeA;nodeD->parent = nodeA;nodeE->parent = nodeC;nodeF->parent = nodeC;// 打印每个节点及其父节点printf("Node %c, Parent: %c\n", nodeA->data, (nodeA->parent ? nodeA->parent->data : 'N'));printf("Node %c, Parent: %c\n", nodeB->data, (nodeB->parent ? nodeB->parent->data : 'N'));printf("Node %c, Parent: %c\n", nodeC->data, (nodeC->parent ? nodeC->parent->data : 'N'));printf("Node %c, Parent: %c\n", nodeD->data, (nodeD->parent ? nodeD->parent->data : 'N'));printf("Node %c, Parent: %c\n", nodeE->data, (nodeE->parent ? nodeE->parent->data : 'N'));printf("Node %c, Parent: %c\n", nodeF->data, (nodeF->parent ? nodeF->parent->data : 'N'));// 释放内存free(nodeA);free(nodeB);free(nodeC);free(nodeD);free(nodeE);free(nodeF);return 0;
}

注：其他操作……有缘再见

5.3.3 儿子链表链接结构

a. 定义树节点结构

struct TreeNode {char data;struct TreeNode* child;struct TreeNode* sibling;
};

b. 创建新节点

struct TreeNode* createNode(char data) {struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));newNode->data = data;newNode->child = NULL;newNode->sibling = NULL;return newNode;
}

c. 添加子节点作为第一个子节点

void addChild(struct TreeNode* parent, struct TreeNode* child) {child->sibling = parent->child;parent->child = child;
}

d. 遍历树打印节点数据

void traverseTree(struct TreeNode* root) {if (root != NULL) {printf("%c\n", root->data);struct TreeNode* child = root->child;while (child != NULL) {printf("  %c (Child)\n", child->data);child = child->sibling;}// 递归遍历每个子节点child = root->child;while (child != NULL) {traverseTree(child);child = child->sibling;}}
}

e. 主函数

int main() {// 创建树节点struct TreeNode* A = createNode('A');struct TreeNode* B = createNode('B');struct TreeNode* C = createNode('C');struct TreeNode* D = createNode('D');struct TreeNode* E = createNode('E');struct TreeNode* F = createNode('F');// 构建树结构addChild(A, B);addChild(A, C);addChild(A, D);addChild(C, E);addChild(C, F);// 遍历并打印树节点traverseTree(A);// 释放内存free(A);free(B);free(C);free(D);free(E);free(F);return 0;
}

f. 代码整合

#include <stdio.h>
#include <stdlib.h>// 定义树节点结构
struct TreeNode {char data;struct TreeNode* child;struct TreeNode* sibling;
};// 创建新节点
struct TreeNode* createNode(char data) {struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));newNode->data = data;newNode->child = NULL;newNode->sibling = NULL;return newNode;
}// 添加子节点作为第一个子节点
void addChild(struct TreeNode* parent, struct TreeNode* child) {child->sibling = parent->child;parent->child = child;
}// 遍历树并打印节点
void traverseTree(struct TreeNode* root) {if (root != NULL) {printf("%c\n", root->data);struct TreeNode* child = root->child;while (child != NULL) {printf("  %c (Child)\n", child->data);child = child->sibling;}// 递归遍历每个子节点child = root->child;while (child != NULL) {traverseTree(child);child = child->sibling;}}
}int main() {// 创建树节点struct TreeNode* A = createNode('A');struct TreeNode* B = createNode('B');struct TreeNode* C = createNode('C');struct TreeNode* D = createNode('D');struct TreeNode* E = createNode('E');struct TreeNode* F = createNode('F');// 构建树结构addChild(A, B);addChild(A, C);addChild(A, D);addChild(C, E);addChild(C, F);// 遍历并打印树节点traverseTree(A);// 释放内存free(A);free(B);free(C);free(D);free(E);free(F);return 0;
}