008——树

树：

数据之间存在一对多的关系

树和子树之间的关系，可以类比于集合和子集，但是子树的根节点下的所有结点都包括的才叫做子树，下面图片圈出来的都是，若是ABCD组成的并不叫作子树。

树的定义是具有递归性的，即树中有树

树的存储结构/表示方法：

树中都需要存储什么？

树中的数据-->数组

数据之间的关系-->父亲(1.双亲表示法) 孩子(2.孩子表示法)孩子和兄弟(3.孩子兄弟表示法)

1.双亲表示法

指名某个结点的父亲

在存储数据的时候，我们可以采用结构体数组

struct node{char data;//数据int fi;//data父亲的下标 
}t[105];

#include<stdio.h>
#include<stdlib.h>
struct node{char data;//数据int fi;//data父亲的下标 
}t[105];
int size;//树中的节点个数 
void initTree(char x)
{t[0].data=x;t[0].fi=-1;size++;
}
int find(char fx)
{for(int i=0;i<size;i++){if(t[i].data==fx){return i;}}
}
void insert(char x,char fx)
{t[size].data=x;int fx_i=find(fx);t[size].fi=fx_i;size++;
}
int main()
{int n;//输入数据的个数char root; scanf("%d",&n);getchar(); scanf("%c",&root);initTree(root);char x,fx;//x的父亲是fx for(int i=1;i<=n-1;i++){getchar();scanf("%c %c",&x,&fx);insert(x,fx); 	}getchar();scanf("%c",&x);//找x的父亲和孩子//找父亲int x_i=find(x); int fx_i=t[x_i].fi;if(fx_i==-1){printf("根节点，没有父亲节点\n");} else{printf("父亲节点是%c\n",t[fx_i].data);} int sum=0;//孩子的个数 //找孩子：printf("孩子节点是：\n"); for(int i=0;i<size;i++){if(x_i==t[i].fi){sum++;printf("%c ",t[i].data);}}if(sum==0){printf("叶子节点，没有孩子节点\n");}return 0;}

2.孩子表示法

孩子表示法

根据上图，我们可以申请一个t数组，t数组中存放有数据和指向孩子的链表，在链表中存放孩子结点的下标，所以代码如下（这里需要注意，链表只是结构体数组的一个成员变量，t的本质仍是数组）

//存放孩子的单链表结点结构
typedef struct childNode {int chi;//存放孩子结点的下标struct childNode* next;//写一个孩子的结点
}chNode;struct node {char data;//存放数据chNode* first;//指向孩子链表
}t[105];

数据的初始化

int size;//记录存储数据的个数，同时可以当作指向下一个将要插入的数据位置的指针//树的初始化
void initTree(char root) {t[0].data = root;t[0].first = NULL;size++;
}

数据的插入（难点）

//寻找对应数据的下标
int find(char x) {for (int i = 0; i < size; i++) {if (t[i].data == x) {return i;}}
}
//插入树的结点
//如果想要插入，首先要知道插入的元素和它的父亲
void insert(char x, char fx) {//先将x放入到t数组中，并将x元素的孩子命名为空t[size].data = x;t[size].first = NULL;//然后再将x的下标存放再fx的的链表中int fxi = find(fx);//寻找fx的下标//申请空间chNode* s = (chNode*)malloc(sizeof(chNode));//为了方便使用，这里我们采用头插法，（无序树）s->chi = size;s->next = t[fxi].first;t[fxi].first = s;size++;
}

理解插入数据的过程：

加入我们想要插入的数据是B，如下图所示

在插入过程，我们需要将让t[2]=B，也就是t[size]=x(x是要插入的数据)，所以size即表示数组中元素的个数，又表示将插入数据的位置的下标

因为现在是在插入元素B，而暂时不考虑B的孩子下标的问题，所以让B的孩子下标为空,即t[size].first = NULL;

因为B是A的孩子，为了体现这一关系，需要在A的孩子下标处插入B的下标2，为了方便代码的编写，这里我们采用头插法。

首先我们要找到B的父亲R的下标，这里我们通过find函数来实现，并记录父亲下标为fxi

因为孩子下标是以链表的方式存储，所以我们需要申请一块孩子下标空间，也就是chNode* s = (chNode*)malloc(sizeof(chNode));

然后头插法插入数据

最后size++;

寻找父亲结点

如果我们知道一个元素，我们很容易知道这个元素的孩子都有哪些，但如果想要知道这个元素的父亲，则需要遍历整个数组，代码如下：

//寻找元素的父亲
void find_fa(int xi) {chNode* p = NULL;int flag = 0;for (int i = 0; i < size; i++) {p = t[i].first;while (p!=NULL&&p->chi!=xi){p = p->next;}if (p !=NULL && p->chi == xi) {flag = 1;printf("%c",t[i].data);break;}}if (flag == 0) {printf("根节点，没有父亲结点");}
}

寻找孩子结点

//寻找孩子结点
void find_ch(int xi) {chNode* p = t[xi].first;int chi;while (p != NULL) {chi = p->chi;printf("%c", t[chi].data);p = p->next;}
}

整体代码

#include <stdio.h>
#include <stdlib.h>//存放孩子的单链表结点结构
typedef struct childNode {int chi;//存放孩子结点的下标struct childNode* next;//写一个孩子的结点
}chNode;struct node {char data;//存放数据chNode* first;//指向孩子链表
}t[105];int size;//记录存储数据的个数，同时可以当作指向下一个将要插入的数据位置的指针//树的初始化
void initTree(char root) {t[0].data = root;t[0].first = NULL;size++;
}//寻找对应数据的下标
int find(char x) {for (int i = 0; i < size; i++) {if (t[i].data == x) {return i;}}
}
//插入树的结点
//如果想要插入，首先要知道插入的元素和它的父亲
void insert(char x, char fx) {//先将x放入到t数组中，并将x元素的孩子命名为空t[size].data = x;t[size].first = NULL;//然后再将x的下标存放再fx的的链表中int fxi = find(fx);//寻找fx的下标//申请空间chNode* s = (chNode*)malloc(sizeof(chNode));//为了方便使用，这里我们采用头插法，（无序树）s->chi = size;s->next = t[fxi].first;t[fxi].first = s;size++;
}//寻找父亲结点
void find_fa(int xi) {chNode* p = NULL;int flag = 0;for (int i = 0; i < size; i++) {p = t[i].first;while (p!=NULL&&p->chi!=xi){p = p->next;}if (p !=NULL && p->chi == xi) {flag = 1;printf("%c",t[i].data);break;}}if (flag == 0) {printf("根节点，没有父亲结点");}
}//寻找孩子结点
void find_ch(int xi) {chNode* p = t[xi].first;int chi;while (p != NULL) {chi = p->chi;printf("%c", t[chi].data);p = p->next;}
}
int main() {return 0;
}