二叉树与完全二叉树的概念及遍历解析

"第6章 树和二叉树答案1" 本章主要涉及树和二叉树的相关概念，包括选择题、判断题和填空题的答案解析。以下是相关知识点的详细说明： 1. **二叉树的性质**：二叉树节点的公式n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1，其中n0、n1和n2分别代表度为0、1和2的节点数量。对于完全二叉树，n1只能取0或1。 2. **完全二叉树与节点数量**：如果一个二叉树有1001个节点，且是完全二叉树，那么根据上述公式，n1=0，因此节点数n=501。 3. **二叉树的遍历序列**：前序遍历是"根左右"，后序遍历是"左右根"。如果前序和后序序列相反，那么树只能是单支树，即只有一个叶子节点。 4. **线索二叉树**：线索二叉树是通过在二叉树的空链域中添加线索，便于遍历。一个有n个节点的二叉树有n+1个空链域可以用来存储线索。 5. **遍历的唯一性**：只有在确定了特定的遍历顺序（如前序、中序、后序或层次遍历）后，遍历结果才是唯一的。 6. **二叉树的遍历策略**：对于只有一侧子树的二叉树，如只有左子树的二叉树，遍历过程可以不需要栈来辅助。 7. **节点编号与子节点关系**：在完全二叉树中，编号为i的节点，其左子节点编号为2i（如果2i≤n），右子节点编号为2i+1（如果2i+1≤n）。 8. **中序遍历的前驱与后继**：在二叉树中，一个节点的中序前驱是其左子树上按中序遍历的最右边的节点；中序后继是其右子树上按中序遍历的最左边的节点。对于有左右子树的节点，前驱线索指向祖先，后继线索指向祖先。 9. **顺序存储二叉树**：在顺序存储二叉树时，应按照完全二叉树的顺序排列，对于非完全二叉树，需要添加“虚结点”。 10. **结点在同一层的条件**：如果两个结点i和j的顺序存储下标分别为s和t，它们在同一层的条件是log2s=log2t，这意味着它们在树的高度上是相同的。 11. **平衡因子**：在平衡二叉树中，平衡因子是左右子树高度的差，用于判断树是否平衡。 12. **高度计算**：对于满二叉树，第k层有2^(k-1)个节点，树的高度H可以通过公式H=log2N+1计算，其中N是树的节点总数。 13. **插入操作**：在二叉树中，新插入的节点通常作为叶子节点。 以上就是关于二叉树和树的一些基本知识点，包括节点数量的计算、遍历序列的特性、线索二叉树的构建、节点间的关联以及树的高度计算等。这些知识点是理解并操作二叉树的基础。