双亲表示法详解

一、双亲表示法简介

双亲表示法，简称为“树”，是一种在计算机科学和数学中广泛使用的数据结构。它由节点和边组成，通常用于模拟具有层次结构的问题。与其他数据结构相比，树结构具有更高的搜索效率和更好的可读性，因此在数据库、图形建模、编译器等领域都得到了广泛的应用。

在双亲表示法中，每个节点都有一个指向其父节点的指针，并且每个节点最多只有一个父节点。根据节点之间的关系，树结构可以被分为有根树和无根树两种类型。在有根树中，一个节点只有一个入度，而在无根树中，节点没有入度限制。

二、双亲表示法的基本操作

1、创建树

//创建树的结构体
typedef struct{
    int data; //节点的数据
    int parent; //指向其父节点的指针
}TreeNode;
 
//创建树的函数
void createTree(TreeNode t[], int n){
    int i, j, k;
    for (i=0; i<n; i++){
        printf("请输入第%d个节点的数据和双亲编号：", i+1);
        scanf("%d%d", &t[i].data, &t[i].parent);
        for (j=0; j<i; j++){  //判断是否重复输入
            if(t[i].data==t[j].data){
                printf("输入的节点已存在，请重新输入！\n");
                i--;
                break;
            }
        }
        if(t[i].parent!=i-1){  //判断是否满足双亲表示法的条件
            printf("输入的双亲编号错误，请重新输入！\n");
            i--;
        }
    }
}

在创建树的过程中，我们利用结构体TreeNode来存储树节点的数据和它的双亲编号。对于每个节点，我们用scanf函数获取输入的数据和双亲编号，并与之前输入的节点进行比较，以确保输入的节点没有重复。在输入完成后，我们再次遍历所有节点，判断它们的双亲编号是否符合双亲表示法的条件，即是否等于它的编号减一。

2、遍历树

//先序遍历
void preOrder(TreeNode t[], int n, int root){
    int i;
    printf("%d ", t[root].data); //输出根节点
    for (i=0; i<n; i++){
        if(t[i].parent==root){ //遍历其子节点
            preOrder(t, n, i);
        }
    }
}
 
//后序遍历
void postOrder(TreeNode t[], int n, int root){
    int i;
    for (i=0; i<n; i++){
        if(t[i].parent==root){ //遍历其子节点
            postOrder(t, n, i);
        }
    }
    printf("%d ", t[root].data); //输出根节点
}

遍历树的过程就是按照一定的顺序遍历树的所有节点。在双亲表示法中，我们可以使用递归的方式遍历树结构。对于每个节点，我们判断它是否为根节点，然后遍历它的子节点，直到遍历到叶子节点为止。

3、判断是否为叶子节点

bool isLeaf(TreeNode t[], int n, int root){
    int i;
    for (i=0; i<n; i++){
        if(t[i].parent==root){ //如果有子节点，则不是叶子节点
            return false;
        }
    }
    return true; //没有子节点，则是叶子节点
}

叶子节点是指没有子节点的节点。在双亲表示法中，我们可以通过判断一个节点是否有子节点来判断它是否为叶子节点。

三、双亲表示法的应用场景

1、数据库中的树结构

数据库中的树结构是一种用于描述数据之间层次关系的常见数据结构，通常用于表示各种分类结构。例如，一本图书可以用树的形式表达为作者->出版社->书名，一个公司可以用树的形式表达为公司->部门->员工。使用双亲表示法存储树结构可以使得访问父节点更加容易。

2、语法分析器中的树结构

编译器中的语法分析器通常使用树结构来表示程序的语法结构。双亲表示法可以方便地表示每个语法构造所在的上下文，使得错误处理和代码生成更加容易。

3、图形建模中的树结构

在图形建模中，双亲表示法可以用于表示三维物体的层次结构，从而方便地实现平移、旋转和缩放等操作。

4、面向对象中的继承关系

在面向对象的编程语言中，继承关系可以用树结构来表示，子类可以看作是父类的子节点。使用双亲表示法可以很方便地查找和处理继承层次结构。