(C++注释)对任意给定的二叉树完成下列操作: (1)根据输入的序列,建立二叉链表存储结构; (2)输出该二叉树的先序、中序、后序遍历结果(递归算法); (3)先序遍历二叉树(非递归算法); (4)借助队列实现二叉树的层次遍历; (5)求二叉树的高度; (6)求二叉树叶子结点个数; (7)将二叉链表视为树或森林的孩子兄弟链表,计算其叶子结点个数。
时间: 2023-10-30 20:04:42 浏览: 85
好的,这是一个关于二叉树的问题,我将根据您的问题逐步回答,并且在代码中添加注释。
1. 根据输入的序列,建立二叉链表存储结构
```cpp
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x): val(x), left(NULL), right(NULL){}
};
// 递归建立二叉树
TreeNode* buildTree(vector<int>& nums, int& index){
if(index >= nums.size() || nums[index] == -1){
index++;
return NULL;
}
TreeNode* node = new TreeNode(nums[index]);
index++;
node->left = buildTree(nums, index);
node->right = buildTree(nums, index);
return node;
}
// 将输入的序列转换为二叉树
TreeNode* buildTree(vector<int>& nums){
int index = 0;
return buildTree(nums, index);
}
```
2. 输出该二叉树的先序、中序、后序遍历结果(递归算法)
```cpp
// 先序遍历
void preorder(TreeNode* root){
if(root == NULL) return;
cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}
// 中序遍历
void inorder(TreeNode* root){
if(root == NULL) return;
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
// 后序遍历
void postorder(TreeNode* root){
if(root == NULL) return;
postorder(root->left);
postorder(root->right);
cout << root->val << " ";
}
```
3. 先序遍历二叉树(非递归算法)
```cpp
void preorderNonRecursive(TreeNode* root){
stack<TreeNode*> st;
st.push(root);
while(!st.empty()){
TreeNode* node = st.top();
st.pop();
if(node == NULL) continue;
cout << node->val << " ";
st.push(node->right);
st.push(node->left);
}
}
```
4. 借助队列实现二叉树的层次遍历
```cpp
void levelorder(TreeNode* root){
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
TreeNode* node = q.front();
q.pop();
if(node == NULL) continue;
cout << node->val << " ";
q.push(node->left);
q.push(node->right);
}
}
```
5. 求二叉树的高度
```cpp
int getHeight(TreeNode* root){
if(root == NULL) return 0;
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
return max(leftHeight, rightHeight) + 1;
}
```
6. 求二叉树叶子结点个数
```cpp
int getLeafCount(TreeNode* root){
if(root == NULL) return 0;
if(root->left == NULL && root->right == NULL) return 1;
return getLeafCount(root->left) + getLeafCount(root->right);
}
```
7. 将二叉链表视为树或森林的孩子兄弟链表,计算其叶子结点个数
```cpp
int getForestLeafCount(TreeNode* root){
if(root == NULL) return 0;
if(root->left == NULL && root->right == NULL) return 1;
return getForestLeafCount(root->left) + getForestLeafCount(root->right);
}
```
以上就是关于二叉树的一些基本操作,希望能够帮到您!
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.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)