树的存储方式有多种即可采用順序存储结构，又可采用链式存储结构无论哪种方式都要反映出树中各结点之间的逻辑关系，下面介绍3种常用的存储结构

这种存储方式采用哟组连续空间来存储每个结点同时在每个结点种增设一个伪指针，指示其双亲结点在数组中的位置

双亲表示法的存储结构描述 内聯代码片。

该存储结构利用了每个结点（根结点除外）只有唯一双亲的性质可以很快得到每个结点的双亲结点，但求结点的孩子时需要遍历整个结构

孩子表示法是将每个结点的孩子结点都用单链表链接起来形成一个线性结构，此时n个结点就有n个孩子链表（叶子结点的孩孓链表为空表）如下图
这种存储方式寻找子女的操作非常直接而寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表.

1.3 駭子兄弟表示法

孩子兄弟表示法又称二叉树表示法，即以二叉树表作为树的存储结构孩子兄弟表示法使每个结点包括三部分内容：结点值、指向结点第一个孩子结点的指针及指向结点下一个兄弟结点的指针。
孩子兄弟表示法的存储结构描述如下 内联代码片

由于二叉树和樹都可以用二叉链表作为存储结构，因此以一叉链表作为媒介可以导出树与二叉树的一个对应关系即给定一棵树， 可以找到唯一的一 棵②叉树与之对应从物理结构上看，它们的二叉链表是相同的只是解释不同而已。
树转换为二叉树的规则:每个结点左指针指向它的第一個孩子 右指针指向它在树中的相邻右兄弟，这个规则又称“左孩子右兄弟”由于根结点没有兄弟，所以对应的二又树没有右子树
树转換成:又树的画法:①在兄弟结点之间加连线: ②对每个结点只保留它与第一个孩子的连线，而与其他孩子的连线全部抹掉:③以树根为轴心顺時针发转45℃
森林转换成二又树的画法:①将森林中的每棵树转换成相应的二叉树:②每棵树的根也可视为兄弟关系，在每棵树的根之间加一根连线: ③以第一棵树的根 为轴心顺时针旋转45°。
二又树转换为森林的规则:若二叉树非空则二叉树的根及其左子树为第一棵树的 二叉树形式，故将根的右链断开二叉树根的右子树又可视为一一个由除第一 棵树 外的森林转换后的二叉树，应用同样的方法直到最后只剩棵没囿右子树的二 叉树为止，最后再将每棵二叉树依次转换成

树的遍历是指用某种方式访问树中的每个结点且仅访问次。 主要有两种 方式:
1)先根遍历若树非空，先访问根结点再依次遍历根结点的每棵子树，遍历子树时仍遵循先根后子树的规则其遍历序列与这棵树相应二叉樹的先序序列相同。
2)后根遍历若树非空，先依次遍历根结点的每棵子树再访问根结点， 遍历子树时仍遵循先子树后根的规则其遍历序列与这棵树相应二叉树的中序序列相同。
按照森林和树相互递归的定义可得到森林的两种遍历方法。
1)先序遍历森林若森林为非空，則按如下规则进行遍历:
●访问森林中第一棵树 的根结点
●先序遍历第一 棵树中根结点的子树森林。
●先序遍历除去第一棵树之后剩余的樹构成的森林
2)中序遍历森林。森林为非空时按如下规则进行遍历:
●中序遍历森林中第一 棵树的根结点的子树森林。
●访问第棵树的根結点
●中序遍历除去第一 棵树之后剩余的树构成的森林。

在采用树的双亲指针数组表示作为并查集的存储表示时集合元素的编号从0到size-1。其中size是最大无素的个数下面是并查集主要运算的实现。
并查集的结构定义如下:

并查集的初始化操作(s即为并查集):

Find操作(函数在并查集S中查找并返回包含元素x的树的根):

Union操作(函数求两个不相交子集合的并集):