十：树及其应用.PPTVIP

Const m=树中结点数上限； Type node=record {结点类型} data：datatype； {数据值} prt，lch，rch：integer； {父结点、左儿子、右儿子编号} end； treetype=array[1‥m] of node； {二叉树的顺序表类型} Var Tree：treetype； {二叉树} 2、链式存储结构 动态数据结构（指针）。由于二叉树中每个结点通常包括数据元素和两个分支。因此二叉树对应的二重链表中每个结点应有三个域： ⑴值域： data ⑵左指针域： lch ⑶右指针域： rch 这种链表也称为二叉链表。二叉链表头指针bt指向二叉树的根结点 例如用下图（b）所示的二叉链表存储二叉树（下图（a）） Type bitrpetr=↑bnode； {结点指针类型} benode=record {结点类型} data：datatype； {值域} lch，rch：bitreptr； {左指针域和右指针域} end； Var bt： bitreptr； {头指针} 三、二叉树的遍历(访问) 所谓二叉树的遍历是指按照一定的规律不重复地访问二叉树中的每一个结点。 如果用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，则对二叉树的遍历可以有下列六种（3!=6）组合： LDR、 LRD、 DLR、 DRL、RDL、 RLD 若再限定先左后右的次序，则只剩下三种组合 DLR、LDR、 LRD 这三种遍历规则分别称为先（前）序遍历、中序遍历和后序遍历（以根为标准）。 1、前（根）序遍历： DLR 前序遍历的规则如下： 若二叉树为空，则退出。否则 ⑴访问处理根结点； ⑵前序遍历左子树； ⑶前序遍历右子树； a b d e h i c f g 2、中序遍历： LDR 中序遍历的规则如下： 若二叉树为空，则退出；否则 ⑴中序遍历左子树； ⑵访问处理根结点； ⑶中序遍历右子树； 若中序遍历上图中的二叉树，可以得到如下的中序序列： d b h e i a f c g 3、后序遍历： LRD 后序遍历的规则如下： 若二叉树为空，则退出；否则 ⑴后序遍历左子树； ⑵后序遍历右子树； ⑶访问处理根结点； 若后序遍历上图中的二叉树，可以得到如下的后序序列 d h i e b f g c a 2）、写出二叉树后序遍历序列 1）、对二叉树从1进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的 编号，则可以采取[ ]次序的遍历方法。 A 先序 B中序 C后序 D从根开始的层次 1、编程实现：二叉树的遍历（tree1.pas） 建立二叉树，然后实现：输出先序遍历、中序遍历、后序遍历的结果。 输入： 第一行：结点个数n。 以下行：每行3个数，第一个是父亲，后两个依次为左右孩子。 输出：根、先中后序遍历结果。 样例输入： 8 1 2 4 2 0 0 4 8 0 3 1 5 5 6 0 6 0 7 8 0 0 7 0 0 样例输出： 3 3 1 2 4 8 5 6 7 2 1 8 4 3 6 7 5 2 8 4 1 7 6 5 3 const maxn=100; type