数据结构树
换向器的作用-小学数独九宫格
2023年2月23日发(作者：美秀美术馆)数据结构之树（三）——树的存储结构（三种）
双亲表⽰法
实现：定义结构数组存放树的结点，每个结点含两个域：
数据域：存放结点本⾝信息。
双亲域：指⽰本结点的双亲结点在数组中的位置。
例⼦：
上图所⽰树的双亲表⽰法的数组下标为：
特点：找双亲容易，找孩⼦难。
类型定义：
typedefstructPTNode//结点结构
{
TElemTypedata;
intparent;//双亲位置域
}PTNode;
#defineMAX_TREE_SIZE100
typedefstruct//树结构
{
PTNodenodes[MAX_TREE_SIZE];
intr,n;//根结点的位置和结点个数
}PTree;
孩⼦链表
实现：把每个结点的孩⼦结点排列起来，看成是⼀个线性表，⽤单链表存储，则n个结点有n个孩⼦链表(叶⼦的孩⼦链表为空表)。⽽n
个头指针⼜组成⼀个线性表，⽤顺序表(含n个元素的结构数组)存储。
例⼦：
类型定义：
1.孩⼦结点结构
typedefstructCTNode
{
intchild;
structCTNode*next;
}*ChildPtr;
2.双亲结点结构
typedefstruct
{
TElemTypedata;
ChildPtrfirstchild;//孩⼦链表的头指针
}CTBox;
3.树结构
typedefstruct
{
CTBoxnodes[MAX_TREE_SIZE];
intn,r;//结点数和根结点的位置
};
特点：找孩⼦容易，找双亲难。
为了解决找双亲难得问题，可以在双亲结点⾥增设⼀个指针域，存放双亲结点的下标——带双亲的孩⼦链表。
孩⼦兄弟表⽰法(⼆叉树表⽰法，⼆叉链表表⽰法)
实现：⽤⼆叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第⼀个孩⼦结点和下⼀个兄弟结点。
类型定义：
typedefstructCSNode
{
ElemTypedaya;
structCSNode*firstchild,*nextsibling;
}CSNode,*CSTree;
例⼦：
特点：找孩⼦容易，找孩⼦的兄弟容易，找双亲难。
可以给每个结点增设⼀个指针域，从⽽解决找双亲难的问题。