C++二叉树的算法代码
时间: 2023-10-05 12:05:46 浏览: 34
以下是C++实现二叉树的基本算法代码,包括创建二叉树、遍历二叉树、查找节点等操作:
```cpp
#include <iostream>
using namespace std;
// 二叉树的节点定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 创建二叉树
TreeNode* createBinaryTree() {
int val;
cin >> val;
if (val == -1) { // -1表示该节点为空
return NULL;
}
TreeNode* node = new TreeNode(val);
node->left = createBinaryTree();
node->right = createBinaryTree();
return node;
}
// 先序遍历二叉树
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 << " ";
}
// 查找二叉树中的节点
TreeNode* findNode(TreeNode* root, int val) {
if (root == NULL) {
return NULL;
}
if (root->val == val) {
return root;
}
TreeNode* node = findNode(root->left, val);
if (node != NULL) {
return node;
}
return findNode(root->right, val);
}
int main() {
TreeNode* root = createBinaryTree();
cout << "先序遍历结果:" << endl;
preOrder(root);
cout << endl;
cout << "中序遍历结果:" << endl;
inOrder(root);
cout << endl;
cout << "后序遍历结果:" << endl;
postOrder(root);
cout << endl;
int val;
cout << "请输入要查找的节点值:" << endl;
cin >> val;
TreeNode* node = findNode(root, val);
if (node != NULL) {
cout << "找到了节点,值为:" << node->val << endl;
}
else {
cout << "没找到节点" << endl;
}
return 0;
}
```
使用示例:
```
输入:
1 2 -1 -1 3 -1 -1
4
输出:
先序遍历结果:
1 2 3
中序遍历结果:
2 1 3
后序遍历结果:
2 3 1
请输入要查找的节点值:
找到了节点,值为:3
```
这里实现的二叉树是基于链表的方式,每个节点包括一个值、左子树和右子树。其中遍历二叉树的方法有三种:先序遍历、中序遍历、后序遍历。查找节点的方法使用了递归实现。