🏷️ 知识点：树转化为二叉树

若将一棵树 T 转化为对应的二又树 BT，则下列对 BT 的遍历中，其遍历序列与 T 的后根遍历序列相同的是（ ）。

树和二叉树的转换

A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历

[tag_link]

正确答案：B

本第一步，需要知道如何将一棵 树转化为二叉树：对于每一个结点，第一个孩子结点放左子树，其余孩子结点（即第一个孩子结点的兄弟结点）放在第一个孩子结点的右子树，其余的孩子结点再依次放在右子树的右子树，依次类推。第二步，需要知道选项中的四种遍历方式先序遍历：该结点，左子树，右子树中序遍历：左子树，该结点，右子树后序遍历：左子树，右子树，该节点层次遍历：队列实现前 3 种遍历方式，左子树都是先于右子树，“先”、“中”、“后”指的是访问该结点的次序，对于上图，我们发现，对树的后序遍历与对二叉树的中序遍历相同，选 B。

已知一棵有 2011 个结点的树，其叶结点个数为 116，该树对应的二叉树中无右孩子的结点个数是（ ）。

树的概念

A. 115

B. 116

C. 1895

D. 1896

[tag_link]

正确答案：D

树转化为二叉树 时，树中每一个分支结点的所有子结点中的最右子结点无右孩子，根结点转换后也没有右孩子，因此，对应的二叉树中无右孩子的结点个数＝分支结点数+1 = 2011-116+1 = 1896。通常本题应采用特殊法解，设题意中的树是如右图所示的结构，则对应的二叉树中仅有前 115 个叶结点有右孩子，故无右孩子的结点个数 = 2011-115 = 1896。