三、数组
线性表（包括栈和队列）都是线性结构，结构中的每个元素只是无结构的数据元素。我们对线性表作进一步的推广，使结构中的元素本身也可以是具有某种结构（如向量）的数据，从而引出了数组这一种新的数据结构。
（1）数组的定义和运算
类似于线性表，一个二维数组（或称矩阵）可以看成是由m个行向量所组成的向量，也可以看成是由n个列向量所组成的向量。
对于数组的运算，主要有检索或存取数组中某个元素。
（2）数组的顺序存储结构
由于对数组一般不作插入或删除运算，因此，一旦数组被建立，则结构中的元素个数和元素之间的关系就不再发生变动。对这种情况采用顺序存储结构表示数组是比较恰当的。
由于计算机存储单元是一维的结构，而数组是多维的结构，因此就必须把多维结构映射为一维的结构，即把多维结构按一定次序排列成一维的。
四、树型结构
线性表、栈和队列等数据结构所表达和处理的数据以线性结构为组织形式。然而，在计算机科学和计算机应用的各个领域中，存在着大量需要用更复杂的逻辑结构加以表示的问题。因此必须研究更复杂的逻辑结构及相应的数据结构。树形结构就是这些更复杂的结构中最重要的一类。
1.树的基本概念
树是一类重要的树形结构，其定义如下:树是n（n>0）个结点的有穷集合，满足:
（1）有且仅有一个称为根的结点;
（2）其余结点分为m（m≥0）个互不相交的非空集合，T 1 ，T 2 ，…，T m ，这些集合中的每一个都是一棵树，称为根的子树。
在树上，根结点没有直接前趋。对树上任一结点X来说，X是它的任一子树的根结点惟一的直接前趋。为了讨论方便，我们引入树的若干习惯术语。树上任一结点所拥有的子树的数目称为该结点的度。度为0的结点称为叶子或终端结点。度大于0的结点称为非终端结点或分支点。一棵树中所有结点的度的最大值称为该树的度。若树中结点A是结点B的直接前趋，则称A为B的双亲或父结点，称B为A的孩子（即“子女”）或子结点。易知任何结点A的孩子B也就是A的一棵子树的根结点，父结点相同的结点互称为兄弟。一棵树上的任何结点（不包括根本身）称为根的子孙。反之若B是A的子孙，则称A是B的祖先，结点的层数（或深度）从根开始算起:根的层数为1，其余结点的层数为其双亲的层数加1。一棵树中所有结点层数的最大值称为该树的高度或深度。
树（及一切树形结构）是一种“分支层次”结构。所谓“分支”是指树中任一结点的子孙可以按它们所在的子树的不同而划分成不同的“分支”;所谓“层次”是指树上所有结点可以按它们的层数划分不同的“层次”。在实际应用中，树中的一个结点可用来存储实际问题中的一个数据元素，而结点间的逻辑关系（即父结点与子结点之间的邻接关系）往往用来表示数据元素之间的某种重要的、必须加以表达的关系。
用图示法表示任何树形结构时，箭头的方向总是从上到下，即从父结点指向子结点，因此，可以简单地用连线代替箭头。
2.树的基本运算包括:
①求根ROOT（T），引用型运算，其结果是结点X在树T的根结点。
②求双亲PARENT（T，X），引用型运算，其结果是结点X在树T上的双亲结点;若X是树T的根或X不在T上，则结果为一特殊标志。
③求孩子CHILD（T，X，i），引用型运算，其结果是树T上的结点X的第i个孩子;若X不在T上或X没有第i个孩子，则结果为一特殊标志。
④建树CREATE（X，T 1 ，…，T k ）k≥1，加工型运算，其作用是建立一棵以X为根，以T 1 ，…，T k 为第1，…k棵子树的树。
⑤剪枝DELETE（T，X，i），加工型运算，其作用是删除树T上结点X的第i棵子树;若T无第i棵子树，则为空操作。
3.二叉树
（1）二叉树的基本概念
二叉树是结点的有穷集合，它或者是空集，或者同时满足下述两个条件:（1）有且仅有一个称为根的结点:
（2）其余结点分为两个互不相交的集合T 1 、T 2 ，T 1 与T 2 都是二叉树，并且T 1 与T 2 有顺序关系（T 1 在T 2 之前），它们分别称为根的左子树和右子树。
二叉树是一类与树不同的树形结构。它们的区别是:第一，二叉树可以是空集，这种二叉树称为空二叉树。第二，二叉树的任一结点都有两棵子树（当然，它们中的任何一个可以是空子树），并且这两棵子树之间有次序关系，也就是说，它们的位置不能交换。相应地，二叉树上任一结点左、右子树的根分别称为该结点的左孩子和右孩子。另外，二叉树上任一结点的度定义为该结点的孩子数（即非空子树数）。除这个几个术语之外，树的其它术语也适用于二叉树。
特别值得注意的是，由于二叉树上任一结点的子树有左、右之分，因此即使一结点只有一棵非空子树，仍须区别它是该结点的左子树还是右子树，这是与树不同的。
（2）二叉树的性质
在某些情况下，了解二叉树的下列性质是有帮助的。
4.二叉树的存储结构
二叉树通常有两类存储结构，顺序存储结构和链式存储结构。
（1）二叉树的链式存储结构
二叉树有不同的链式存储结构，其中最常用的是二叉树链表与三叉链表。
其中，data域称为数据域，用于存储二叉树结点中的数据元素;lchild域称为左孩子指针域，用于存放指向本结点左孩子的指针（这个指针及指针域有时简称为左指针）。类似地，rchild域称为右孩子指针域，用于存放指向本结点右孩子的指针（简称右指针）。二叉链表中的所有存储结点通过它们的左、右指针的链接而形成一个整体。此外，每个二叉链表还必须有一个指向根结点的指针，该指针称为根指针。根指针具有标识二叉链表的作用，对二叉链表的访问只能从根指针开始。值得注意的是，二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是指向该结点的一个孩子的指针，或者是空指针NULL。
若二叉树为空，则root=NULL。若某结点的某个孩子不存在，则相应的指针为空。具有n个结点的二叉树中，一共有2n个指针域，其中只有n-1个用来指向结点的左右孩子，其余的n+1个指针域为NULL。
二叉树的链式存储结构操作方便，表达简明（二叉树的逻辑关系———结点间的父子关系———在二叉链表和三叉链表中被直接表达成对应存储结点之间的指针），因而成为二叉树最常用的存储结构。然而在某些情况下，二叉树的顺序存储结构也很有用。
（2）二叉树的顺序存储结构
二叉树的顺序存储结构由一个一维数组构成，二叉树上的结点按某种次序分别存入该数组的各个单元。显然，这里的关键在于结点的存储次序，这种次序应能反映结点之间的逻辑关系（父子关系），否则二叉树的基本运算就难以实现。
由二叉树的性质5可知，若对任一完全二叉树上的所有结点按层编号，则结点编号之间的数值关系可以准确地反映结点之间的逻辑关系。因此，对于任何完全二叉树来说，可以采用“以编号为地址”的策略将结点存入作为顺序存储结构的一维数组。具体地说就是:将编号为i的结点存入一维数组的第i个单元。
在这一存储结构中，由于一结点的存储位置（即下标）也就是它的编号，故结点间的逻辑关系可通过它们下标间的数值关系确定。
5.二叉树的遍历
由于二叉树的基本运算在链式存储结构上的实现比较简单，无需详加讨论。下面研究二叉树的一种较为复杂的重要运算———遍历及其在二叉链表上的实现。
遍历一棵二叉树就是按某种次序系统地“访问”二叉树上的所有结点，使每个结点恰好被“访问”一次。所谓“访问”一个结点，是指对该结点的数据域进行某种处理，处理的内容依具体问题而定，通常比较简单。遍历运算的关键在于访问结点的“次序”，这种次序应保证二叉树上的每个结点均被访问一次且仅一次。
由定义可知，一棵二叉树由三部分组成:根、左子树和右子树。因此对二叉树的遍历也可相应地分解成三项“子任务”:
①访问根根点;
②遍历左子树（即依次访问左子树上的全部结点）;③遍历右子树（即依次访问右子树上的全部结点）。
因为左、右子树都是二叉树（可以是空二叉树），对它们的遍历可以按上述方法继续分解，直到每棵子树均为空二叉树为止。由此可见，上述三项子任务之间的次序决定了遍历的次序。若以D、L、R分别表示这三项子任务，则人有六种可能的次序:DLR、LDR、LRD、DRL、RDL和RLD。通常限定“先左后右”，即子任务②在子任务③之前完成，这样就只剩下前三种次序，按这三种次序进行的遍历分别称为先根遍历（或前序遍历）、中根（或中序）遍历、后根（或后序）遍历。三种遍历方法的定义如下:
先根遍历 若需遍历的二叉树为空，执行空操作;否则，依次执行下列操作:
①访问根结点;
②先根遍历左子树;
③先根遍历右子树。
中根遍历 若需遍历的二叉树为空，执行空操作，否则，依次执行下列操作:
①中根遍历左子树;②访问根结点;③中根遍右子树。
后根遍历 若需遍历的二叉树为空，执行空操作，否则，依次执行下列操作:
①后根遍历左子树。②后根遍历右子树。③访问根结点。
显然，上述三种遍历方法的区别在于执行子任务“访问根结点”的“时机”不同;最先（最后、在中间）执行此子任务，则为先根（后根、中根）遍历。
按某种遍历方法遍历一棵二叉树，将得到该二叉树上所有结点的访问序列。
希望与更多计算机等级考试的网友交流，请进入计算机等级考试论坛
更多信息请访问：考试吧计算机等级考试栏目
