关于树的一些题

判断题

---

任何二叉搜索树中同一层的结点从左到右是有序的（从小到大）。 T

---

在一棵二叉搜索树上查找63，序列39、101、25、80、70、59、63是一种可能的查找时的结点值比较序列。 F

---

二叉搜索树的查找和折半查找的时间复杂度相同。 F

---

任何AVL树的中序遍历结果是有序的（从小到大）。T

---

将1、2、3、4、5、6顺序插入初始为空的AVL树中，当完成这6个元素的插入后，该AVL树的先序遍历结果是：4、2、1、3、5、6。 T

做这道题时应该先将这棵树还原出来，记住平衡二叉树也是二叉搜索树，要满足二叉搜索树的特点. 还原这棵树时，看看是否满足平衡二叉树的性质（即左右子树高度差的绝对值小于等于1）,如果不满足需要进行单旋 插入时满足二叉搜索树的性质（即根节点所有左子树的值小于跟结点的值，根节点所有右子树的值大于跟结点的值）

---

对AVL树中的任一结点，其左、右子树的高度一定是一样的。F

---

若一棵平衡二叉树的所有非叶结点的平衡因子都是0，则其必为完美二叉树。T

---

任何最小堆的前序遍历结果是有序的（从小到大）。F

---

任何最小堆中从根结点到任一叶结点路径上的所有结点是有序的（从小到大）。T

---

对N（≥2）个权值均不相同的字符构造哈夫曼树，则树中任一非叶结点的权值一定不小于下一层任一结点的权值. T

---

选择题

---

---

这道题最重要的是将这棵平衡二叉树还原，在还原过程中遵守二叉搜索树和平衡二叉树的性质，在本题中使用了一次RR单旋和一次RL单旋。这道题与上面判断题第五题相似

---

---

---

---

---

---

---

---

2、二叉树的度可能为2，也可能不为2，例如只有根结点的二叉树度为0，斜二叉树度为1 3、二叉树的左右子树有些情况下可以互换，有些情况下不可以互换，例如堆，二叉搜索树，平衡二叉树等

---

完成一个元素最大堆插入过程，只需要让新增结点顺着父结点到根结点的路径比较，然后按从大到小排序即可

---

每条边对应一个节点,只有根节点没有相应的边.先计算边数，根据 总结点数=边数＋1,除去度为1,2,3,和4的结点，剩下的就是叶子节点 边数为：n=1*4+2*2+3*1+4*1=15个 结点数：m=n+1=16个 叶结点数：16-4-2-1-1=8个

---

边数：2*4+3*2+4*1=18 总结点：18+1=19 叶结点：19-4-2-1=12、

---