数据结构

数据结构笔记——树与森林

基本概念

森林：是m棵互不相交的树的集合

存储结构

双亲表示法

定义一个数组，数组中存放输的节点，每个节点包含数据域与双亲域。

双亲域表示当前节点的双亲的在数组中的下标

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

typedef struct PTree
{
    PTNode nodes[MAXQSIZE];
    int r,n //根节点的位置和总元素个数
};

孩子链表表示法

把每个节点用线性表连接起来，把某个节点的所有孩子节点连接成为一个单链表，连接在其父节点的线性表中

typedef struct CTNode
{
    int child;
    struct CTNode *next;
}*ChildPtr; //孩子节点

typedef struct{
    ElemType data;
    ChildPtr firstchild;
}CTbox; //双亲节点

typedef struct{
    CTbox nodes[MAXQSIZE];
    int n,r;//根节点数与根节点的位置
}CTree;

孩子兄弟表示法（二叉树表示法、二叉链表表示法）

用二叉链表作为树的存储结构，链表中每个节点的两个指针域分别指向其第一个孩子节点和下一个兄弟节点

typedef struct CSNode{
    ElemType data;
    struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;

将树转化为二叉树

树转为二叉树转换步骤如下

  1. 加线：兄弟之间加一条线

  2. 抹线：对每个节点，除了其左孩子之外，去除与其他孩子之间的关系

  3. 旋转：以树的根节点为轴心，整棵树顺时针旋转40°

二叉树转为树的步骤如下

  1. 加线：若p节点是双亲节点的左孩子，则将p的右孩子、右孩子的右孩子.......沿着分支找到的所有右孩子，都与p的双亲用线连接起来

  2. 抹线：抹掉原来二叉树的双亲节点与右孩子之间的连线

  3. 调整：将节点按层次排列一下

Comment