6.3树的存储结构( 三 ) _结点

第二种方案
每个结点指针域的个数等于该结点的度，专门取一个位置来存储结点指针域的个数
如下
data为数据域，为度域，也就是存储该结点的孩子结点的个数，到为指针域，指向该结点的各个孩子的结点
实现如图所示
这种方法克服了浪费空间的缺点，对空间利用率提高了很多，但是各个结点的链表是不相同的结构，加上要维护结点的度的数值，在运算上就会带来时间上的损耗
能不能有既可以减少空指针的浪费又能使结点结构相同。
我们为了要便利整棵树，把每个结点放到一个顺序存储结构的数组中是合理的，但，每个结点的孩子有多少是不确定的，所以我们再对每个结点的孩子建立一个单链表来体现它们的关系
? 这就是孩子表示法。具体办法是，把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中
如下图：
图中：
? data 是表示表头结点，其中data是数据域，存储某结点的数据信息。是头指针域，存储该结点的孩子链表的头指针
? child next中child是数据域，用来存储某个结点在表头数组中的下标。next是指针域，用来指向某结点的下一个孩子结点的指针
代码实现如下：
/*树的孩子表示法结构定义*/#define MAX TREE SIZE 100typedef struct CTNode/* 孩子结点*/{int child;struct CTNode *next;}typedef struct //表头结构{TelemType data;ChildPty firstchild;}CTBox;typedef struct//树结构{CTGBox nodes[MAX_TREE_SIZE]; //结点数组int r,n;//根的位置和结点数}CTree;
? **这样的结构对于我们要查找某个结点的某个孩子，或者找某个结点的兄弟，只需要查找这个结点的孩子单链表即可。**对于遍历整棵树也是很方便的，对头结点的数组循环即可。
6.3.3孩子兄弟表示法
任意一个树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此设置两个指针，分别指向该结点的第一个孩子和此节点的右兄弟
如图
? 其中data是数据域，为指针域，存储该结点的第一个孩子结点的存储地址，是指针域，存储该结点的右兄弟结点的存储地址。
代码实现：
/*树的孩子兄弟表示法结构定义*/typedef struct CSNode{TElemType data;struct CSNodeZ* firstchild, *rightsib;} CSNode, *CSTree;
实现效果：
这种表示法，给查找某个结点的某个孩子带来了方便
通过找到此结点的长子，
然后再通过长子结点的找到它的二弟，
接着一直下去，直到找到具体的孩子。
当然，如果想找某个结点的双亲，这个表示法也是有缺陷的
在来个指针就可以了对吧！~~
上述这种孩子兄弟表示法最大的好处是它把一颗复杂的树变成了一颗二叉树
如下所示
好，开始学二叉树喽~~~
6.4 二叉树的定义
二叉树(Tree) 是n(n≥0)个结点的有限集合，该集合或者为空集(称为空二叉树)，或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的叉树组成。
看一个不是二叉树的情况
D结点不满足二叉树，因为它有三个子树
6.4.1 二叉树特点
1.每个结点最多有两颗子树，所以二叉树中不存在大于2的结点。不是只有两颗子树，而是最多有。没有子树或者一颗子树的也是可以的！
2.左子树和右子树是有顺序的，次序不能任意颠倒