用c++实现对任意给定的二叉树完成下列操作: (1)根据输入的序列,建立二叉链表存储结构: (2)输出该二叉树的先序、中序、后序遍历结果(递归算法); (3)先序遍历二叉树(非递归算法);(4)借助队列实现二叉树的层次遍历;(5)求二叉树的高度; (6)求二叉树叶子结点个数: (7)将二叉链表视为树或森林的孩子兄弟链表,计算其叶子结点个数。
时间: 2024-02-17 16:02:39 浏览: 31
好的,我会根据您的要求逐一回答。为了方便起见,我将使用 C++11 标准。
首先,我们需要定义二叉树的节点结构体:
```cpp
struct TreeNode {
char value;
TreeNode* left;
TreeNode* right;
};
```
然后,我们可以定义一个函数 `buildTree()` 来根据输入的序列建立二叉链表存储结构。这里我假设输入的序列已经存储在一个字符串中,每个字符表示一个节点的值,空节点用 `#` 表示。下面是代码实现:
```cpp
TreeNode* buildTree(const string& s, int& index) {
if (index >= s.length() || s[index] == '#') {
return nullptr;
}
TreeNode* root = new TreeNode{s[index], nullptr, nullptr};
++index;
root->left = buildTree(s, index);
++index;
root->right = buildTree(s, index);
return root;
}
TreeNode* buildTree(const string& s) {
int index = 0;
return buildTree(s, index);
}
```
接下来,我们可以定义递归算法实现二叉树的先序、中序、后序遍历。这里的遍历函数都接受一个函数指针作为参数,用来处理遍历到的节点。例如,对于先序遍历,我们可以这样实现:
```cpp
void preorder(TreeNode* root, function<void(TreeNode*)> visit) {
if (root == nullptr) {
return;
}
visit(root);
preorder(root->left, visit);
preorder(root->right, visit);
}
```
注意,这里的 `function<void(TreeNode*)>` 表示一个函数指针,它接受一个 `TreeNode*` 参数,返回值为 `void`。
下面是中序遍历和后序遍历的实现:
```cpp
void inorder(TreeNode* root, function<void(TreeNode*)> visit) {
if (root == nullptr) {
return;
}
inorder(root->left, visit);
visit(root);
inorder(root->right, visit);
}
void postorder(TreeNode* root, function<void(TreeNode*)> visit) {
if (root == nullptr) {
return;
}
postorder(root->left, visit);
postorder(root->right, visit);
visit(root);
}
```
接下来,我们可以使用非递归算法实现先序遍历。这里使用一个栈来模拟递归的过程。具体实现如下:
```cpp
void preorderNonRecursive(TreeNode* root, function<void(TreeNode*)> visit) {
stack<TreeNode*> s;
s.push(root);
while (!s.empty()) {
TreeNode* node = s.top();
s.pop();
if (node != nullptr) {
visit(node);
s.push(node->right);
s.push(node->left);
}
}
}
```
然后,我们可以使用队列实现二叉树的层次遍历。这里的算法很简单,用一个队列来存储节点,每次取出队首节点,访问它的左右子节点并将它们加入队列中。具体实现如下:
```cpp
void levelorder(TreeNode* root, function<void(TreeNode*)> visit) {
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if (node != nullptr) {
visit(node);
q.push(node->left);
q.push(node->right);
}
}
}
```
下面,我们可以实现求二叉树的高度和叶子结点个数。这里的算法都是递归实现的。求高度的代码如下:
```cpp
int getHeight(TreeNode* root) {
if (root == nullptr) {
return 0;
}
return 1 + max(getHeight(root->left), getHeight(root->right));
}
```
求叶子结点个数的代码如下:
```cpp
int getLeafCount(TreeNode* root) {
if (root == nullptr) {
return 0;
}
if (root->left == nullptr && root->right == nullptr) {
return 1;
}
return getLeafCount(root->left) + getLeafCount(root->right);
}
```
最后,我们可以将二叉链表视为树或森林的孩子兄弟链表,计算其叶子结点个数。这里的算法可以递归实现,也可以非递归实现。这里我给出递归实现的代码:
```cpp
int getLeafCount(TreeNode* root) {
if (root == nullptr) {
return 0;
}
if (root->left == nullptr && root->right == nullptr) {
return 1;
}
return getLeafCount(root->left) + getLeafCount(root->right);
}
int getLeafCountAsTree(TreeNode* root) {
if (root == nullptr) {
return 0;
}
if (root->left == nullptr && root->right == nullptr) {
return 1;
}
return getLeafCountAsTree(root->left) + getLeafCountAsTree(root->right);
}
int getLeafCountAsForest(TreeNode* root) {
int count = 0;
for (TreeNode* p = root; p != nullptr; p = p->right) {
count += getLeafCountAsTree(p->left);
}
return count;
}
```
这样,我们就完成了对任意给定的二叉树的六个操作。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)