林淑飞

(北方民族大学计算机学院，宁夏银川750021)

树的一种线性化算法

林淑飞

(北方民族大学计算机学院，宁夏银川750021)

给出了一种树的线性化算法以及从线性化结果重构树的算法.这种线性表表示法比树的其它表示法更简洁、更易管理、更节约空间.在线性表表示方式下，实现了树的求结点双亲、求结点孩子、求树的高度3个运算.从具体实现过程可以看出，线性表表示法对树的常见运算的实现都比较方便.

数据结构;树;线性化;线性表

树是一种非线性结构.具体地说，树形结构是一种层次结构，这种层次结构的特点是，任一结点的前驱如果存在则一定是唯一的，后继如果存在则可以有多个.树形结构在计算机科学中的应用十分广泛，如在编译程序中，可用树表示源程序的语法结构;在数据库系统中，可用树来组织信息;在操作系统中，可用树组织文件.

树的各种操作的实现效率具体取决于树的表示方式.树的表示方式有很多，常用的有双亲表示法、孩子表示法和孩子兄弟表示法等.本文介绍一种线性表表示法，即一种树的线性化算法.需要说明的是，本文研究的树是有序的.

1 树的线性化算法

树的线性化简单地说就是将树中的结点用一个线性表来表示.线性化树要求不能丢失树的精确结构［1－2］，即对于任意结点应该能准确找到其父结点(若存在的话)和其所有的孩子结点(若存在孩子结点的话).

如果我们试图通过简单地按层从……