7.1.5树的基本运算树的运算主要分为三大类：第一类，寻找满足某种特定关系的节点，如寻找当前节点的双亲节点等：第二类，插入或删除某个节点，如在树的当前节点上插入一个新节点或删除当前节点的第个孩子节点等：第三类，遍历树中每个节点，这里着重介绍。21
21 7.1.5 树的基本运算 树的运算主要分为三大类： 第一类，寻找满足某种特定关系的节点，如寻找当前节 点的双亲节点等； 第二类，插入或删除某个节点，如在树的当前节点上插 入一个新节点或删除当前节点的第i个孩子节点等； 第三类，遍历树中每个节点，这里着重介绍
树的遍历树的遍历运算是指按某种方式访问树中的每一个节点且每一个节点只被访问一次有以下三种遍历方法：先根遍历后根遍历层次遍历注意：先根和后根遍历算法都是递归的。22
22 树的遍历运算是指按某种方式访问树中的每一个节点且每 一个节点只被访问一次。 有以下三种遍历方法： 树的遍历 先根遍历 后根遍历 层次遍历 注意：先根和后根遍历算法都是递归的
先根遍历：若树不空，则先访问根节点，然后依次先根遍历各棵子树后根遍历：若树不空，则先依次后根遍历各棵子树，然后访问根节点。按层次遍历：若树不空，则自上而下自左至右访问树中每个节点23
23 先根遍历: 若树不空，则先访问根节点，然后依次先根遍历各棵子树。 后根遍历: 若树不空，则先依次后根遍历各棵子树，然后访问根节点。 按层次遍历: 若树不空，则自上而下自左至右访问树中每个节点
先根遍历的顶点访问次序：ABEFCDGHIJK一后根遍历的顶点访问次序：FEFBCIJKHGDA层次遍历的顶点访问次序：ABCDEFGHIJK24
24 A B C D E F G H I J K 先根遍历的顶点访问次序： A B E F C D G H I J K 后根遍历的顶点访问次序： E F B C I J K H G D A 层次遍历的顶点访问次序： A B C D E F G H I J K
7.1.6树的存储结构1.双亲存储结构这种存储结构是一种顺序存储结构，用一组连续空间存储树的所有节点，同时在每个节点中附设一个伪指针指示其双亲节点的位置。0AB00C2Y0D42E2F56G2(b)(a)树的双亲存储结构示意图25
25 7.1.6 树的存储结构 1. 双亲存储结构 这种存储结构是一种顺序存储结构，用一组连续空间 存储树的所有节点，同时在每个节点中附设一个伪指针指 示其双亲节点的位置。 A B C D E F G A -1 B 0 C 0 D 0 E 2 F 2 G 2 0 1 2 3 4 5 6 (a) (b) 树的双亲存储结构示意图