树的存储结构

• 如果将一棵树去掉根节点，那么这棵树就变成一片森林。
• 反之，将森林中的所有的树加上一个统一的根结点，就变成了树。

双亲表示法

• 以一组连续的存储单元存储树的结点，每个结点除了数据域 data 之外，还附加一个 parent 域用来指向其双亲结点的位置。
• 特点：找双亲容易，找孩子难。

实现

• 定义

  结构数组

  存放树的结点，每个结点包含两个域：

  • 数据域：存放结点本身的信息。
  • 双亲域：指示本结点的双亲结点在数组中的位置。

举个例子

• 根节点 R 没有双亲，所以双亲域存放-1。
• ABC 的双亲域里存着的都是0，表示他们共同的双亲都是在数组下标 0 处的结点 R，以此类推。

结点类型定义

typedef struct PTNode
{
		TElemType data;
		//存放的结点当中的数据，
		//元素类型取决于要存储的结点的元素类型。
		int parent;
		//存放结点双亲的所在位置的下标
}PTNode;

定义树结构数组

#define MAX_TREE_SIZE 100
typedef struct
{
		PTNode nodes[MAX_TREE_SIZE];
		//有100个PTNode类型的数组
		int r;//表示根结点的下标的位置
		int n;//记录总共存储了多少结点
}PTree;

代码实现

#include "stdlib.h"
#include "stdio.h"
#define MaxSize 100          //定义树的最大节点数
typedef int ElemType;     //树结点元素类型
//树的结点结构体
typedef struct PTNode{
    ElemType data;    //结点元素值
    int parent ;      //双亲结点的下标
}PTNode;
//树的结构体
typedef struct {
    PTNode nodes[MaxSize];   //结点数组
    int root ;               //根节点下标
    int num_node;           //树中结点数
}PTree;
//初始化树
void initTree(PTree* tree)
{
    tree->root = -1;        //根节点下标初始化为-1
    tree->num_node = 0;      //结点数初始化为0
}
//创建结点
PTNode createTree(ElemType data, int parent )
{
    PTNode node;
    node.data = data;
    node.parent = parent;
    return node;
}
//向树添加结点
void addNode(PTree* tree , ElemType data, int parent )
{
    //创建新结点
    PTNode node = createTree(data,parent);
    //将新结点加入结点数组
    tree->nodes[tree->num_node] = node;
    //更新父节点的子节点指针
    if(parent != -1 )
    {
        PTNode *parentNode = &(tree->nodes[parent]);
        parentNode->children[parentNode->num_children++] = tree->num_nodes;
    }
    //更新根节点下标和节点数
    if(tree->num_node == 0)
    {
        tree->root = 0;
    }
    tree->num_node++;
}
//打印树
void printTree(PTree tree) {
    for (int i = 0; i < tree.num_nodes; i++) {
        printf("Node %d: data=%d, parent=%d\n", i, tree.nodes[i].data, tree.nodes[i].parent);
    }
}
int main() {
    PTree tree;
    initTree(&tree);
    addNode(&tree, 1, -1);   // 添加根节点
    addNode(&tree, 2, 0);    // 添加第一个子节点
    addNode(&tree, 3, 0);    // 添加第二个子节点
    addNode(&tree, 4, 1);    // 添加第三个子节点
    addNode(&tree, 5, 1);    // 添加第四个子节点
    printTree(tree);         // 打印树
    return 0;
}

孩子表示法

• 由于树的每一个结点都可能有多棵子树，则可以使用多重链表，即每个结点由多个指针域，其中每个指针域指向一个子树的根节点。
• 把每个结点的孩子结点排列起来，看成一个线性表，用单链表存储，则n个结点由n个孩子链表（叶子的孩子链表为空表）。而n个头指针有组成一个线性表，用顺序表（含n个元素的结构数组）存储。
• 特点：找孩子容易，找双亲难

如上图所示

• 根节点R的孩子是ABC，那么就把他的孩子看成一个线性表。
• 将ABC用一个单链表穿起来，数据域用来存储数据元素，指针域则存放后继节点的地址

• 其他结点的孩子则以此类推依次用单链表串起来
• 用数组来存储每个单链表的头指针
• 

