树形结构

树形结构广泛存在于客观世界中，如族谱、目录、社会组织、各种事物的分类等，都可用树形结构表示。树形结构在计算机领域应用广泛，如操作系统中的目录结构；源程序编译时，可用树表示源程序的语法结构；在数据库系统中，树结构也是信息的重要组织形式之一。简单地说，一切具有层次关系或包含关系的问题都可用树形结构描述。

▶1.树的基本概念和特征

图看上去像一棵倒置的树，“树”由此得名。图示法表示树形结构时，通常根在上，叶在下。树的箭头方向总是从上到下，即从父节点指向子节点；因此，可以简单地用连线代替箭头，这是画树形结构时的约定。

一棵树由n(n>0)个元素组成的有限集合，其中每个元素称为节点：树有一个特定的根节点(root);除根节点外，其余节点被分成m(m>0)个互不相交的子集(子树)。
树上任一节点所拥有子树的数量称为该节点的度。图4-26中节点C的度为3,节点B的度为1,节点D、H、F、1、J的度为0。度为0的节点称为叶子或终端节点，度大于0的节点称为非终端节点或分支点。树中节点B是节点D的直接前趋，因此称B为D的父节点，称D为B的孩子或子节点。与父节点相回的节点互称为兄弟，如E、F、G是兄弟节点。一棵树或子树上的任何节点(不包括根本身)称为根的子孙。树中节点的层数(或深度)从根开始算起：根的层数为1,其余节点的层数为双亲节点层数加1。在一棵树中，如果从一个节点出发，按层次自上而下沿着一个个树枝到达另一个节点，则称它们之间存在一条路径，路径的长度等于路径上的节点数减1。森林指若干棵互不相交树的集合，实际上，一棵树去掉根节点后就成为森林。
树是一种“分支层次”结构。所谓“分支”是指树中任一节点的子孙，可以它们所在子树的不同划分成不同的“分支”;所谓“层次”是指树上所有节点，可以按层划分成不同的“层次”。在实际应用中，树中的一个节点可用来存储实际问题中的一个数据元素，而节点之间的逻辑关系往往用来表示数据元素之间的某种重要关系。
例：在3D游戏中，经常把游戏场景组织在一个树结构中，这是为了可以快速判断出游戏的可视区域。其算法思想是：如果当前节点完全不可见，那么它的所有子节点也必然完全不可见；如果当前节点完全可见，那么它的所有子结点也必然完全可见；如果当前节点部分可见，就必须依次判断它的子节点，这是一个递归的算法。
树的基本运算包括建树(CREATE)、树遍历、剪枝(DELETE)、求根(ROOT)、求双亲(PARENT)、求孩子(CHILD)等操作。

▶2.二叉树的存储结构

1)二叉树

二叉树的特点是除了叶以外的节点都有2个子树，如图4-27所示。二叉树的2个子树有左右之分，颠倒左右就是不一样的二叉树了，所以二叉树左右不能随便颠倒。由此还可以推出三叉树、四叉树、五叉树、六叉树等。

2)二叉树的链表存储结构

二叉树有两类存储结构：链式存储结构和顺序存储结构。最常用的是二叉树节点链表存储结构(简称为二叉树链表)。

链表存储结构中，Data称为数据域，用于存储节点中的数据元素，Lchid称为左孩子域，用于存放指向本节点左孩子的指针《简称为左指针);与此类似，Rchid称为右指针；每个二叉树链表还有一个指向根节点的指针，该指针称为根指针。根指针具有标识二叉树链表的作用，对二叉树链表的访问从根指针开始。值得注意的是，二叉树链表中每个存储节点的每个指针域必须有一个值，这个值
或者是指向该节点一个孩子的指针，或者是空标志(null或^)。

二叉树的多数基本运算(如求根、求左右子树等)很容易实现。但求双亲运算(PARENT)比较麻烦，而且时间性能不高。如果在实际问题中需要经常做求双亲运算，则采用二叉树链表为存储结构显然不合适。这时可以采用三叉树链表作为存储结构。

3)二叉树的顺序存储结构

程序设计语言中并没有“树”这种数据类型，因此二叉树的顺序存储结构由一维数组构成，二叉树的节点按次序分别存入数组的各个单元。一维数组的下标就是节点位置指针，每个节点中有一个指向各自父亲节点的数组下标。显然，节点的存储次序很重要，存储次序应能反映节点之间的逻辑关系(父子关系),否则二叉树的运算就难以实现。为了节省查询时间，可以规定儿子的数组下标值大于父亲的数组下标值，而兄弟节点的数组下标值随兄弟从左到右递增。

在顺序存储结构中，由于节点的存储位置就是它的编号(即下标),因此节点之间可通过它们的下标确定关系。如果二叉树不是完全二叉树，就必须将其转化为完全二叉树。可通过在二叉树“残缺”位置上增设“虚节点”的方法，将其转化成一棵完全二叉树。然后对得到的完全二叉树重新按层编号，然后再按编号将各节点存入数组，各个“虚节点”在数组中用空标志△表示。经过变换的顺序存储结构，可以用完全二叉树类似的方法实现二叉树数据结构的基本运算。显然，上述方法解决了非完全二叉树的顺序存储问题，但同时也造成了存储空间的浪费。可见这是一种以空间换取性能的计算思维方式。

▶3.二叉树的遍历

树的遍历是指沿着某条搜索路线，依次对树中每个节点访问一次且仅访问一次。树的遍历方法有广度优先遍历和深度优先遍历。二叉树访问一个节点就是对该节点的数据域进行某种处理，处理内容依具体问题而定。
二叉树由三部分组成：根(N)、左子树(L)和右子树(R)。遍历运算的关键在于访问节点的“次序”,二叉树的遍历可分解成三项子任务：访问根节点；遍历左子树(依次访问左子树的全部节点);遍历右子树(依次访问右子树的全部节点)。树的遍历方法主要有“广度优先遍历”和“深度优先遍历”。通常限定为“先左后右”,这样就减少了一些遍历方法。树的深度优先遍历又可分为前序遍历(NLR,根一左—右),后序遍历(LRN,左—右一根)和中序遍历(LNR,左—根一右),其中中序遍历只有对二叉树才有意义。
A)