目錄

一、樹的雙親表示

存儲結構?

?總代碼

二、樹的孩子表示

存儲結構

總代碼

三、樹的雙親孩子表示

存儲結構

---

一、樹的雙親表示

存儲結構?

?采用結構體數組的形式存儲數據。

（根結點parent=1：它沒有雙親結點了）

//樹的雙親表示
typedef struct
{char data;				//結點數據int parent;			//雙親在數組中的位置
}Tree;
Tree tree[MAXSIZE];

?總代碼

//樹的雙親表示法（雙親樹）
//getchar()：吸收換行符
#include<stdio.h>#define MAXSIZE 20
int count = 0;//樹的雙親表示
typedef struct
{char data;				//結點數據int parent;			//雙親在數組中的位置
}Tree;
Tree tree[MAXSIZE];//雙親樹的初始化
void Init_Tree()
{tree[0].parent = -1;
}//創建樹
void Create_Tree()
{int i, n = 0;printf("請輸入結點個數：\n");scanf_s("%d", &n);getchar();											//這里吸收換行符printf("請依次輸入結點數據和雙親結點序號：\n");for (i = 0; i < n; i++){scanf_s("%c", &(tree[i].data));		//輸入數據scanf_s("%d", &(tree[i].parent));	//輸入雙親結點getchar();										//這里吸收換行符count++;}
}//遍歷樹
void Traverse()
{int i = 0;for (i = 0; i < count; i++){printf("%c的雙親結點：%d\n", tree[i].data, tree[i].parent);}
}int main()
{Init_Tree();			//初始化Create_Tree();		//創建樹Traverse();			//遍歷樹return 0;
}

二、樹的孩子表示

存儲結構

先創建一個結構體數組，用*firstchild連接它們的第一個孩子結點，用*next連接后面的孩子結點。最后把地址賦空（注：這里把地址賦空用的是二級指針，能同步改變根結點的地址，但凡需要地址的改變都要二級指針，二級指針是個難點，單獨放在另一篇博客中）

//孩子結點
typedef struct Child
{int child;struct Child** next;
}Child, *pChild;

總代碼

//樹的孩子表示法
//兩個結構體：
//一個結構體數組存放整體數據元素，里面有*firstchild指針指向第一個孩子
//一個孩子鏈表存放孩子信息
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <malloc.h>#define MAXSIZE 20
int length = 0;					//數組長度//孩子結點
typedef struct Child
{int child;struct Child** next;
}Child, * pChild;				//*pChild：創建二級指針//樹
typedef struct
{char data;Child* firstchild;
}Tree;
Tree T[MAXSIZE];//輸入
void InputTree()
{int i;char ch;Child* child;printf("請輸入您需要創建的結點數據：\n");scanf("%c", &ch);for (i = 0; i < MAXSIZE && ch != '\n'; i++){T[i].data = ch;scanf("%c", &ch);}length = i;					//記錄數據長度（數組）
}//初始化
void InitTree()
{int i;for (i = 0; i < length; i++){T[i].firstchild = NULL;}
}//根據結點數據查找孩子下標
int FindIndex(char ch)
{int i = 0;for (i = 0; i < length; i++){if (T[i].data == ch)return i;}return -1;
}//創建樹
void CreateTree()
{int i = 0;char ch;pChild* p = NULL;					//二級指針for (i = 0; i < length; i++){printf("請輸入%c的孩子結點數據（沒有就直接回車）：  ", T[i].data);scanf("%c", &ch);//首孩子if (ch != '\n'){T[i].firstchild = (Child*)malloc(sizeof(Child));	//創建指向首孩子的指針p = (pChild*)malloc(sizeof(pChild));				//孩子指針p = &T[i].firstchild;											//孩子指針指向首孩子指針(*p)->child = FindIndex(ch);(*p)->next = (pChild*)malloc(sizeof(pChild));*((*p)->next) = NULL;										//一級指針賦NULLscanf("%c", &ch);}//后面的孩子while (ch != '\n'){//二級指針的操作（給*p地址）(*p)->next = (pChild*)malloc(sizeof(pChild));	//創建指向首孩子的指針	（p: 二級指針有地址）p = (*p)->next;												//后移								（next: 二級指針有地址）//一級指針的操作（給*p地址）(*p) = (Child*)malloc(sizeof(pChild));				//創建一級指針(*p)->child = FindIndex(ch);							//(*p)一級指針并沒有地址！！！//在二級指針的基礎上，要把一級指針浮NULL，必須得先給二級指針地址(*p)->next = (pChild*)malloc(sizeof(pChild));*((*p)->next) = NULL;										//一級指針賦NULLscanf("%c", &ch);}}
}//遍歷樹
void Traverse()
{int i;Child* p = NULL;for (i = 0; i < length; i++){p = T[i].firstchild;printf("\n%c的孩子結點(下標)：", T[i].data);while (p != NULL){printf("%d ", p->child);p = *(p->next);}}
}int main()
{InputTree();InitTree();CreateTree();				//創建樹Traverse();					//遍歷return 0;
}

三、樹的雙親孩子表示

存儲結構

總代碼

//樹的雙親孩子表示法
#include <stdio.h>
#include <malloc.h>#define MAXSIZE 20
int sum = 0;//孩子結點
typedef struct Child
{int index;struct Child* next;
}Child;
Child* now;//樹
typedef struct
{char data;int childNum;char parent;Child* firstchild;
}Tree;
Tree tree[MAXSIZE];//初始化
void Init_Tree()
{now = (Child*)malloc(sizeof(Child));tree[0].parent = NULL;
}//創建樹
void Create_Tree()
{int num, i, j;Child* child;printf("請輸入您需要創建的結點個數：\n");scanf_s("%d", &sum);													//結點總數getchar();//輸入數組列表for (i = 0; i < sum; i++){printf("\n請輸入第%d個結點數據：\n", i + 1);scanf_s("%c", &tree[i].data);									//輸入數據getchar();printf("請輸入%c結點的孩子結點個數：\n", tree[i].data);scanf_s("%d", &num);												//孩子節點總數getchar();//輸入孩子結點if (num)			//num!=0printf("請分別輸入%c結點的孩子結點在數組中的位置：\n", tree[i].data);for (j = 0; j < num; j++){child = (Child*)malloc(sizeof(Child));					//創建孩子結點child->next = NULL;scanf_s("%d", &child->index);								//孩子節點在數組中的下標getchar();tree[child->index].parent = tree[i].data;				//設置孩子結點的雙親結點//連接到上一個if (j == 0){tree[i].firstchild = child;child->next = NULL;}else{now->next = child;									//指向當前結點}now = child;tree[i].childNum++;}}
}//遍歷樹
void Traverse()
{int i, j;Child* now;for (i = 0; i < sum; i++){printf("\n第%d個結點：%c\n", i + 1, tree[i].data);now = tree[i].firstchild;									//指向第一個葉子結點printf("%c結點的雙親結點：%c\n", tree[i].data, tree[i].parent);for (j = 0; j < tree[i].childNum; j++){printf("%c結點的第%d個孩子結點：%c\n", tree[i].data, j + 1, tree[now->index].data);now = now->next;										//往后移}}
}int main()
{Init_Tree();Create_Tree();				//創建樹Traverse();					//遍歷return 0;
}

總結

以上是生活随笔為你收集整理的数据结构与算法（6-1）树的存储（树的双亲表示、树的孩子表示及树的双亲孩子表示）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。