数据结构－树

树

树的存储

1.双亲表示法：

以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指向其双亲结点到链表中的位置

#define MAX_TREE_SIZE 100
typedef int ELemType
typedef struct PTNode //结点结构
{
ElemType data; //结点数据 
int partent;  //双亲位置
}PTNode;
typedef struct
{
PTNode nodes[MAX_TREE_SIZE]; //结点数组
int r; //根
int n;//结点
}PTree

2.孩子双亲表示法:

把每个结点的孩子排列起来，以单链表做存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针有组成一个线性表，采用顺序存储结构，存放进入一个一维数组中.

#define MAX_TREE_SIZE 100
typedef char ElemType 
typedef struct CNode //孩子结构
{
int data; 孩子所在数组的下标
struct CNode *next;//指向下一个孩子结点的指针
}*ChildPtr;
typedef struct //表头结构
{
ElemType data;//结点数据
ChildPtr firstchild;//指向第一个孩子的指针
}CTbox;
typedef struct //将两个结构联合起来
{
CTbox nodes[MAX_TREE_SIZE];
int r,n;//树的根，结点
}

3.孩子兄弟表示法：

我们发现，任意一颗树，它的结点的第一个孩子如果存在就是的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。

typedef int ElemType
typedef struct CSNode
{
ElemType data;
struct CSNode *firstchild *rightsib;
}CSNode,*CSTree;

二叉树