根节点 R 在下标为 r = 4 的位置，总共有 n = 10 个结点

孩子结点结构

typedef struct CTNode
{
		int child;
		struct CTNode *next;
}*ChildPtr;

双亲结点结构

typedef struct
{
		TElemType data;
		ChildPtr firstchild;
		//孩子链表的头指针，
		//这个指针指向的类型是有两个成员所构成的孩子结点结构。
}CTBox;

树结构

typedef struct
{
		CTBox nodes[MAX_TREE_SIZE];
		//用来存放所有指向孩子链表的头指针
		int r;//表示根节点所在数组位置的下标
		int n;//表示该树有多少个结点
}CTree;

代码实现、

#include <stdio.h>
#include <stdlib.h>
#define MAX_CHILDREN 10 // 子节点个数的最大值
// 树节点结构体
typedef struct TreeNode {
    int data; // 节点数据
    struct TreeNode *first_child; // 指向第一个子节点的指针
    struct TreeNode *next_sibling; // 指向下一个兄弟节点的指针
} TreeNode;
// 创建一个新的树节点
TreeNode *create_node(int data) {
    TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode)); // 为新节点分配内存空间
    node->data = data; // 设置节点的数据
    node->first_child = NULL; // 初始化节点的第一个子节点为空
    node->next_sibling = NULL; // 初始化节点的下一个兄弟节点为空
    return node; // 返回新节点的指针
}
// 添加一个子节点
void add_child(TreeNode *parent, TreeNode *child) {
    if (parent->first_child == NULL) { // 如果父节点没有子节点
        parent->first_child = child; // 将新节点设置为父节点的第一个子节点
    } else { // 如果父节点已经有子节点了
        TreeNode *p = parent->first_child;
        while (p->next_sibling != NULL) { // 找到父节点的最后一个子节点
            p = p->next_sibling;
        }
        p->next_sibling = child; // 将新节点设置为最后一个子节点的下一个兄弟节点
    }
}
// 打印树的孩子表示法
void print_tree(TreeNode *node) {
    if (node != NULL) { // 如果节点不为空
        printf("%d ", node->data); // 输出节点的数据
        if (node->first_child != NULL) { // 如果节点有子节点
            printf("("); // 输出左括号
            print_tree(node->first_child); // 递归打印子节点
            printf(")"); // 输出右括号
        }
        if (node->next_sibling != NULL) { // 如果节点有下一个兄弟节点
            printf(","); // 输出逗号
            print_tree(node->next_sibling); // 递归打印下一个兄弟节点
        }
    }
}
int main() {
    // 创建一棵树
    TreeNode *root = create_node(1); // 创建根节点
    TreeNode *node2 = create_node(2);
    TreeNode *node3 = create_node(3);
    TreeNode *node4 = create_node(4);
    TreeNode *node5 = create_node(5);
    TreeNode *node6 = create_node(6);
    add_child(root, node2); // 添加2为根节点的子节点
    add_child(root, node3); // 添加3为根节点的子节点
    add_child(node2, node4); // 添加4为2的子节点
    add_child(node2, node5); // 添加5为2的子节点
    add_child(node3, node6); // 添加6为3的子节点
    // 打印树的孩子表示法
    print_tree(root);
    printf("\n");
    return 0;
}

双亲孩子法

• 由前面两种表示法知道，要么不好找孩子，要么不好找双亲，这个时候就需要一种既能找爸爸又能找孩子的表示法。
• 可以将双亲法与孩子表结合起来，变成孩子双亲法，在结构数组中再增加一个成员用来存储每个结点的双亲结点的下标。
• 这种结构就称为带双亲的孩子链表。

