---

---

树

一、树的概念

树形结构是一种重要的非线性结构，讨论的是层次和分支关系。

树是n个节点的有限集合，在任一棵非空树中：

（1）有且仅有一个称为根的节点。

（2）其余节点可分为n-1个互不相交的集合，而且这些集合中的每一集合都本身又是一棵树，称为根的子树。

• 树是递归结构，在树的定义中又用到了树的概念

例：下面的图是一棵树

T = {A, B, C, D, E, F, G, H, I, J，K，L，M}

• A是根，其余节点可以划分为3个互不相交的集合：

• T1={B, E, F，K，L} 、 T2={C, G} 、T3={D, H, I, J，M}

这些集合中的每个集合都本身又是一棵树，它们是A的子树。例如对于 T1而言，B是根，其余节点可以划分为2个互不相交的集合：T11={E，K，L}，T12={F}，T11,T12又是B的子树。

从逻辑结构看：

1）树中只有根节点没有前趋节点；

2）除根节点外，其余节点都有且仅一个前趋；

3）树的节点，可以有零个或多个后继；

4）除根节点外的其他节点，都存在唯一条从根节点到该节点的路径；

5）树是一种分枝结构 （除了一个称为根的节点外）每个元素都有

且仅有一个直接前趋，有且仅有零个或多个直接后继。

---

二、树的应用

1）树可表示具有分枝结构关系的对象

例1．家族族谱

设某家庭有13个成员A、B、C、D、E、F、G、H、I、J，K，L，M。他们之间的关系可下图所示的树表示：

例2．单位行政机构的组织关系

2）树是常用的数据组织形式

有些应用中数据元素之间并不存在间分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。

例3 . 计算机的文件系统

不论是DOS文件系统还是window文件系统，所有的文件是用树的形式来组织的。

---

三、树的表示

1）图示表示

2）二元组表示

3）嵌套集合表示

4）凹入表示法（类似书的目录）

5）广义表表示

---

四、树的基本术语

树的节点：包含一个数据元素及若干指向子树的分支；

祖先节点：从根到该节点的所经分支上的所有节点，也就是当前节点的所有迭代父节点。

双亲节点：B 节点是A节点的孩子，则A节点是B节点的双亲（父节点）；

兄弟节点：同一双亲（父节点）的孩子节点；

堂兄节点：节点深度相同，但父节点不同，则它们是一对堂兄弟节点；

孩子节点：节点的子树的根称为该节点的孩子；

子孙节点：以某节点为根的子树中任一节点都称为该节点的子孙

节点层：根节点的层定义为1；根的孩子为第二层节点，依此类推；

树的深度：树中最大的节点层（层数）

节点的度：节点子树的个数

树的度： 树中最大的节点度

叶子节点：也叫终端节点，是度为 0 的节点；

分枝节点：度不为0的节点；

有序树：子树有序的树，如：家族树；

无序树：不考虑子树的顺序；

森林：互不相交的树集合；森林和树之间的联系是：一棵树去掉根，其子树构成一个森林；一个森林增加一个根节点成为树。

二叉树：每个节点最多含有两个子树的树称为二叉树；

满二叉树：叶节点除外的所有节点均含有两个子树的树被称为满二叉树

完全二叉树：有个节点的满二叉树称为完全二叉树

哈夫曼树（最优二叉树）：带权路径最短的二叉树称为哈夫曼树或最优二叉树

五、树的四种表示方法

先分别说下三种不同的表示法：双亲表示法、孩子表示法、双亲孩子表示法、孩子兄弟表示法

5.1 双亲表示法

• 双亲表示法：一般采用顺序存储方式；

  • 以一组连续的空间存储树的结点，同时在每一个结点中附设一个指示器指示其双亲结点在链表中的位置

  • #define MAX_TREE_SIZE 100
    
    typedef struct PTNode{   //结点结构
        TElemTye data;       //数据元素类型
        int parent;          //双亲结点域
    }PTNode;
    
    typedef struct {                //树结构
        PTNode nodes[MAX_TREE_SIZE];//存储的结点
        int r,n;                    //根的位置和节点数
    }PTNode;
    

