树的双亲表示法

由于树中的每个结点都有唯一的一个双亲结点,所以可用一组连续的存储空间(一维数组)存储树中的各个结点,数组中的一个元素表示树中的一个结点,每个结点含两个域,数据域存放结点本身信息,双亲域指示本结点的双亲结点在数组中位置。

#include <iostream>
#include <cstdio>
using namespace std;

#define MAX_TREE_SIZE 100

typedef struct PTNode{
    char data;
    int parent;
}PTNode;

typedef struct{
    PTNode nodes[MAX_TREE_SIZE];
    int r, n;
}PTree;

int main(){
    PTree T;
    printf("请输入树根的位置\n");
    scanf("%d",&T.r);
    printf("请输入节点的个数\n");
    scanf("%d",&T.n);
    printf("请输入每个节点及其双亲的位置\n");
    for(int i = 0;i < T.n;i++){
        cin >> T.nodes[i].data >> T.nodes[i].parent;
    }
    printf("输入结束\n");
    for(int i = 0;i < T.n;i++){
        for(int j = 0;j < T.n;j++){
            if(T.nodes[j].parent == i)
                printf("%c是%c的孩子\n",T.nodes[j].data,T.nodes[i].data);
        }
    }
    return 0;
}

树的孩子表示法

孩子表示法存储普通树采用的是 "顺序表+链表" 的组合结构,其存储过程是:从树的根节点开始,使用顺序表依次存储树中各个节点,需要注意的是,与双亲表示法不同,孩子表示法会给各个节点配备一个链表,用于存储各节点的孩子节点位于顺序表中的位置。

#include <bits/stdc++.h>

using namespace std;

#define MAX_TREE_SIZE 100

typedef struct CTNode{
    int child;
    struct CTNode *next;
}*Childptr;
typedef struct{
    char data;
    Childptr firstchild;
}CTBox;
typedef struct{
    CTBox nodes[MAX_TREE_SIZE];
    int n, r;
}CTree;

void initTree(CTree &T){
    printf("请输入树根的位置\n");
    scanf("%d",&T.r);
    printf("请输入节点的个数\n");
    scanf("%d",&T.n);
    for(int i = 0;i < T.n;i++){
        printf("请输入节点的元素\n");
        cin >> T.nodes[i].data;
        T.nodes[i].firstchild = (Childptr)malloc(sizeof(struct CTNode));
        T.nodes[i].firstchild ->next = NULL;
        printf("输入%c节点的孩子数量\n",T.nodes[i].data);
        int num;
        scanf("%d",&num);
        if(num != 0){
            Childptr p = T.nodes[i].firstchild;
            for(int j = 0;j < num;j++){
                Childptr q = (Childptr)malloc(sizeof(struct CTNode));
                q ->next = NULL;
                printf("请输入第%d个节点的位置\n",j + 1);
                scanf("%d",&q ->child);
                p ->next = q;
                p = p ->next;
            }
        }
    }
}

int main(){
    CTree T;
    initTree(T);
    for(int i = 0;i < T.n;i++){
        if(T.nodes[i].firstchild ->next != NULL){
            Childptr p = T.nodes[i].firstchild;
            while(p ->next != NULL){
                printf("%c是%c的双亲\n",T.nodes[i].data,T.nodes[p ->next ->child].data);
                p = p ->next;
            }
        }
    }
    return 0;
}