首页判断完全二叉树【问题描述】给定一棵树的前序遍历和中序遍历，判断该树是否为完全二叉树【输入形式】一棵树的前序遍历和中序遍历写出C++代码,能直接运行

判断完全二叉树【问题描述】给定一棵树的前序遍历和中序遍历，判断该树是否为完全二叉树【输入形式】一棵树的前序遍历和中序遍历写出C++代码,能直接运行

时间: 2024-12-24 16:16:40 浏览: 50

判断一棵树是否为完全二叉树，可以利用前序遍历（根节点 -> 左子树 -> 右子树）和中序遍历（左子树 -> 根节点 -> 右子树）的特点。完全二叉树的特点是除了最后一层外，每一层都是满的，并且所有叶子节点都在最右边。以下是一个简单的C++函数，用于判断给定的前序遍历和中序遍历数组是否对应于一棵完全二叉树： ```cpp #include <vector> using namespace std; // 假设前序遍历的第一个元素为根节点 bool isCompleteBinaryTree(vector<int>& preOrder, vector<int>& inOrder) { int root = preOrder[0], rootIndex = 0; // 中序遍历查找根节点的位置 for (int i = 0; i < inOrder.size(); ++i) { if (inOrder[i] == root) { rootIndex = i; break; } } // 比较前序遍历和中序遍历在根节点之后的部分 int i = 0, j = rootIndex + 1; while (j < inOrder.size() && preOrder[i + 1] != inOrder[j]) { if (preOrder[i + 1] > inOrder[j]) { // 如果前序中的下一个元素大于当前中序元素，说明右子树未完成 return false; } else { // 移动到下一个中序元素 j++; } i++; } // 如果遍历完前序，而右子树尚未处理，则为完全二叉树 if (i == inOrder.size()) { return true; } else { // 如果剩余前序元素少于剩余中序元素，则不是完全二叉树 return preOrder.size() - (rootIndex + 1) == j - (rootIndex + 1); } } // 示例用法 int main() { vector<int> preOrder = {1, 2, 4, 5, 3}; vector<int> inOrder = {4, 2, 5, 1, 3}; if (isCompleteBinaryTree(preOrder, inOrder)) { cout << "The tree is a complete binary tree." << endl; } else { cout << "The tree is not a complete binary tree." << endl; } return 0; } ```

阅读全文