#include <stdio.h>
#include <stdlib.h>
#define MAX_CHILDREN 10         // 每个节点最多包括10个子节点
// 树的节点结构体
typedef struct TreeNode {
    int value;                      // 节点的值
    struct TreeNode *parent;        // 父节点指针
    struct TreeNode *firstChild;    // 第一个子节点指针
    struct TreeNode *children[MAX_CHILDREN];  // 子节点数组，最多包括MAX_CHILDREN个子节点
} TreeNode;
// 创建一个新节点
TreeNode* createNode(int value, TreeNode *parent) {
    TreeNode *newNode = (TreeNode*) malloc(sizeof(TreeNode)); // 动态分配节点空间
    newNode->value = value;         // 设置节点值
    newNode->parent = parent;       // 设置父节点指针
    newNode->firstChild = NULL;     // 初始化第一个子节点指针为空
    for (int i = 0; i < MAX_CHILDREN; i++) {  // 初始化子节点数组为空
        newNode->children[i] = NULL;
    }
    return newNode;
}
// 在树中添加一个节点
void addChild(TreeNode *parent, int value) {
    TreeNode *newNode = createNode(value, parent);  // 创建新节点
    if (parent->firstChild == NULL) {   // 如果父节点没有子节点
        parent->firstChild = newNode;   // 将新节点作为父节点的第一个子节点
    } else {                            // 否则
        TreeNode *child = parent->firstChild;
        while (child->children[MAX_CHILDREN-1] != NULL) {  // 找到父节点的最后一个子节点
            child = child->children[MAX_CHILDREN-1];
        }
        int i = 0;
        while (child->children[i] != NULL) {  // 找到第一个空的子节点位置
            i++;
        }
        child->children[i] = newNode;   // 将新节点添加到最后一个子节点的后面
    }
    newNode->parent = parent;   // 设置新节点的父节点指针
}
// 遍历整棵树
void traverseTree(TreeNode *root) {
    printf("%d ", root->value);     // 先输出当前节点的值
    if (root->firstChild == NULL) { // 如果当前节点没有子节点，返回
        return;
    }
    TreeNode *child = root->firstChild;
    while (child != NULL) {         // 遍历所有子节点
        traverseTree(child);        // 递归遍历子节点的子树
        child = child->children[0]; // 遍历下一个子节点
    }
}

孩子兄弟表示法

（二叉树表示法，二叉链表表示法）即以二叉链表做树的存储结构

实现方法

• 用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向第一个孩子结点和下一个兄弟结点（左孩右兄）
• 特点：找到孩子容易，找双亲难

1. 根节点 R 的左指针域存储它的第一个孩子 A 的地址，因为 R 没有兄弟，所以右指针域为NULL。
2. A 左指针指向它的第一个孩子 D，右指针指向它从左往右数的下一个兄弟 B。
3. 其余结点以此类推。
4. 从左往右斜着看在一条线上的都是兄弟，反之从右往左斜着看在一条线上的则是孩子。

#include <stdio.h>
#include <stdlib.h>
// 树的节点结构体
typedef struct TreeNode {
    int value;                  // 节点的值
    struct TreeNode *firstChild;    // 第一个子节点指针
    struct TreeNode *nextSibling;   // 下一个兄弟节点指针
} TreeNode;
// 创建一个新节点
TreeNode* createNode(int value) {
    TreeNode *newNode = (TreeNode*) malloc(sizeof(TreeNode)); // 动态分配节点空间
    newNode->value = value;             // 设置节点值
    newNode->firstChild = NULL;         // 初始化第一个子节点指针为空
    newNode->nextSibling = NULL;        // 初始化下一个兄弟节点指针为空
    return newNode;
}
// 在树中添加一个子节点
void addChild(TreeNode *parent, int value) {
    TreeNode *newNode = createNode(value);  // 创建新节点
    if (parent->firstChild == NULL) {       // 如果父节点没有子节点
        parent->firstChild = newNode;       // 将新节点作为父节点的第一个子节点
    } else {                                // 否则
        TreeNode *child = parent->firstChild;
        while (child->nextSibling != NULL) {    // 找到父节点的最后一个子节点
            child = child->nextSibling;
        }
        child->nextSibling = newNode;           // 将新节点添加到最后一个子节点的后面
    }
}
// 遍历整棵树
void traverseTree(TreeNode *root) {
    if (root == NULL) {             // 如果当前节点为空，返回
        return;
    }
    printf("%d ", root->value);     // 输出当前节点的值
    traverseTree(root->firstChild); // 遍历子节点的子树
    traverseTree(root->nextSibling);// 遍历兄弟节点的子树
}
int main() {
    // 创建根节点
    TreeNode *root = createNode(1);
    // 添加子节点
    addChild(root, 2);
    addChild(root, 3);
    addChild(root, 4);
    addChild(root->firstChild, 5);
    addChild(root->firstChild, 6);
    addChild(root->firstChild->nextSibling, 7);
    addChild(root->firstChild->nextSibling->nextSibling, 8);
    // 遍历树
    traverseTree(root);
    return 0;
}