示意图：

代码实现：

/**
 * File : Work2.c
 * Author: 骑着蜗牛ひ追导弹'
 * Date: 2022/12/13 
 */
#include<stdio.h>

#define MAX_TREE_SIZE 100 //树中最多结点数
#define NodeNum 11 //总的结点数
typedef char ElemType;
typedef struct { //树的结点定义
    ElemType data; //数据元素
    int parent; //双亲位置域
} PTNode;
typedef struct { //树的类型定义
    PTNode nodes[MAX_TREE_SIZE]; //双亲表示
    int n; //结点数
} PTree;

void CreateTree(PTree *t) {
    int i, loc,tmp;
    ElemType ch;
    for (i = 0; i < NodeNum; i++) {
        printf("输入结点信息：");
        scanf("%c", &ch);
        t->nodes[i].data = ch;
        tmp = getchar();
        printf("输入对应双亲的位置下标：");
        scanf("%d", &loc);
        t->nodes[i].parent = loc;
        tmp = getchar();
        printf("\n");
    }
}

int main() {
    PTree *t;
    int i, j;
    CreateTree(t);
    printf("输出各结点的连接情况：\n");
    for (i = 0; i < NodeNum; i++) {
        printf("%c", t->nodes[i].data);
        for (j = 0; j < NodeNum; j++) {
            if (t->nodes[j].parent == i) printf(" -%c", t->nodes[j].data);
        }
        printf("\n");
    }
    return 0;
}

返回顶部

---

5.2 孩子表示法

• 孩子表示法：采用顺序存储+链式存储；

  • 把每个结点的孩子结点排列起来，看成一个线性表，并且以单链表做存储结构，则n个结点有n个孩子链表（叶子节点的孩子链表为空表），而n个头结点又组成一个线性表。

  • #define MAX_TREE_SIZE 100
    
    typedef struct CTNode{  //孩子结点
        int child;          //孩子数
        struct CTNode* next;//下一个孩子结点指针
    }* ChildPtr;
    
    typedef struct{
        TElemType data;     //数据域
        ChildPtr firstChild;//孩子链表头指针
    }CTBox;
    
    typedef struct{
        CTBox nodes[MAX_TREE_SIZE];//存储的结点
        int n,r;                   //结点数和根的位置
    }
    

示意图：

代码实现：

/**
 * File : Work2_haizi.c
 * Author: 骑着蜗牛ひ追导弹'
 * Date: 2022/12/13 
 */

#include<stdio.h>
#include<malloc.h>

#define MAX_TREE_SIZE 100
#define NodeNum 11
typedef char ElemType;
typedef struct CTNode { //孩子结点
    int child; //孩子结点在数组中的位置
    struct CTNode *next; //下一个孩子
} CTNode;

typedef struct { //顺序存储表
    ElemType data;
    struct CTNode *firstChild; //第一个孩子
} CTBox;

typedef struct {
    CTBox nodes[MAX_TREE_SIZE];
    int n, r; //结点数和根的位置
} CTree;

void CreateBox(CTree *t) {
    int i;
    ElemType ch;
    printf("输入结点信息：");
    for (i = 0; i < NodeNum; i++) {
        scanf("%c", &ch);
        t->nodes[i].data = ch;
        t->nodes[i].firstChild = NULL;
    }

}

void CreateNodes(CTree *t, ElemType ch, int num) {
    CTNode *p, *r = t->nodes[0].firstChild;
    int i, j, k = 0;
    while (num--) {
        p = (CTNode *) malloc(sizeof(CTNode));
        p->next = NULL;
        printf("输入孩子结点的编号：");
        scanf("%d", &i);
        for (j = 0; j < NodeNum; j++)
            if (t->nodes[j].data == ch) k = j;
        if (i != k) {
            p->child = i;
            if (t->nodes[k].firstChild == NULL) {
                t->nodes[k].firstChild = p;
                r = p;
            } else {
                r->next = p;
                r = p;
            }
        }
    }
}


