树的存储结构

　　

,,提到存储结构,可以很自然的想到顺序存储结构和链式存储结构两种。树这种数据结构类型,它是由结点和联接结点的边构成。这些边,联接了树中的任意两个结点,从计算机内存中的存储方式来看,其实,就是通过指针保存了地址,从而实现了两个结点间的联接。

,,那么关于树的表示方式,先讲一下最简单的,就是双亲表示法,我把它称之为父节点表示法。毕竟,在树中,双亲结点其实就是父节点。既然,链表也是有结点构成,那么,这个结点中,必然的必须得有能够存放数据的变量,以及存放下一个结点的地址的变量,如果没有这个变量,如何建立两个结点间的联接呢?但是,此时,这个存放的地址的变量,并不是存放下一个结点的地址,存放的是它的父节点的地址,也就是父节点在数组中的下标位置,然后还得再定义一个树结构,这个数结构中,必须得包含一个数组,因为数组就是用来表示结点的,还得有一个根节点的位置变量以及结点数的变量。那么,该结构定义如下:

# define  MAX_TREE_SIZE  100年 　　typedef  int  TElemType; 　　typedef  struct  PTNode { 　　 　　,,,TElemType 数据; 　　,,,int 家长; 　　}PTNode; 　　 　　typedef 结构{ 　　 　　,,,PTNode 节点(MAX_TREE_SIZE); 　　,,,int  r,, n; 　　}PTree;

因为,根节点就是祖先,所以它没有父类,所以,约定,根节点的位置域设置为1 .

树的存储结构

如上图所示,结点一个就是根结点。

下标,,,,data ,,父母 　　,0,,,,,,,A ,,,,,,, 1 　　,1,,,,,,,B ,,,,,,, 0 　　,2,,,,,,,C ,,,,,,, 0 　　,3,,,,,,,D ,,,,,,, 0 　　,4,,,,,,,E ,,,,,,, 1 　　,5,,,,,,,F ,,,,,,, 1 　　,6,,,,,,,G ,,,,,,, 1 　　,7,,,,,,,H ,,,,,,, 2 　　,8个,,,,,,,我,,,,,,,,3 　　,9日,,,,,,,J ,,,,,,, 3

因为B的父亲是,所以B中存放了一个的下标0,C和D的父亲都是A,所以都存放了下标0 E、F和G的父亲是B,所以它们存放了B的下标1;H的父亲是C,所以H存放了下标2;I和J的父亲是D,所以它们存放了D的下标3。这种方式可以知道哪个结点是哪个结点的父亲,哪个结点是哪个结点的儿子,但是却无法确定顺序,也就是说,一个结点可能拥有多个子节点,但是却无法确定这些子节点哪个在前哪个在后。双亲表示法求父节点方便,因为每个结点中都保存了其父节点的下标。

,,第二种方式。孩子表示法。依然采用连续存储,也就是数组存储,不过,一个结点分为两部分,一部分放数据,另一部分放其子节点的指针(地址)。若是一个结点有多个孩子,假设一个有三个孩子,B, C和D .那么,一个中就存放B的指针域,在B中则存放C的指针域,C中则存放D的指针域,也就是一个的孩子采用了链式存储的方式,串联了起来。孩子表示法,求其子节点比较方便,而求其父节点就比较麻烦。

树的存储结构

孩子表示法结构代码如下:

# define  MAXZ_TREE_SIZE  100年 　　typedef  struct  CTNode { 　　,,,, 　　,,,int 儿童; 　　,,,struct  CTNode  *下; 　　}* ChildPtr; 　　 　　typedef 结构{ 　　 　　,,,TElemType 数据; 　　,,,ChildPtr 写上; 　　}CTBox; 　　 　　typedef 结构{ 　　 　　,,,CTBox 节点(MAX_TREE_SIZE); 　　,,,int  r,, n,,,,//存放树的根和结点数 　　,,,, 　　}CTree;

,,第三种方式。父亲孩子表示法。顾名思义,就是将前两种方式结合了。也就是说,一个结点不止存放数据,还存放该该节点的父节点的下标,还存放该节点子节点的指针,那为什么父节点可以存放下标,存放子节点就只能存放子节点的指针?因为,一个结点只有一个父节点,却有多个子节点,或者是没有子节点,所以没有办法确定子节点的个数,于是,就只能通过链式存储了。

树的存储结构

,,,,,,,,二叉树法(孩子兄第表示法)就是将一般树转化为二叉树。具体转化方式为:左指针指向它的第一个孩子结点,右指针指向它的第一个兄弟结点。

二叉树法结构代码定义如下:

typedef  struct  CSNode { 　　,,,, 　　,,,TElemType 数据; 　　,,,struct  CSNode  *写上,,* rightsib; 　　 　　}CSNode,, * CSTree;

树的存储结构