二叉树的转换

树与二叉树的转换

• 将树转化为二叉树进行操作，利用二叉树的算法来实现对树的操作。
• 由于树和二叉树都可以用二叉链表作为存储结构，则以二叉链表作媒介可以导出树与二叉树之间的一个对应关系

将树以二叉链表的形式存储

• 解释成孩子兄弟链表。

• 左指针域指向结点的第一个孩子，右指针域则指向结点的下一个兄弟。

  • A 结点的第一个孩子是 B，A 是根节点没有兄弟。
  • B 没有孩子，它的下个兄弟是 C。
  • C 的第一个孩子是 D，下个兄弟是 E。
  • D 既没有孩子也没用兄弟。

• 让一棵二叉树存储成二叉链表是同样的结构

• 每个结点的左右指针域分别存储该结点的左右孩子。

总结

上图的 树与二叉树，具有相同的二叉链表存储结构，那么就可以：

• 把一棵 树 进行存储得到二叉链表，然后将二叉链表解释成二叉树对应的存储形式，就可以得到二叉树了。
• 同理，将这棵 二叉树 存储得到二叉链表，然后将二叉链表解释成树对应的存储形式，就可以得到树了。
• 以中间的这个存储结构作为媒介，就可以找到树与二叉树之间的对应关系。
• 给定一棵树，可以找到唯一的一棵二叉树与之对应。

规律：在树中的兄弟结点到了二叉树中变成了右孩子，左变右兄弟变儿子，右变左儿子变兄弟。

树转换成二叉树

1. 加线：在兄弟之间加一条线
2. 抹线：对每个结点，只保留双亲与第一个孩子之间的连线，其余连线全部消除。
3. 旋转：以树的根节点为轴心，将整棵树顺时针转 45°。

树变二叉树：兄弟相连留长子。

举个栗子

将这棵树转换成二叉树，兄弟相连留长子。

1. 连线：兄弟之间要连线。

2. 抹线：只保留双亲结点与其第一个孩子之间的连线。

3. 旋转：以树的根结点为轴，顺时针转 45°。

#include <stdio.h>
#include <stdlib.h>
// 定义树节点
typedef struct node {
    char data;  // 节点数据
    struct node *first_child;  // 第一个子节点
    struct node *next_sibling;  // 下一个兄弟节点
} Node;
// 定义二叉树节点
typedef struct binary_tree_node {
    char data;  // 节点数据
    struct binary_tree_node *left_child;  // 左子节点
    struct binary_tree_node *right_child;  // 右子节点
} BinaryTreeNode;
// 将树转换为二叉树
BinaryTreeNode *convert_tree_to_binary_tree(Node *root) {
    if (root == NULL) {  // 如果根节点为空，则返回空
        return NULL;
    }
    // 创建二叉树节点，节点数据为根节点数据
    BinaryTreeNode *binary_root = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
    binary_root->data = root->data;
    binary_root->left_child = NULL;
    binary_root->right_child = NULL;
    // 转换根节点的第一个子节点为左子树
    if (root->first_child != NULL) {
        binary_root->left_child = convert_tree_to_binary_tree(root->first_child);
    }
    // 转换根节点的兄弟节点为右子树
    if (root->next_sibling != NULL) {
        binary_root->right_child = convert_tree_to_binary_tree(root->next_sibling);
    }
    return binary_root;  // 返回二叉树根节点
}
int main() {
    // 创建树
    Node *root = (Node*)malloc(sizeof(Node));
    root->data = 'A';
    Node *b = (Node*)malloc(sizeof(Node));
    b->data = 'B';
    Node *c = (Node*)malloc(sizeof(Node));
    c->data = 'C';
    Node *d = (Node*)malloc(sizeof(Node));
    d->data = 'D';
    Node *e = (Node*)malloc(sizeof(Node));
    e->data = 'E';
    Node *f = (Node*)malloc(sizeof(Node));
    f->data = 'F';
    root->first_child = b;
    b->next_sibling = c;
    c->next_sibling = NULL;
    b->first_child = d;
    d->next_sibling = e;
    e->next_sibling = NULL;
    d->first_child = f;
    f->next_sibling = NULL;
    f->first_child = NULL;
    e->first_child = NULL;
    // 将树转换为二叉树
    BinaryTreeNode *binary_root = convert_tree_to_binary_tree(root);
    return 0;
}

