一对一的数据结构:线性表
一对多的数据结构:树
树的定义:
树是n(n>=0)个结点的有限集;当n = 0时称为空树,在任意一颗非空树中:
1、n > 0时,有且仅有一个特定的称为根的结点
2、当n > 1时,其余结点可分为m(m> 0)个互不相交的有限集T1、T2、……Tm,其中每一个集合本身又是一棵树,并且称为根的子树
结点的分类:
结点拥有的子树称为结点的度,树的度取决于树内各结点的度的最大值
度为0的结点称为叶结点或终端结点
度不为0的结点称为分支结点或非终端结点,除根结点外,分支结点也称为内部结点
树中结点的最大层次称为树的深度或高度
如果将中结点的各子树看成从左至右是有次序的,不能互换的,则成该树为有序树,否则称为无序数
双亲表示法:
定义:
//树的双亲表示法结点结构定义
#defineMAX_TREE_SIZE 100
typedefint ElemType;
typedefstruct PTNode
{
ElemType data;//结点数据
int parent;//双亲位置
}PINode;
typedefstruct
{
PINode nodes[MAX_TREE_SIZE];
int r; //根的位置
int n; //结点数目
}PTree;
孩子表示法:
双亲孩子表示法:
双亲孩子表示法代码(顺序不可改变):
#defineMAX_TREE_SIZE 100
typedefchar ElemType;
//孩子结点
typedefstruct CTNode
{
int child; //孩子结点的下标
struct CTNode *next; //指向下一个孩子结点的指针
}*ChildPtr;
//表头结构
typedefstruct
{
ElemType data; //存放在树中的结点的数据
int parent; //存放双亲的下标
ChildPtr firstchild;//指向第一个孩子的指针
}CTBox;
//树结构
typedefstruct
{
CTBox nodes[MAX_TREE_SIZE]; //结点数组
int r,n;
}