在孩子兄弟链表表示法中，结点形式统一，结点间的联系比较简捷。同时，在这种存储结构上容易实现树数据结构的大多数运算。
(3)双亲表示法
树上每个结点的孩子可以有任意多个，但双亲只有一个。因此，通过指向双亲的指针而将树中所有结点组织在一起形成一种存储结构是十分简法的。树的这种存储表示方法称为双亲表示法。在双亲表示法下，每个存储结点由两个域组成:数据域———用于存储树上结点中的数据元素;“指针”域———用于指示本结点之双亲所在的存储结点。值得注意的是，“指针”域的类型定义可以有两种选择。第一种是将其定义为高级语言(如C语句)中的指针类型。通过将存储结点中的指针域定义为高级语言中的指针类型，就得到各种链式存储结构，如单链表、二叉链表、孩子链表等等。第二种选择是将“指针”域定义为整型、子界型等型。严格地说，无论选择上述哪种定义，得到的都是链式存储结构，因为在这两种定义之下，各存储结点之间的联结是通过“指针”完成的，而且这些指针反映了结点之间的逻辑关系。
为了区别这两种链式结构，通常将指针域定义为高级语言中的指针类型的各种链式存储结构(如单链表、二叉链表等等)称为“动态链表”，相应的指针称为“动态指针”;将指针域定义为整型、子界型等类型的各种键式存储结构称为“静态链表”，相应的“指针”称为:“静态指针”。动态链表中的结点是通过高级语言中的标准过程例如C语言的库函数malloc(size)动态(即运行期间)生成的(动态链表由此得名)，无需事先规定链表的容量，因此动态链表的大小是动态变化的。相反，静态链有的容量必须事先说明，因而其大小是固定的。然而，在某些情况下，特别是当结点数固定不变且可事先确定时，采用静态链表往往更加方便、直观。
静态双亲链表由一个一维数组树成。数组的每个分量包含两个域:数据域和双亲域。数据域用于存储树上一个结点中的数据元素;双亲域用于存放本结点的双亲结点在数组中的序号(下标值)。
7.树的遍历
与二叉树类似，遍历是树的一种重要运算。树的主要遍历方法有以下三种。
(1)先根遍历若树非空，则
①访问根结点;
②依次先根遍历根的各个子树T 1 ，?，T m 。
(2)后根遍历若树非空，则
①依次先根遍历根的各个子树T 1 ，?，T m 。②访问根结点;
(3)层次遍历
①若树非空，访问根结点;
②若第1，?，i(i≥1)层结点已被访问，且第i+1层结点未访问，则从左到右依次访问第i+1层结点。
显然，按层次遍历所得的结点访问序列中，各结点的序号与按层编号所得的编号一致。
8.树与二叉树之间的转换
一般树转换为二叉树的基本思想是:将树中每个结点用两个链接表示就可以了，一个指向它最左边的孩子，另一个指向它右边的一个兄弟，从图形上看，具体步骤是:
①加线:在兄弟结点直接加一虚线;
②抹线:对每个结点，除了其最左的一个孩子外，抹去该结点原来与其余孩子之间的边线;
③旋转:将新加上的虚线改为实线，并将虚线以及有关的实线顺时钟旋转45度。
二叉树还原为一般树的步骤是:
①加线:若某结点是一父结点的左孩子，则将该结点的右孩子以及沿着右链搜索到的所有右孩子结点都用线与那个父结点连接起来;
②抹线:抹去原二叉树中所有结点与其右孩子的连线;
③旋转:将虚线及有关实线逆时钟旋转约45度，并将几个结点按层次排列。
9.二叉树与森林之间的转换
森林转换为二叉树的步骤是:
①将森林中的每棵树转换为二叉树;
②森林中第一棵树的根结点就是转换后二叉树的根结点，依次将后一棵树作为前一棵树根结点的右子树。
二叉树转换为森林的步骤是:
①森林第一棵树的根就是二叉树的根;
②二叉树的左子树转换为森林的第一棵树，二叉树的右子树对应于森林中其余的树;③二叉树右子树的根结点作为余下树中第一棵树的根结点??，以此类推。
五、图
图的概念
图是一种较线性表和树形结构更为复杂的数据结构。在线性表中每个数据元素只有一个(直接)前驱和后继，即各数据元素之间仅有线性关系。在树形结构中，数据元素之间有明显的层次关系，每一层中的数据元素只和上一层中的一个元素(即双亲结点)相关。而在图中，任意两个数据元素之间均有可能相关。
图(graph)是图型结构的简称。它是一种复杂的非线性数据结构。图在各个领域都有着广泛的应用。图的二元组定义为:
G=(V，E)
其中，V是非空的顶点集合，即
V={v i |1≤i≤n，n≥1，v i ∈elemtype，n为顶点数｝
E是V上二元关系的集合，一般只讨论仅含一个二元关系的情况，且直接用E表示这个关系。这样，E就是V上顶点的序偶或无序对(每个无序对(x，y)是两个对称序偶和的简写形式)的集合。对于V上的每个顶点，在E中都允许有任意多个前驱和任意多个后继，即对每个顶点的前驱和后继个数均不加限制。回顾一下线性表和树的二元组定义，都是在其二元关系上规定了限制条件，线性表的限制条件是只允许每个结点有一个前驱和一个后继，树的限制条件是只允许每个结点有一个前驱。因此，图比线性表和树更具有广泛性，它包含线性表和树在内，线性表和树可以认为是图的简单情况。
对于一个图G，若E是序偶的集合，则每个序偶对应图形中的一条有向边，若E是无序对的集合，则每个无序对对应图形中的一条无向边，所以可把E看作为边的集合。这样，图的二元组定义可叙述为:图的非空顶点集(vertexset)和边集(edgeset)所组成。针对图G，顶点集和边集可分别记为V(G)和E(G)。边集E(G)允许是空集，若是空集，图G中的顶点均为孤立顶点。对于一个图G，若边集E(G)为有向边的集合，则称此图为有向图(digraph)，若边集E(G)为无向边的集合，则称此图为无向图(undigraph)。
六、排序
1.直接插入排序
直接插入排序的基本思想是把表中元素依次插入一个已排好序的表中，就像人们打扑克摸牌时把牌插入手中的若干张牌里一样。表中n个元素依次插入的比较次数为1+2+3+?+(n-1)=n(n-1)/2。在插入时，元素的移动次数最多为1+2+3+?+(n-1)=n(n-1)/2。如果表中元素已排好序，则只需比较n-1次，而移动次数为0。
2.直接选择排序
直接选择排序的基本思想是在表的n个元素中，经过n-1次比较得到其最大值(或最小值，下同)，这就排好了第一个元素;再经过n-2次比较得到余下元素中的最大值，这就排好了第二个元素?直到比较1次后排好第n-1个元素，第n个元素的位置也就自然确定了。所需的比较次数为(n-1)+(n-2)++1=n(n-1)/2。所需移动次数最多也为n(n-1)/2。如果表中元素排好序，也需要比较n(n-1)/2次，而移动次数为0。
3.冒泡排序
冒泡排序的基本思想是将表中元素两个相邻元素依次比较，若不符合排序要求，则交换位置，这样经过n-1次比较后，将确定出最大(或最小)元素的位置，这称为一趟扫描。经过n-1次扫描后，就完成了整个表的排序。第一趟扫描的比较次数是n-1，第二趟扫描的比较次数是n-2??，总的比较次数是(n-1)+(n-2)+??+1=n(n-1)/2。如果恰好表中元素按反序排列，则需要移动的次数为3×n(n-1)/2。如果表中元素已排好序，并采用交换标志来表示并未发生过交换，则只需一趟扫描，只比较n-1次，就够了;当然，移动次数也是0。
4.归并排序
归并排序的基本思想是表中元素两两比较排序，使表中的n个元素变成n/2个已排序的组，再两两组比较，而变成n/4个已排序的组??，直到表中只含有一个已排序的组，即完成排序。所需要的比较次数为nlog 2 n，移动次数为n。若表已排好序，则比较次数仍为nlog 2 n，但移动次数为0。
5.快速排序
快速排序的基本思想是把表中某元素作为基准，将表划分为大于该值和小于该值的两部分，然后用递归的方法处理这两个子表，直到完成整个表的排序。快速排序的比较次数为(n-1)+(n-2)+?+1=n(n-1)/2，移动次数最多也是n(n-1)/2。如果每次的基准元素刚好是表的中值，使表分为大小相等的两个子表，则比较次数为nlog 2 n;如果表已排好序，则移动次数为0。
6.常用排序方法的性能比较如下表所示:
常用排序方法的性能比较
排序方法 平均时间 最坏情况的时间 辅助存储
冒泡法、直接选择法、直接插入法 O(n2 ) O(n2 ) O(1)
快速排序 O(nlog2 n) O(n2 ) O(log2 n)
堆排序 O(nlog2n) O(nlog2 n) O(1)
归并排序 O(nlog2 n) O(nlog2 n) O(n)
注:在上表中，我们将n(n-1)/2也记为O(n2 )。如果在待排序的表中含有多个码值相同的记录，经过排序后，这些记录的相对次序不变，则称这种排序方法是稳定的，否则是不稳定的。根据上述说法，可以看出直接插入法、归并法是稳定的;而直接选择法、冒泡法、快速排序法、堆排序法是不稳定的。
七、检索
1.顺序检索
检索又称为查找。顺序检索是将待查找的关键码值与线性表中个结点的关键码值逐一比较，直到找到所需的记录，检索成功;或者在表中找不到所需记录而检索失败。顺序检索不要求线性表事先排序。设线性表有n个元素，则最多检索次数为n，最少检索次数为1。
2.二分法检索
二分法检索要求线性表结点按关键排序且以顺序方式存储。在查找时，首先与表的中间位置上结点的关键值比较，若相等则检索成功;否则根据比较结果确定下一步在表的前半部或后半部中继续进行。二分法检索的效率较主动，设线性表有n个元素，则最多的检索次数为大于log 2 n的最小整数，最少的检索次数为1。
3.分块检索
分块检索把线性表分成若干块，块内结点不必有序，但块与块之间必须有序，即每一块中各结点的关键值必须大于(或小于，与此类推)前一块最大关键值。为加快查找，还要建立一个索引表，表中给出每一块的最大关键值和指向块内第一个结点位置的指针。分块检索分两步进行，先查索引表，确定要找的记录在哪一块;然后再在相应的块中检索。分块检索适合于线性表很大，数据又是动态变化的情况。在查索引表时，可采用顺序法或二分法;在块内查找所求记录时，采用顺序法。由于分块而缩小了查找范围，从而加快检索速。
4.散列表检索
根据关键值，就可以迅速找到该记录所对应的存储位置，这就是建立在散列函数基础上的散列检索。设记录的关键值为k，则该记录的存储位置可用散列函数H来计算H=H(k)。常用来产生的散列函数的方法是除余法，即取H(k)=k mod p设散列表长度为n，取p为小于n的最大素数。一般说来，关键码值的集合比散列表存储位的数目大得多，这正是体现散列表的优势所在，但同时带来了冲突问题，即不同的关键值经散列函数计算，可能得到相同的存储位置。一个好的散列函数应该使冲突的可能性尽量小。最常用的解决冲突的方法是线性探测法，就是在发生冲突时，从H(k)以后的位置逐一探测，直至找到一个空位置，将新记录插入;在检索时，如果H(k)中不是所需关键值的记录，也是从H(k)往下逐一搜索，直到找到所需关键值或查找失败为止。应注意查找次序是:H(k)，H(k)+1，H(k)+2，?n-1，0，1，2，?，H(k)-1即在n-1以后，又从0开始，因为在位置上是循环的。双重散列技术是对线性探测法的改进。它使用两个散列函数H1和H2。对关键值k，计算H1(k)，求得0到n-1之间的一个散列地址;若在这个地址上冲突，下一个被探测的地址为(H1(k)+H2(k))mod n，关于选择H2的方法在此不做讨论。