二叉树转换成树

既然可以将树通过兄弟相连留长子这个方法转换成二叉树，那么同样可以将这个方法逆转得到二叉树。

1. 加线：若 p 结点是双亲结点的左孩子，则将 p 的右孩子，右孩子的右孩子…沿着分支找到所有的右孩子，都与 p 的双亲用线连接起来。
2. 抹线：抹掉原来二叉树中双亲结点与右孩子之间的连线
3. 调整：将结点按照层次排列，形成树结构。

二叉树变树：左孩右右连双亲，去掉原来右孩线。

举个例子

将这棵二叉树转换成树，左孩右右连双亲，去掉原来右孩线。

1. 加线：B 为 A 的左孩子，将 B 的右右右孩子每个都与 A 连起来，其余结点同理。

2. 抹线：去掉原来的二叉树中双亲结点与右孩子之间的连线，（加了几根线就去掉几根线）。
   • 如：去掉 B 与 C 之间的线、去掉 C 与 D 之间的线、H 与 I 之间的线…

3. 调整：同一层的结点的孩子为同一层。

   • BCD 为第一层的结点 A 的孩子，放在第二层。

   • EFGHI 为第二层的结点的孩子，放在第三层。

#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点
typedef struct binary_tree_node {
    char data;  // 节点数据
    struct binary_tree_node *left_child;  // 左子节点
    struct binary_tree_node *right_child;  // 右子节点
} BinaryTreeNode;
// 定义树节点
typedef struct node {
    char data;  // 节点数据
    struct node *first_child;  // 第一个子节点
    struct node *next_sibling;  // 下一个兄弟节点
} Node;
// 将二叉树转换为树
Node *convert_binary_tree_to_tree(BinaryTreeNode *root) {
    if (root == NULL) {  // 如果根节点为空，则返回空
        return NULL;
    }
    // 创建树节点，节点数据为根节点数据
    Node *tree_root = (Node*)malloc(sizeof(Node));
    tree_root->data = root->data;
    tree_root->first_child = NULL;
    tree_root->next_sibling = NULL;
    // 如果有左子节点，则将其转换为第一个子节点
    if (root->left_child != NULL) {
        tree_root->first_child = convert_binary_tree_to_tree(root->left_child);
    }
    // 如果有右子节点，则将其转换为兄弟节点
    if (root->right_child != NULL) {
        tree_root->next_sibling = convert_binary_tree_to_tree(root->right_child);
    }
    return tree_root;  // 返回树根节点
}
int main() {
    // 创建二叉树
    BinaryTreeNode *root = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
    root->data = 'A';
    BinaryTreeNode *b = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
    b->data = 'B';
    BinaryTreeNode *c = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
    c->data = 'C';
    BinaryTreeNode *d = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
    d->data = 'D';
    BinaryTreeNode *e = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
    e->data = 'E';
    BinaryTreeNode *f = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
    f->data = 'F';
    root->left_child = b;
    root->right_child = c;
    b->left_child = d;
    b->right_child = e;
    c->left_child = f;
    c->right_child = NULL;
    d->left_child = NULL;
    d->right_child = NULL;
    e->left_child = NULL;
    e->right_child = NULL;
    f->left_child = NULL;
    f->right_child = NULL;
    // 将二叉树转换为树
    Node *tree_root = convert_binary_tree_to_tree(root);
    return 0;
}

森林和二叉树的转换

森林转换成二叉树

二叉树与多棵树之间的关系

