第13章 树-浙江高中信息技术知识点

浙江高中技术培优算法（陶小波） 52 第十三章 树 1. 树是一种非线性的数据结构用它能很好的描述有分支和层次特性的数据集合 2. 树可以描述为由 n(n>=0)个节点（Node）构成的一个有限集合以及在该集合上 定义的一种节点关系。 3. 集合中的元素称为树的节点，n=0 的树称为空树；树中某个节点下面的所有节 点所构成的树称为该节点的子树。 4. 树的两个节点之间如果有一条边连接，那么称为这两个节点之间存在一条边； 对于一颗具有 n个节点的树，它由 n-1 条边。 5. 如下图：下图中的树中共有 13 个节点、12 条边、节点 B、G、H 构成节点 A 的一颗子树 图 4.1 6. 树的一个节点所拥有的子树个数称为该节点的度，最大的节点的度称为树的 度。如图 4.1，节点 A的度为 5，节点 B的度为 2，节点 I的度为 3，因此此树的 度为 5。 7. 在树形结构中，没有前驱的节点称为根节点，又称为开始节点（图 4.1 的 A 节点）。 8. 度为 0的节点称为叶子节点，又称为终端节点（图 4.1 的 G、H、C、D、K、L、 M、J、F） 9. 树中度不为 0的节点称为分支节点或非终端节点，除根节点外的分支节点统 称为内部节点（图 4.1 的 B、E、I 节点） 10. 在树形结构中，对于两个以边直接连接的节点，上端节点称为下端节点的父 节点或双亲节点。相应的下端节点称为上端节点的孩子节点。如图 4.1 所示，节 点 K、L、M都是节点 I的孩子节点。反过来，节点 I是节点 K、L、M的父节点， 节点 K、L、M是兄弟节点 11. 树中节点的层数从根开始计算，根的层数为 1，其余节点的层数等于其父节 点的层数加 1 12. 树中节点的最大层数称为树的高度或深度 13. 二叉树是一个具有 n(n>=0)个节点的有限集合；当 n=0 时，二叉树是一颗空 树；当 n!=0 是，则是一颗由根节点和两颗互不相交的分别称为这个根节点的左 子树和右子树组成的二叉树，由于左、右子树也是二叉树，因此子树也可以是空 树。 14 二叉树的分类如下图：从左到右分别是为 1.空二叉树、2.只有根节点的单点 树、3.只有根节点和左子树、4.只有根节点和右节点、5.有根节点和左右子树 浙江高中技术培优算法（陶小波） 53 14. 完全二叉树:这一类二叉树至多只有最下面两层中的节点度数小于 2，且最下 面一层的叶子节点都依次排列在该层的最左边位置。如下图： 15. 二叉树的性质如下： 16. 二叉树的遍历：二叉树的遍历根据根节点的访问顺序，可以分为 前序遍历、 中序遍历、后序遍历。 17. 前序遍历规则：先访问根节点，再访问左子树，最后访问右子树。如下图 4.2： 最后访问顺序为：A-B-D-H-E-C-F-I-G-J-K 18. 中序遍历规则：先访问左子树，再访问根节点，最后访问右子树。如下图 4.3： 最后访问顺序为：D-H-B-E-A-I-F-C-J-G-K 19. 后序遍历规则：先访问左子树，再访问右子树，最后访问根节点。如下图 4.4： 最后访问顺序为：H-D-E-B-I-F-J-K-G-C-A 可以根据前序遍历，中序遍历推算出唯一的后序遍历、可以根据中序遍历，后序 遍历推算出唯一的前序遍历、无法根据前序遍历，后序遍历推算出唯一的中序遍 历（或者说无法根据前序遍历、后序遍历推算中序遍历） 浙江高中技术培优算法（陶小波） 54 图 4.2 图 4.3 图 4.4 （一）逆波兰表达式 逆波兰式是一种将待计算量写在前, 把运算符写在后（通常是两数之后）的计算 式，比如： 中序表达式 逆波兰表达式 A + B A B + A * B A B * A +B * C A B C * + A * ( B + C ) A B C + * 逆波兰表达式可以通过栈、叉树等数据结构存储，其中二叉树用的较多，通过二 叉树存储 通过前序、中序、后序遍历中的其中一种方法，可以遍历出一个表达式。 例如：有如下二叉树存储的逆波兰表达式 a+(b-c) 当前二叉树的中序遍历为 a+(b-c),【注意：b-c 外的括弧，是因为他们与 a不在 同一子树所以增加】 浙江高中技术培优算法（陶小波） 55 逆波兰表达式代码 def nbl(tokens): s = [] operators = ['+', '-', '*', '/'] for token in tokens: if token not in operators: s.append(int(token)) else: num2 = s.pop() num1 = s.pop() if token == '+': s.append(num1 + num2) elif token == '-': s.append(num1 - num2) elif token == '*': s.append(num1 * num2) elif token == '/': s.append(int(num1 / num2)) return s[0] print(nbl(["2", "1", "+", "3", "*"])) # 输出: 浙江高中技术培优算法（陶小波） 56 （三）根据前序遍历、中序遍历推整个二叉树 前序遍历为：A-B-D-H-E-C-F-I-G-J-K 中序遍历为：D-H-B-E-A-I-F-C-J-G-K （本文根据前序遍历从前往后逐位判定元素位置） 第一步：判定根节点【因为前序遍历的遍历顺序为根左右，所以可以判定 A为整 棵树的根节点】，可以绘制如下二叉树图 第二步：判定 A的左右子树范围【因为中序遍历的遍历顺序为左根右，所以可以 判定 DHBE 是 A 的左子树，IFCJGK 为 A 的右子树】 第三步：判定 B 的位置【前序遍历的顺序是根左右，观察前序遍历可以得到 B 在 A的右边第一个位置，所以可以初步判定 B是 A的左子树，中序遍历的顺序是 左根右，观察中序遍历可以得到 B在 A的左边，所以可以判定 B是 A的左子树】， 可以绘制如下二叉树图 第四步：判定 D 的位置【前序遍历的顺序是根左右，观察前序遍历可以得到 D 在 B的右边第一个位置，所以可以初步判定 D是 B的左子树，中序遍历的顺序是 左根右，观察中序遍历可以得到 D在 B的左边，所以可以判定 D是 B的左子树】， 可以绘制如下二叉树图 浙江高中技术培优算法（陶小波） 57 第五步：判定 H 的位置【前序遍历的顺序是根左右，观察前序遍历可以得到 H 在 D的右边第一个位置，所以可以初步判定 H是 D的右子树，中序遍历的顺序是 左根右，观察中序遍历可以得到 H在 D的右边第一个位置，所以可以判定 H是 D 的右子树】，可以绘制如下二叉树图 第六步：判定 E的位置【基于前五步推出的结果，因为中序遍历 E在 B的右边， 所以可以判定 E是 B的右子树】，可以绘制如下二叉树图 第七步：判定 C的位置【观察中序遍历可以得到 A是根节点，C在 A的右边，据 此可以判定 C是 A的右边子树，又根据前序遍历 C在右边子树的第一个位置，因 为前序遍历是根左右，所以可以判定 C是 A的右子树】，可以绘制如下二叉树图 浙江高中技术培优算法（陶小波） 58 第八步：判定 F 的位置【前序遍历的顺序是根左右，观察前序遍历可以得到 F 在 C的右边第一个，可以初步判定 F是 C的左子树，中序遍历的顺序是左根右， 观察中序遍历可以得到 F在 C的左边，所以可以判定 F是 C的左子树】可以绘制 如下二叉树图 第九步：判定 I 的位置【前序遍历的顺序是根左右，观察前序遍历可以得到 I 在 F的右边第一个位置，可以初步判定 I是 F的左子树，中序遍历的顺序是左根 右，观察中序遍历可以得到 I在 F的左边第一个位置，所以可以判定 I是 F的左 子树】可以绘制如下二叉树图 第十步：判定 G的位置【观察前序遍历 G在 I的右边第一个位置，但是中序遍历 G和 I并不是相邻关系，所以可以判定 G并不是 I的子树，此时根据遍历原理， 需要去判定 G是不是 C的子树，观察中序遍历可得 JGK 都在 C的右边，说明 JGK 都是 C的右子树，又根据前序遍历和中序遍历的顺序，可以得到 G是 JGK 的根节 点也是 C的右子树】，可以绘制如下二叉树图 浙江高中技术培优算法（陶小波） 59 第十一步：判定 J的位置【根据第十步的结果，因为中序遍历 J在 G的左边，说 明 J是 G的左子树】可以绘制如下二叉树图 第十二步：判定 K的位置【根据第十步的结果，因为中序遍历 K在 G的右边，说 明 K是 G的右子树】，可以绘制如下二叉树图 浙江高中技术培优算法（陶小波） 60 （三）根据中序遍历、后序遍历推整个二叉树 中序遍历为：D-H-B-E-A-I-F-C-J-G-K 后序遍历为：H-D-E-B-I-F-J-K-G-C-A （本文根据后序遍历从后往前逐位判定元素位置） 第一步：判定根节点【因为后序遍历的遍历顺序为左右根，所以可以判定 A 为整棵树的 根节点】，可以绘制如下二叉树图 第二步：判定 A 的左右子树范围【因为中序遍历的遍历顺序为左根右，所以可以判定 DHBE 是 A 的左子树，IFCJGK 为 A 的右子树】 第三步：判定 C的位置【后序遍历的顺序是左右根，观察后序遍历可以得到 C 在 A 的左边第 一个位置，所以可以初步判定 C 是 A 的右子树，中序遍历的顺序是左根右，观察中序遍历可 以得到 C 在 A 的右边，所以可以判定 C是 A的右子树】可以绘制如下二叉树图 第四步：判定 G的位置【后序遍历的顺序是左右根，观察后序遍历可以得到 G 在 C 的左边第 一个位置，所以可以初步判定 G 是 C 的右子树，中序遍历的顺序是左根右，观察中序遍历可 以得到 G 在 C 的右边，所以可以判定 G是 C的右子树】可以绘制如下二叉树图 浙江高中技术培优算法（陶小波） 61 第五步：判定 K的位置【后序遍历的顺序是左右根，观察后序遍历可以得到 K 在 G 的左边第 一个位置，所以可以初步判定 K 是 G 的右子树，中序遍历的顺序是左根右，观察中序遍历可 以得到 K 在 G 的右边，所以可以判定 K是 G的右子树】可以绘制如下二叉树图 第六步：判定 J的位置【后序遍历的顺序是左右根，观察后序遍历可以得到 J 在 K 的左边第 一个位置，且根据上一步推的 K 是 G 的右子树，此时可以初步判定 J 是 G 的左子树，又因为 中序遍历的顺序是左根右，观察中序遍历可以得到 J 在 G 的左边，所以可以判定 J 是 G 的左 子树】可以绘制如下二叉树图 第七步：判定 F 的位置【根据前六步的结果，可以得到 F只能是 C的左子树（观察中序遍历， 因为 F在 C的左边第一个位置）】可以绘制如下二叉树图 浙江高中技术培优算法（陶小波） 62 第八步：判定 I的位置【后序遍历的顺序是左右根，观察后序遍历可以得到 I 在 F 的左边第 一个位置，所以可以初步判定 I 是 F 的左子树，中序遍历的顺序是左根右，观察中序遍历可 以得到 I 在 F 的左边第一个位置，所以可以判定 I 是 F 的左子树】可以绘制如下二叉树图 第九步：判定 B的位置【中序遍历的顺序是左根右，已知 A是根节点，所以 B 必定是 A 的左 边子树，后序遍历中 B 在左边子树的最后一个位置，因为后序遍历的顺序是左右根，所以可 以判定 B 是左边子树的根，也就是 A 的左子树】可以绘制如下二叉树图 第十步：判定 E的位置【中序遍历的顺序是左根右，观察中序遍历可以得到 E 在 B 的右边第 一个位置，因为上一步推的 B是根节点，所以可以初步判定 E 是 B 的右子树，后序遍历的顺 序是左右根，观察后序遍历可以得到 E 在 B 的左边第一个位置，所以可以判定 E 是 B 的右子 树】可以绘制如下二叉树图 浙江高中技术培优算法（陶小波） 63 第十一步：判定 D 的位置【后序遍历的顺序是左右根，观察后序遍历可以得到 D 在 E 的左边 第一个位置，因为上一步推的 E 是右节点，所以可以初步判定 D 是 B 的左子树，中序遍历的 顺序是左根右，观察中序遍历可以得到 D 在 B 的左边，所以可以判定 D 是 B 的左子树】可以 绘制如下二叉树图 第十二步：判定 H的位置【中序遍历的顺序是左根右，因为 B 的子树已经满了，所以只能是 B的子树的子树，观察后序遍历，因为 H 在 D 的右边第一个位置，所以可以初步判定 H 是 D 的右子树，中序遍历 H在 D的右边，根据中序遍历的原理，可以判定 H 是 D 的右子树】可以 绘制如下二叉树图