二叉树全集

你提供的代码和解释涵盖了二叉树的几个关键概念，包括如何从遍历序列中重建二叉树以及如何检查二叉树是否为完全二叉树。以下是对这些内容的详细解释：

1. 从前序遍历和中序遍历重建二叉树

给定前序遍历和中序遍历序列，可以唯一地重建一颗二叉树。前序遍历的第一个元素是根节点，然后根据根节点在中序遍历中的位置，可以将中序遍历分为左子树和右子树。

以下是实现该功能的代码：

#include <iostream> #include <vector> struct BinaryTreeNode { int value; BinaryTreeNode* left; BinaryTreeNode* right; BinaryTreeNode(int x) : value(x), left(NULL), right(NULL) {} }; BinaryTreeNode* buildTree(const std::vector<int>& preorder, const std::vector<int>& inorder, int& preIndex, int inStart, int inEnd) { if (inStart > inEnd) return NULL; BinaryTreeNode* root = new BinaryTreeNode(preorder[preIndex++]); int inIndex; for (int i = inStart; i <= inEnd; ++i) { if (inorder[i] == root->value) { inIndex = i; break; } } root->left = buildTree(preorder, inorder, preIndex, inStart, inIndex - 1); root->right = buildTree(preorder, inorder, preIndex, inIndex + 1, inEnd); return root; } BinaryTreeNode* rebuildTree(const std::vector<int>& preorder, const std::vector<int>& inorder) { int preIndex = 0; return buildTree(preorder, inorder, preIndex, 0, inorder.size() - 1); } void printInorder(BinaryTreeNode* node) { if (node == NULL) return; printInorder(node->left); std::cout << node->value << " "; printInorder(node->right); } 

2. 检查二叉树是否为完全二叉树

完全二叉树的特点是：除了最后一层外，其他所有层的节点都是满的，并且最后一层的所有节点都尽可能地靠左。

以下是实现该功能的代码：

#include <iostream> #include <queue> bool isCompleteBinaryTree(BinaryTreeNode* pRoot) { if (pRoot == NULL) return false; std::queue<BinaryTreeNode*> q; q.push(pRoot); bool mustHaveNoChild = false; while (!q.empty()) { BinaryTreeNode* pNode = q.front(); q.pop(); if (mustHaveNoChild) { if (pNode->left != NULL || pNode->right != NULL) return false; } else { if (pNode->left != NULL && pNode->right != NULL) { q.push(pNode->left); q.push(pNode->right); } else if (pNode->left != NULL && pNode->right == NULL) { mustHaveNoChild = true; q.push(pNode->left); } else if (pNode->left == NULL && pNode->right != NULL) { return false; } else { mustHaveNoChild = true; } } } return true; } 

总结

• 前序遍历和中序遍历重建二叉树：通过递归方法，根据前序遍历的第一个元素作为根节点，并在中序遍历中找到该节点的位置，然后递归构建左子树和右子树。
• 检查完全二叉树：通过层次遍历（广度优先搜索），如果某个节点有左子树但没有右子树，则后续的节点必须是叶节点。

这些方法在处理二叉树问题时非常有用，可以帮助我们理解和操作二叉树的各种属性。