1. 将各棵树分别转换成二叉树（兄弟相连留长子）。
2. 将每棵树的根结点用线相连。
3. 以第一棵树的根结点为二叉树的根，再以根结点为轴心，顺时针旋转构成二叉树型结构。

森林变二叉树：树变二叉树根相连。

1. 通过兄弟相连留长子的方法将所有的树转换成二叉树。

2. 所有的树变二叉树之后，将所有的二叉树的根 AEG 连在一条线上。

3. 以第一棵树的根节点 A 作为整个二叉树的根，然后以这个根结点旋转，其余的根结点 EG 就变成了 A 的右孩子，以及右孩子的右孩子。

#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结点类型
struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};
// 定义森林结点类型
struct ForestNode {
    int val;
    struct ForestNode* firstChild;
    struct ForestNode* nextSibling;
};
// 辅助函数：将一个森林结点转换为一棵二叉树
struct TreeNode* forestToTree(struct ForestNode* node) {
    // 如果结点为空，返回 NULL
    if (node == NULL) {
        return NULL;
    }
    // 将当前结点的值存储到新建的二叉树结点中
    struct TreeNode* root = (struct TreeNode*) malloc(sizeof(struct TreeNode));
    root->val = node->val;
    root->left = NULL;
    root->right = NULL;
    // 如果当前结点有子结点，将其第一个子结点转换为左子树
    if (node->firstChild != NULL) {
        root->left = forestToTree(node->firstChild);
    }
    // 如果当前结点有兄弟结点，将其第一个兄弟结点转换为右子树
    if (node->nextSibling != NULL) {
        root->right = forestToTree(node->nextSibling);
    }
    return root;
}

二叉树转换成森林

1. 抹线： 将二叉树中根节点与其右孩子的连线，及沿右分支搜索到的所有右孩子间的连线全部抹掉（森林变二叉树时，根结点只留了个 A 剩下两个成了它的右孩子），使其变成独立的二叉树。
2. 还原：将独立的二叉树还原成树。

二叉树变森林：去掉全部右孩线，孤立二叉再还原。

去掉全部右孩线，孤立二叉再还原。

1. 抹线：
   • 将根结点 A 与它的右孩子 E，以及 E 的右孩子 G之间的线抹除。
   • 如果还有右右右孩子，则继续顺着右分支抹线。

2. 去掉所有的右孩子线之后整棵二叉树就变成了几棵独立的二叉树。

3. 将独立的二叉树通过左孩右右连双亲，去掉原来右孩线，变成树
   • 将同一个结点的孩子放在同一层。

树的遍历

• 由于树的每个结点可以有多个子树，所以将根放在哪个位置上就无法确定，导致树没有中序遍历。
• 只有先根遍历和后根遍历以及层次遍历这三种遍历方法。

树的三种遍历方式

• 先根遍历：若树不为空，则先访问根节点，然后依次先根遍历根的每棵子树。
• 后根遍历：若树不为空，则先依次后根遍历每棵子树，然后访问根结点。
• 层次遍历：若树不为空，则按照自上而下，自左而右的顺序访问树中每个节点。

森林的遍历

将森林看作由三部分构成，分别遍历这三个部分。

1. 森林中第一棵树的根结点。
2. 森林中第一棵树的子树森林。
3. 森林中其他树构成的森林。

• 先序遍历（123）：如果首先遍历森林的第一部分，则称这种遍历为先序遍历。
• 中序遍历（213）：如果首先遍历森林的第二部分，则称这种遍历为中序遍历。

先序遍历

若森林不为空，则：

1. 首先访问森林中第一棵树的根节点。
2. 先序遍历森林中第一棵树的子树森林。
3. 先序遍历森林中（除第一棵树之外）其余树所构成的森林。

森林的先序：依次从左至右对森林中的每一棵树进行先根遍历。

中序遍历

若森林不为空，则：

1. 中序遍历森林中第一棵树的子树森林。
2. 然后访问森林中第一棵树的根节点。
3. 中序遍历森林中（除第一棵树之外）其余树所构成的森林。

森林的中序：依次从左至右对森林中的每一棵树进行后根遍历（注意是后根遍历）。