int main() {
    CTree t;
    CTNode *p;
    int i, num;
    CreateBox(&t);
    printf("\n");
    for (i = 0; i < NodeNum; i++) {
        printf("创建结点%c的孩子结点\n", t.nodes[i].data);
        printf("输入要创建的孩子结点个数：");
        scanf("%d", &num);
        CreateNodes(&t, t.nodes[i].data, num);
        printf("\n");
    }

    printf("输出各结点的连接情况：\n");
    for (i = 0; i < NodeNum; i++) {
        p = t.nodes[i].firstChild;
        printf("%d(%c)", i, t.nodes[i].data);
        while (p != NULL) {
            printf("-%d(%c) ", p->child, t.nodes[p->child].data);
            p = p->next;
        }
        printf("\n");
    }
    return 0;
}

返回顶部

---

5.3 双亲孩子表示法

• 孩子表示法：采用顺序存储+链式存储；

  • 表中第一列为结点编号，第二列为结点数据，第三列为该节点的双亲编号（根节点双亲为-1），后面的单链表表示了该节点所有的孩子，从左至右依次进行遍历。

  • #define MAX_TREE_SIZE 100
    
    typedef struct CTNode{  //孩子结点
        int child;          //孩子数
        struct CTNode* next;//下一个孩子结点指针
    }* ChildPtr;
    
    typedef struct{
        TElemType data;     //数据域
        int parent;         //双亲下标
        ChildPtr firstChild;//孩子链表头指针
    }CTBox;
    
    typedef struct{
        CTBox nodes[MAX_TREE_SIZE];//存储的结点
        int n,r;                   //结点数和根的位置
    }
    

示意图：

代码实现：

/**
 * File : Work2_shuangqinhaizi.c
 * Author: 骑着蜗牛ひ追导弹'
 * Date: 2022/12/15 
 */

#include<stdio.h>
#include<malloc.h>

#define MAX_TREE_SIZE 100
#define NodeNum 11
typedef char ElemType;
//孩子链表结点
typedef struct CTNode {
    int child;           //孩子结点在数组中的位置
    struct CTNode *next; //下一个孩子
} CTNode;

//顺序存储表
typedef struct {
    ElemType data;    // 数据域
    int parent;       // 双亲位置
    struct CTNode *firstChild; //第一个孩子
} CTBox;
typedef struct {
    CTBox nodes[MAX_TREE_SIZE];
    int n, r; //结点数和根的位置
} CTree;

// 创建顺序表
void CreateBox(CTree *t) {
    int i,p;
    ElemType ch;
    printf("输入结点信息：");
    for (i = 0; i < NodeNum; i++) {
        scanf("%c", &ch);
        t->nodes[i].data = ch;
        t->nodes[i].firstChild = NULL;
    }
    printf("输入双亲结点信息：\n");
    for (i = 0; i < NodeNum; i++) {
        scanf("%d", &p);
        t->nodes[i].parent = p;
    }
}

void CreateNodes(CTree *t, ElemType ch, int num) {
    CTNode *p, *r = t->nodes[0].firstChild;
    int i, j, k = 0;
    while (num--) {
        p = (CTNode *) malloc(sizeof(CTNode));
        p->next = NULL;
        printf("输入孩子结点的编号：");
        scanf("%d", &i);
        for (j = 0; j < NodeNum; j++)
            if (t->nodes[j].data == ch) k = j;
        if (i != k) {
            p->child = i;
            if (t->nodes[k].firstChild == NULL) {
                t->nodes[k].firstChild = p;
                r = p;
            } else {
                r->next = p;
                r = p;
            }
        }
    }
}


