使用C++,根据二叉树的先序遍历序列建立二叉树,完善代码函数tree.CreateBinaryTree(); 例如:根据先序遍历序列ABDG#L##HM###EIN##O###C#FJ##K##建立二叉树,其中,#表示空树。
时间: 2024-10-18 12:13:13 浏览: 8
要实现 `CreateBinaryTree` 函数,可以根据给定的先序遍历序列构建二叉树。以下是该函数的实现:
```cpp
#include <iostream>
#include <queue>
using namespace std;
// 假设 BTNode 是一个定义好的二叉树节点类
template <class T>
class BTNode {
public:
T data;
BTNode<T> *left, *right;
BTNode(T d = T(), BTNode<T> *l = nullptr, BTNode<T> *r = nullptr) : data(d), left(l), right(r) {}
};
// 假设 BinaryTree 是一个定义好的二叉树类
template <class T>
class BinaryTree {
private:
BTNode<T> *root;
public:
BinaryTree() : root(nullptr) {}
~BinaryTree() { Destroy(root); }
void CreateBinaryTree();
void PreOrder(void (*visit)(const T&)) const;
void InOrder(void (*visit)(const T&)) const;
void PostOrder(void (*visit)(const T&)) const;
void LevelOrder(void (*visit)(const T&)) const;
int Width() const;
int NodeCount() const;
private:
void Destroy(BTNode<T> *&node);
void PreOrder(BTNode<T> *node, void (*visit)(const T&)) const;
void InOrder(BTNode<T> *node, void (*visit)(const T&)) const;
void PostOrder(BTNode<T> *node, void (*visit)(const T&)) const;
int Width(BTNode<T> *node) const;
int NodeCount(BTNode<T> *node) const;
};
template <class T>
void BinaryTree<T>::CreateBinaryTree() {
queue<BTNode<T>*> q;
char ch;
cin >> ch;
if (ch == '#') {
root = nullptr;
} else {
root = new BTNode<T>(ch);
q.push(root);
}
while (!q.empty()) {
BTNode<T> *p = q.front();
q.pop();
cin >> ch;
if (ch != '#') {
p->left = new BTNode<T>(ch);
q.push(p->left);
}
cin >> ch;
if (ch != '#') {
p->right = new BTNode<T>(ch);
q.push(p->right);
}
}
}
template <class T>
void BinaryTree<T>::PreOrder(void (*visit)(const T&)) const {
PreOrder(root, visit);
}
template <class T>
void BinaryTree<T>::InOrder(void (*visit)(const T&)) const {
InOrder(root, visit);
}
template <class T>
void BinaryTree<T>::PostOrder(void (*visit)(const T&)) const {
PostOrder(root, visit);
}
template <class T>
void BinaryTree<T>::LevelOrder(void (*visit)(const T&)) const {
if (root == nullptr) return;
queue<BTNode<T>*> q;
q.push(root);
while (!q.empty()) {
BTNode<T> *p = q.front();
q.pop();
visit(p->data);
if (p->left) q.push(p->left);
if (p->right) q.push(p->right);
}
}
template <class T>
int BinaryTree<T>::Width() const {
return Width(root);
}
template <class T>
int BinaryTree<T>::NodeCount() const {
return NodeCount(root);
}
template <class T>
void BinaryTree<T>::Destroy(BTNode<T> *&node) {
if (node) {
Destroy(node->left);
Destroy(node->right);
delete node;
node = nullptr;
}
}
template <class T>
void BinaryTree<T>::PreOrder(BTNode<T> *node, void (*visit)(const T&)) const {
if (node) {
visit(node->data);
PreOrder(node->left, visit);
PreOrder(node->right, visit);
}
}
template <class T>
void BinaryTree<T>::InOrder(BTNode<T> *node, void (*visit)(const T&)) const {
if (node) {
InOrder(node->left, visit);
visit(node->data);
InOrder(node->right, visit);
}
}
template <class T>
void BinaryTree<T>::PostOrder(BTNode<T> *node, void (*visit)(const T&)) const {
if (node) {
PostOrder(node->left, visit);
PostOrder(node->right, visit);
visit(node->data);
}
}
template <class T>
int BinaryTree<T>::Width(BTNode<T> *node) const {
if (node == nullptr) return 0;
int maxWidth = 0, thisLevel = 1, nextLevel = 0;
queue<BTNode<T>*> q;
q.push(node);
while (!q.empty()) {
BTNode<T> *p = q.front();
q.pop();
thisLevel--;
if (p->left) {
q.push(p->left);
nextLevel++;
}
if (p->right) {
q.push(p->right);
nextLevel++;
}
if (thisLevel == 0) {
if (nextLevel > maxWidth) maxWidth = nextLevel;
thisLevel = nextLevel;
nextLevel = 0;
}
}
return maxWidth;
}
template <class T>
int BinaryTree<T>::NodeCount(BTNode<T> *node) const {
if (node == nullptr) return 0;
return 1 + NodeCount(node->left) + NodeCount(node->right);
}
```
### 解释
1. **CreateBinaryTree**:
- 使用队列来辅助层次遍历。
- 按照先序遍历的顺序读取字符,遇到 '#' 表示空节点。
- 构建根节点并将其加入队列。
- 依次处理队列中的节点,为其创建左右子节点,并将非空子节点加入队列。
2. **其他方法**:
- `PreOrder`, `InOrder`, `PostOrder`, 和 `LevelOrder` 分别实现了前序、中序、后序和层序遍历。
- `Width` 计算二叉树的最大宽度。
- `NodeCount` 计算二叉树的节点数。
- `Destroy` 用于销毁二叉树,释放内存。
这样,你可以根据给定的先序遍历序列构建二叉树,并进行各种遍历操作和其他计算。
阅读全文