之前，我们介绍的所有的数据结构都是线性存储结构。本章，我们所介绍的树的结构是⼀种⾮线 性的存储结构。存储的是具有⼀对多的关系的数据元素的集合。
1.树的定义
树是由n(n>=0)个结点组成的有限集，n=0时为空树，且对于非空树：
有且仅有一个特定的称为根的结点；
当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每一个集合本身又是一 棵树，称为根的子树(subtree)。
这里使用了递归定义。树中的每个结点都是某一子树的根。结点包含数据项和指向其它结点的分支信息。
2.基本术语
1.结点：一个数据元素+若干指向子树的分支
2.结点拥有的子树数（或分支数）称为结点的度。结点A的度是3，C的是1，G的是零。
3.度为零的结点称为叶子结点/终端结点。K，L，F，G，M，I，J是叶子结点。度不为零的结点称为分支结点/非终端结点。
4.结点的子树的根称为该结点的孩子，该结点称为孩子的双亲。D的孩子是H，I和J，D的双亲是A。
4.同一个双亲的孩子是兄弟。 H，I和J是兄弟。
5.双亲在同一层的结点称为堂兄弟
6.结点的祖先是从根到该结点所经过的所有结点。 M的祖先是A、D和H。
7.结点的子孙是该结点下层子树中的任意结点。 B的子孙为E、F、K和L。
8.结点的层次：从根到该结点的层数（根结点为第一层）。
9.树的深度： 指所有结点最大的层数（Max{各结点的层数}）。
10.树的度：所有结点度的最大值（Max{各结点的度}）。上图中树的度为3
11.有序树： 结点各子树从左至右有序，不能互换（左为第一）
12.无序树 ：结点各子树可互换位置
13.森林： 指m棵互不相交的树的集合
14.任何一棵非空树是一个二元组Tree =（root，F） root 被称为根结点，F被称为子树森林
3.树结构和线性结构的比较
4.树的性质
参考文档：数据结构：树(Tree)【详解】_数据结构 树-CSDN博客
5.树的存储结构
1.双亲表示法
1.代码展示
#include <stdlib.h>
#include <stdio.h>
# include <string.h>
struct node{
int data;
int fi;//father_i,如果fi==-1,认为是根节点。
}t[1000];
int size;//节点的真实个数
void initTree(int x)
{
//加入根节点；
t[1].data=x;
t[1].fi=-1;
size++;
}
int find(int fx)
{
for(int i=1;i<=size;i++)
{
if(t[i].data==fx)
{
return i;
}
}
return -1;
}
void insert(int x,int fx)
{
size++;
t[size].data=x;
int fx_i=find(fx);
if(fx_i==-1)
{
printf("%d的父亲不存在\n",x);
return ;
}
t[size].fi=fx_i;
}
void find_ch(int x)
{
int x_i=find(x);
int sum=0;//
for(int i=1;i<=size;i++)
{
if(t[i].fi==x_i)
{
sum++;
printf("%d ",t[i].data);
}
}
if(sum==0)
{
printf("%d没有孩子节点",x);
}
printf("\n");
}
void find_fa(int x)
{
int x_i=find(x);
int fa_i=t[x_i].fi;
if(fa_i==-1)
{
printf("该节点是根节点，没有父亲节点");
}
else{
printf("%d ",t[fa_i].data);
}
printf("\n");
}
int main()
{
int n;//节点的总数
scanf("%d",&n);
int root;//根节点的数据
scanf("%d",&root);
initTree(root);
int x,fx;//fx是x的父亲
for(int i=2;i<=n;i++)
{
scanf("%d %d",&x,&fx);
insert(x,fx);
}
//寻找x的孩子和父亲
scanf("%d",&x);
find_ch(x);
find_fa(x);
return 0;
} 2.优缺点说明
由于根结点是没有双亲的，所以我们约定根结点的位置域设置为-1，这也就意味着，我们所有的结点都存有它双亲的位置。这样的存储结构，我们可以根据结点的parent指针很容易找到它的双亲结点，所⽤的时间复杂度为O(1)，直到parent为-1时，表示找到了树结点的根。
可如果我们要知道结点的孩子是什么，对不起，请遍历整个结构才行。 这真是麻烦，能不能改进⼀下呢?当然可以。我们增加⼀个结点最左边孩⼦的域，不妨叫它长子域，这样就可以很容易得到结点的孩⼦。如果没有孩⼦的结点，这个长子域就设置为-1。 对于有0个或1个孩子结点来说，这样的结构是解决了要找结点孩⼦的问题了。甚⾄是有2个孩子，知道了长子是谁，另⼀个当然就是次子了。
另外⼀个问题场景，我们很关注各兄弟之间的关系，双亲表示法⽆法体现这样的关系，那我们怎么办?嗯，可以增加⼀个右兄弟域来体现兄弟关系，也就是说， 每⼀个结点如果它存在右兄弟，则记录下右兄弟的下标。同样的，如果右兄弟不存在，则赋值为-1。 但如果结点的孩⼦很多，超过了2个。我们⼜关注结点的双亲、⼜关注结点的孩⼦、还关注结点的 兄弟，⽽且对时间遍历要求还⽐较⾼，那么我们还可以把此结构扩展为有双亲域、⻓⼦域、再有右兄弟域。存储结构的设计是⼀个⾮常灵活的过程。⼀个存储结构设计得是否合理，取决于基于该存储结构的 运算是否适合、是否⽅便，时间复杂度好不好等。
2.孩子表示法
1.代码展示
#include <stdlib.h>
#include <stdio.h>
# include <string.h>
//孩子链表的结点结构
typedef struct chNode{
char data;
struct chNode* next;
}chNode;
//树的结构
struct Tree{
char data;
chNode* first;
}t[1005];
int size;
void initTree(char root)
{
size++;
t[size].data=root;
t[size].first=NULL;
}
int find(char fx)
{
for(int i=1;i<=size;i++)
{
if(t[i].data==fx)
{
return i;
}
}
return -1;
}
void insert(char x,char fx)
{
size++;
t[size].data=x;//先把数据放到数组中
t[size].first=NULL;
//建立 x和 fx的父子关系
int fx_i=find(fx);//fx_i是fx的下标
if(fx_i!=-1)
{
chNode* s=(chNode*)malloc(sizeof(chNode));
s->data=x;
//头插法
s->next=t[fx_i].first;
t[fx_i].first=s;
}
}
void find_ch(char x)
{
int x_i=find(x);
chNode* p=t[x_i].first;
if(p==NULL)
{
printf("%c没有孩子结点\n",x);
return;
}
while(p!=NULL)
{
printf("%c ",p->data);
p=p->next;
}
printf("\n");
}
void find_fa(char x)
{
chNode* p=NULL;
int flag=0;
for(int i=1;i<=size;i++)
{
p=t[i].first;
while(p!=NULL&&p->data!=x)
{
p=p->next;
}
if(p!=NULL&&p->data==x)
{
printf("%c\n",t[i].data);
flag=1;
break;
}
}
if(flag==0)
{
printf("%c是根节点\n",x);
}
}
int main()
{
int n;//结点个数
scanf("%d",&n);
char root;
getchar();
scanf("%c",&root);
initTree(root);
char x,fx;
for(int i=2;i<=n;i++)
{
getchar();
scanf("%c %c",&x,&fx);
insert(x,fx);
}
getchar();
scanf("%c",&x);
find_ch(x);
find_fa(x);
return 0;
}
3.孩子兄弟表示法
1.代码展示
#include <stdlib.h>
#include <stdio.h>
# include <string.h>
//孩子兄弟表示法---二叉链表
typedef struct Node{
char data;
struct Node* first;//指向第一个孩子
struct Node* bro;//指向右边第一个亲兄弟
}TNode,*TreeList;
TreeList initTree(char root)
{
TNode* s=(TNode*)malloc(sizeof(TNode));
s->data=root;
s->first=s->bro=NULL;
return s;
}
//大问题是：在以r为根节点的树中，找到fx所在的结点
//1.和根结点对比，r->data==fx,reture r; 否则执行2
//2.问题转化为去以r->first为根的子树中找fx find(r->fisrt,fx)
//3.或者 以r->bro为根的子树中找fx find(r->beo,fx)
//递归出口： r==NULL
TNode* find(TreeList r,char fx)
{
if(r==NULL||r->data==fx)
{
return r;
}
if(r->first!=NULL)
{
TNode* ans=find(r->first,fx);
if(ans!=NULL&&ans->data==fx)
{
return ans;
}
}
if(r->bro!=NULL)
{
TNode* ans=find(r->bro,fx);
if(ans!=NULL&&ans->data==fx)
{
return ans;
}
}
return NULL;//若fx不存在树中，NULL
}
//往以r为根节点的树中，插入数据x，x的父亲数据是fx
void insert(TreeList r,char x,char fx)
{
TNode* f=find(r,fx);
if(f==NULL)
{
printf("该父亲结点不存在，插入失败\n");
return ;
}
TNode* s=(TNode*)malloc(sizeof(TNode));
s->data=x;
//s->first=NULL;
if(f->first==NULL)
{//x是长子
f->first=s;
s->first=NULL;
s->bro=NULL;
}
else
{//x不是长子
TNode* fir=f->first;
s->bro=fir->bro;
fir->bro=s;
s->first=NULL;
}
}
int main()
{
int n;//结点个数
char root;
TreeList r=NULL;
scanf("%d",&n);
getchar();
scanf("%c",&root);
r=initTree(root);
char x,fx;
for(int i=2;i<=n;i++)
{
getchar();
scanf("%c %c",&x,&fx);
insert(r,x,fx);
}
getchar();
scanf("%c",&x);
TNode* p=find(r,x);
TNode* fir=p->first;
if(fir!=NULL)
{
p=fir;
while(p!=NULL)
{
printf("%c ",p->data );
p=p->bro;
}
}
}
/*
10
A
B A
C A
D A
E B
F B
G B
H D
I D
J E
D
*/
/*
H I
*/
2.优缺点说明
这种表示法，给查找某个结点的某个孩⼦带来了⽅便，只需要通过firstchild找到此结点的⻓⼦， 然后再通过⻓⼦结点的rightsib找到它的⼆弟，接着⼀直下去，直到找到具体的孩⼦。当然，如果想找某个结点的双亲，这个表示法也是有缺陷的，那怎么办呢? 对，如果真的有必要，完全可以再增加⼀个parent指针域来解决快速查找双亲的问题，这⾥就不再细谈了。
标签：5.1,结点,NULL,复习,fx,int,数据结构,data,first From： https://blog.csdn.net/2301_81070376/article/details/139391615