二叉树的定义、建立、遍历函数(先中后)和释放操作函数
时间: 2023-07-31 17:08:55 浏览: 38
二叉树是一种树形结构,其中每个节点最多有两个子节点,分别称为左子节点和右子节点。以下是二叉树的定义:
```c++
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
```
二叉树的建立可以通过递归的方式实现。以下是以数组为输入建立二叉树的代码:
```c++
TreeNode* buildTree(vector<int>& nums, int start, int end){
if(start > end) return nullptr;
int mid = (start + end) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = buildTree(nums, start, mid - 1);
root->right = buildTree(nums, mid + 1, end);
return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
if(nums.empty()) return nullptr;
return buildTree(nums, 0, nums.size() - 1);
}
```
二叉树的遍历有三种方式:先序遍历、中序遍历和后序遍历。以下是这三种遍历方式的代码实现:
```c++
// 先序遍历
void preorder(TreeNode* root) {
if(root) {
cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}
}
// 中序遍历
void inorder(TreeNode* root) {
if(root) {
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
}
// 后序遍历
void postorder(TreeNode* root) {
if(root) {
postorder(root->left);
postorder(root->right);
cout << root->val << " ";
}
}
```
二叉树的释放操作函数可以通过递归的方式实现。以下是二叉树的释放函数:
```c++
void destroyTree(TreeNode* root) {
if(root) {
destroyTree(root->left);
destroyTree(root->right);
delete root;
}
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![py](https://img-home.csdnimg.cn/images/20210720083646.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)