int main() {
    CTree t;
    CTNode *p;
    int i, num;
    CreateBox(&t);
    printf("\n");
    for (i = 0; i < NodeNum; i++) {
        printf("创建结点%c的孩子结点\n", t.nodes[i].data);
        printf("输入要创建的孩子结点个数：");
        scanf("%d", &num);
        CreateNodes(&t, t.nodes[i].data, num);
        printf("\n");
    }

    printf("输出各结点的连接情况：\n");
    for (i = 0; i < NodeNum; i++) {
        p = t.nodes[i].firstChild;
        printf("%d(%c)[%d]", i, t.nodes[i].data,t.nodes[i].parent);
        while (p != NULL) {
            printf("-%d(%c) ", p->child, t.nodes[p->child].data);
            p = p->next;
        }
        printf("\n");
    }
    return 0;
}

返回顶部

---

5.4 孩子兄弟表示法

• 孩子兄弟表示法：采用链式存储，（其实是一个二叉链表，相当于构建二叉树）

  • 又称二叉树表示法，或者二叉链表表示法。链表中结点的两个链域分别指向该节点的第一个孩子结点和下一个兄弟结点

  • typedef struct CSNode{
        TElemType data;
        struct CSNode *firstChild, *nextSibling;
    }CSNode , *CSTree;
    

示意图：

代码实现：

/**
 * File : Work1.c
 * Author: 骑着蜗牛ひ追导弹'
 * Date: 2022/12/13 
 */
# include <stdio.h>
# include <stdlib.h>

typedef char nodeType;
typedef struct Tree {
    nodeType data;  // 数据域
    struct Tree *left;
    struct Tree *right;
} Tree, *BitTree;

BitTree createLink() {
    BitTree tree; // 二叉树
    char data;  // 节点数据
    char tmp;

    scanf("%c", &data);
    // 前面的scanf()在读取输入时会在缓冲区中留下一个字符’\n’（输入完按回车键所致），
    // 所以如果不在此加一个getchar()把这个回车符取走的话，
    // 接下来的scanf()就不会等待从键盘键入字符，
    // 而是会直接取走这个“无用的”回车符，从而导致读取有误
    tmp = getchar(); // 吸收空格

    if (data == '#') {
        return NULL; // 当前节点不存在数据
    } else {
        tree = (BitTree) malloc(sizeof(Tree)); // 分配空间
        tree->data = data;                    // 存储节点数据
        printf("请输入%c的左子树：", data);
        tree->left = createLink();            // 开始递归创建左子树
        printf("请输入%c的右子树：", data);
        tree->right = createLink();           // 开始到上一级节点的右边递归创建左右子树
        return tree;  // 返回根节点
    }
}

// 先序遍历
void showXianXu(BitTree T) {
    if (T == NULL) return; // 遇到空返回上一层节点
    printf("%c ", T->data);
    showXianXu(T->left); // 递归遍历左子树
    showXianXu(T->right);// 递归遍历右子树
}

// 中序遍历
void showZhongXu(BitTree T) {
    if (T == NULL) return; // 遇到空返回上一层节点
    showZhongXu(T->left); // 递归遍历左子树
    printf("%c ", T->data);
    showZhongXu(T->right);// 递归遍历右子树
}


// 后序遍历
void showHouXu(BitTree T) {
    if (T == NULL) return; // 遇到空返回上一层节点
    showHouXu(T->left); // 递归遍历左子树
    showHouXu(T->right);// 递归遍历右子树
    printf("%c ", T->data);
}



int main() {

    BitTree S;
    printf("请输入第一个节点的数据：\n");
    S = createLink();

    printf("先序遍历结果:\n");
    showXianXu(S);
    printf("\n中序遍历结果:\n");
    showZhongXu(S);
    printf("\n后序遍历结果:\n");
    showHouXu(S);

    return 0;
}

返回顶部

---