用链式存储写一个二叉树包括各种功能实现
时间: 2023-12-29 15:23:45 浏览: 34
好的,以下是基于链式存储的二叉树的实现,包括创建二叉树、前序、中序、后序遍历、求树的深度、查找节点等功能。
```c++
#include<iostream>
using namespace std;
//定义二叉树节点
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
//创建二叉树
void createTree(TreeNode*& root) {
int val;
cin >> val;
if (val == -1) {
root = nullptr;
}
else {
root = new TreeNode(val);
createTree(root->left);
createTree(root->right);
}
}
//前序遍历
void preOrder(TreeNode* root) {
if (root == nullptr) {
return;
}
cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}
//中序遍历
void inOrder(TreeNode* root) {
if (root == nullptr) {
return;
}
inOrder(root->left);
cout << root->val << " ";
inOrder(root->right);
}
//后序遍历
void postOrder(TreeNode* root) {
if (root == nullptr) {
return;
}
postOrder(root->left);
postOrder(root->right);
cout << root->val << " ";
}
//求树的深度
int depth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int leftDepth = depth(root->left);
int rightDepth = depth(root->right);
return max(leftDepth, rightDepth) + 1;
}
//查找节点
TreeNode* search(TreeNode* root, int val) {
if (root == nullptr || root->val == val) {
return root;
}
TreeNode* leftResult = search(root->left, val);
if (leftResult != nullptr) {
return leftResult;
}
TreeNode* rightResult = search(root->right, val);
if (rightResult != nullptr) {
return rightResult;
}
return nullptr;
}
int main() {
TreeNode* root;
cout << "请输入二叉树的节点(-1表示该节点为空):" << endl;
createTree(root);
cout << "前序遍历结果:" << endl;
preOrder(root);
cout << endl;
cout << "中序遍历结果:" << endl;
inOrder(root);
cout << endl;
cout << "后序遍历结果:" << endl;
postOrder(root);
cout << endl;
cout << "树的深度为:" << depth(root) << endl;
cout << "请输入要查找的节点值:" << endl;
int val;
cin >> val;
TreeNode* result = search(root, val);
if (result == nullptr) {
cout << "未找到节点" << val << endl;
}
else {
cout << "找到节点" << val << endl;
}
return 0;
}
```
以上代码实现了二叉树的基本功能,包括创建二叉树、前序、中序、后序遍历、求树的深度、查找节点等。
相关推荐
![](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)