数据结构(5.4_1)——树的存储结构

树的逻辑结构

双亲表示法(顺序存储)

每个结点中保存指向双亲的“指针”

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

增加结点操作 

新增数据元素无需按逻辑上的次序存储，之家在上一个结点后添加新结点，并记录双亲结点

 

删除叶结点操作 

1、删除结点数据域                           

2、将尾部数据移动至删除结点位置填充空缺

删除非叶结点操作  

寻找其双亲结点相同的结点

孩子表示法 (顺序+链式存储)

顺序存储各个节点，每个结点中保存孩子的链表头指针

#define MAX_TREE_SIZE 100//树中最多结点
 
struct CTNode {
    int child;//孩子在结点数组中的位置
    struct CTNode* next;//下一个孩子
};
typedef struct {
    int data;
    struct  CTNode* firstChild;//第一个孩子
}CTBox;
typedef struct {
    CTBox nodes[MAX_TREE_SIZE];
    int n, r;//结点数和根的位置
}CTree;

孩子兄弟表示法(链式存储) 

 

/树的存储——孩子兄弟表示法
typedef struct CSNode {
    int data;
    struct CSNode* firsitchild, * nextsilbling;//第一个孩子和右兄弟指针
}CSNode,*CSTree;
int main() {
 
    return 0;
}

树和二叉树的转化：

使用孩子兄弟表示法

 

森林和二叉树的转化 

森林—>二叉树

二叉树—>森林

 

总结：