2.后根遍历 后根遍历过程为: (1)按照从左到右的次序后根遍历根结点的每一棵子树; (2)访问根结点。 E(((① EFBGCMHIJDA
2. 后根遍历 后根遍历过程为： (1)按照从左到右的次序后根遍历根结点的每一棵子树； (2)访问根结点。 A B C D E F G H I J M E F B G C M H I J D A
7.1.6树的存储结构 工.双亲存结构 这种存储结构是一种顺序存储结构,用一组连续空间存储 树的所有结点同时在每个结点中附设一个伪指针指示其双 亲结点的位置。 0a-1 1 b 00 3d1 d 5f4 伪指针
7.1.6 树的存储结构 1. 双亲存储结构 这种存储结构是一种顺序存储结构,用一组连续空间存储 树的所有结点,同时在每个结点中附设一个伪指针指示其双 亲结点的位置。 a b c d e f g 6 g 4 5 f 4 4 e 1 3 d 1 2 c 0 1 b 0 0 a -1 伪指针
找某节点的双亲:伪指针给出 找某节点的孩子:需扫描整个表格 b 0123 d abcdef 1001144 伪指针 18
18 a b c d e f g 6 g 4 5 f 4 4 e 1 3 d 1 2 c 0 1 b 0 0 a -1 伪指针 找某节点的双亲: 找某节点的孩子：需扫描整个表格 伪指针给出
2.孩子链存结构 孩子链存储结构可按树的度即树中所有结点度 的最大值)设计结点的孩子结点指针域个数。 b)(c d b ∧∧ d ∧∧∧ ∧A|∧ 较浪费空间 特点难查找结点的双亲 19
19 2. 孩子链存储结构 孩子链存储结构可按树的度(即树中所有结点度 的最大值)设计结点的孩子结点指针域个数。 a b c d e a b ^ ^ c ^ ^ ^ d ^ ^ ^ e ^ ^ ^ 较浪费空间 特点:难查找结点的双亲
3.孩子兄弟链结 孩子兄弟链存储结构是为每个结点设计三个域 一个数据元素成一个指向复第一个孩子结点指针域 一个指向复下一个兄弟结点指。 a A bAc「} b d dA 优点:有利于将一般的树转化为二叉树(后 面将详细讨论) 不足:查找双亲结点难 20
20 3. 孩子兄弟链存储结构 孩子兄弟链存储结构是为每个结点设计三个域： 一个数据元素域,一个指向其第一个孩子结点指针域, 一个指向其下一个兄弟结点指针域。 a ^ b ^ c ^ e ^ ^ d ^ a b c d e 优点:有利于将一般的树转化为二叉树(后 面将详细讨论) 不足:查找双亲结点难