二叉树建立和普遍算法的代码
时间: 2024-03-17 09:45:20 浏览: 11
以下是二叉树的建立和三种遍历算法的C++代码实现:
```C++
#include <iostream>
#include <queue>
using namespace std;
// 二叉树结构体定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 递归方式建立二叉树
TreeNode* createTree(vector<int>& nums, int left, int right) {
if (left > right) {
return NULL;
}
int mid = (left + right) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = createTree(nums, left, mid - 1);
root->right = createTree(nums, mid + 1, right);
return root;
}
// 递归方式前序遍历二叉树
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 << " ";
}
// 非递归方式层次遍历二叉树
void levelOrder(TreeNode* root) {
if (root == NULL) {
return;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
cout << node->val << " ";
if (node->left != NULL) {
q.push(node->left);
}
if (node->right != NULL) {
q.push(node->right);
}
}
}
int main() {
vector<int> nums = {1, 2, 3, 4, 5, 6, 7};
TreeNode* root = createTree(nums, 0, nums.size() - 1);
cout << "preOrder: ";
preOrder(root);
cout << endl;
cout << "inOrder: ";
inOrder(root);
cout << endl;
cout << "postOrder: ";
postOrder(root);
cout << endl;
cout << "levelOrder: ";
levelOrder(root);
cout << endl;
return 0;
}
```
以上代码实现了二叉树的建立和三种遍历算法,其中二叉树的建立使用递归方式,遍历算法使用了递归和非递归两种方式。