文章目錄
- 樹的雙親表示法
- 樹的孩子表示法
- 樹的孩子兄弟表示法
如下圖所示，這是一棵普通的樹，該如何存儲呢？通常，存儲具有普通樹結構資料的方法有 3 種：
雙親表示法；
孩子表示法；
孩子兄弟表示法；
圖1
雙親表示法采用順序表（也就是數組）存儲普通樹，其實作的核心思想是：順序存儲各個節點的同時，給各節點附加一個記錄其父節點位置的變量。
注意，根節點沒有父節點（父節點又稱為雙親節點），是以根節點記錄父節點位置的變量通常置為 -1。
圖2
雙親表示法存儲普通樹代碼
/*
* @Description: 樹的雙親表示法
* @Version: V1.0
* @Autor: Carlos
* @Date: 2020-05-21 14:41:32
* @LastEditors: Carlos
* @LastEditTime: 2020-06-01 22:12:34
*/ #include<stdio.h>#include<stdlib.h>//宏定義樹中結點的最大數量#define MAX_SIZE 20//宏定義樹結構中資料類型typedef char ElemType;//結點結構typedef struct Snode
{//樹中結點的資料類型ElemType data;//結點的父結點在數組中的位置下标int parent;}PNode;//樹結構typedef struct {//存放樹中所有結點PNode tnode[MAX_SIZE];//結點個數int n; }PTree;/**
* @Description: 節點初始化
* @Param: PTree tree 結構體變量
* @Return: PTree 結構體位址
* @Author: Carlos
*/PTree InitPNode(PTree tree){int i,j;char ch;printf("請輸入節點個數:\n");scanf("%d",&(tree.n));printf("請輸入結點的值其雙親位于數組中的位置下标:\n");for(i=0; i<tree.n; i++){fflush(stdin);scanf("%c %d",&ch,&j);tree.tnode[i].data = ch;tree.tnode[i].parent = j;}return tree;}/**
* @Description: 查找樹中指定節點
* @Param: PTree tree 結構體變量
* @Return: 無
* @Author: Carlos
*/void FindParent(PTree tree){char a;int isfind = 0;printf("請輸入要查詢的結點值:\n");fflush(stdin);scanf("%c",&a);for(int i =0;i<tree.n;i++){if(tree.tnode[i].data == a){isfind=1;//找到父節點的下标數值int ad=tree.tnode[i].parent;printf("%c的父節點為 %c,存儲位置下标為 %d",a,tree.tnode[ad].data,ad);break;}}if(isfind == 0){printf("樹中無此節點");}}int main(){PTree tree;tree = InitPNode(tree);FindParent(tree);return 0;} 孩子表示法存儲普通樹采用的是 “順序表+連結清單” 的組合結構，其存儲過程是：從樹的根節點開始，使用順序表依次存儲樹中各個節點，需要注意的是，與雙親表示法不同，孩子表示法會給各個節點配備一個連結清單，用于存儲各節點的孩子節點位于順序表中的位置。
如果節點沒有孩子節點（葉子節點），則該節點的連結清單為空連結清單。
例如，使用孩子表示法存儲左圖中的普通樹，則最終存儲狀态如右圖所示：
圖3
/*
* @Description: 樹的孩子表示法。三部分構成，連結清單，節點，樹
* @Version:
* @Autor: Carlos
* @Date: 2020-05-21 14:59:47
* @LastEditors: Carlos
* @LastEditTime: 2020-06-01 22:47:38
*/ #include<stdio.h>#include<stdlib.h>#define MAX_SIZE 20#define TElemType chartypedef struct CTNode{//連結清單中每個結點存儲的不是資料本身，而是資料在數組中存儲的位置下标！！int child;struct CTNode * next;}ChildPtr;typedef struct {//結點的資料類型TElemType data;//孩子連結清單的頭指針ChildPtr* firstchild;}CTBox;typedef struct{//存儲結點的數組CTBox nodes[MAX_SIZE];//結點數量和樹根的位置int n,r;}CTree;/**
* @Description: 孩子表示法存儲普通樹
* @Param: CTree tree 樹的結構體變量
* @Return: CTree tree 結構體變量
* @Author: Carlos
*/CTree InitTree(CTree tree){printf("輸入節點數量：\n");scanf("%d",&(tree.n));for(int i=0;i<tree.n;i++){printf("輸入第 %d 個節點的值：\n",i+1);fflush(stdin);scanf("%c",&(tree.nodes[i].data));tree.nodes[i].firstchild=(ChildPtr*)malloc(sizeof(ChildPtr));tree.nodes[i].firstchild->next=NULL;printf("輸入節點 %c 的孩子節點數量：\n",tree.nodes[i].data);int Num;scanf("%d",&Num);if(Num!=0){//帶頭結點的連結清單ChildPtr * p = tree.nodes[i].firstchild;for(int j = 0 ;j<Num;j++){ChildPtr * newEle=(ChildPtr*)malloc(sizeof(ChildPtr));newEle->next=NULL;printf("輸入第 %d 個孩子節點在順序表中的位置",j+1);scanf("%d",&(newEle->child));p->next= newEle;p=p->next;}}}return tree;}/**
* @Description:查找節點
* @Param: CTree tree 樹的結構體，char a 要查找的節點
* @Return: 無
* @Author: Carlos
*/void FindKids(CTree tree,char a){int hasKids=0;for(int i=0;i<tree.n;i++){if(tree.nodes[i].data==a){ChildPtr * p=tree.nodes[i].firstchild->next;while(p){hasKids = 1;//列印所有孩子節點 p->child 孩子節點在數組中的位置printf("%c ",tree.nodes[p->child].data);p=p->next;}break;}}if(hasKids==0){printf("此節點為葉子節點");}}int main(){CTree tree;tree = InitTree(tree);//預設數根節點位于數組notes[0]處tree.r=0;printf("找出節點 F 的所有孩子節點：");FindKids(tree,'F');return 0;} 樹結構中，位于同一層的節點之間互為兄弟節點。例如，圖1中的普通樹中，節點 A、B 和 C 互為兄弟節點，而節點 D、E 和 F 也互為兄弟節點。
孩子兄弟表示法，采用的是鍊式存儲結構，其存儲樹的實作思想是：從樹的根節點開始，依次用連結清單存儲各個節點的孩子節點和兄弟節點。
是以，該連結清單中的節點應包含以下 3 部分内容：
節點的值；
指向孩子節點的指針；
指向兄弟節點的指針；
版權聲明：本文為部落客原創文章，遵循 CC 4.0 BY-SA 版權協定，轉載請附上原文出處連結和本聲明。
本文連結：https://blog.csdn.net/qq_16933601/article/details/106483088
#define ElemType chartypedef struct CSNode{ElemType data;struct CSNode * firstchild,*nextsibling;}CSNode,*CSTree;