二叉树的创建和三种遍历方式
时间: 2023-11-05 13:04:13 浏览: 44
二叉树是一种经常用于数据存储和搜索的数据结构。它由节点构成,每个节点最多有两个子节点,分别称为左子节点和右子节点。以下是二叉树的创建和三种遍历方式:
1. 创建二叉树
二叉树的创建可以通过递归或非递归方式实现。以下是递归方式的示例代码:
```C++
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* createTree(vector<int>& nums, int index) {
if (index >= nums.size() || nums[index] == -1) {
return NULL;
}
TreeNode* root = new TreeNode(nums[index]);
root->left = createTree(nums, index * 2 + 1);
root->right = createTree(nums, index * 2 + 2);
return root;
}
// 调用方式:TreeNode* root = createTree(nums, 0);
// 其中 nums 是二叉树的层次遍历序列,-1 表示空节点。
```
2. 三种遍历方式
二叉树的遍历方式分为前序遍历、中序遍历和后序遍历。以下是递归方式的示例代码:
前序遍历:根节点 -> 左子树 -> 右子树
```C++
void preOrder(TreeNode* root) {
if (root == NULL) {
return;
}
cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}
// 调用方式:preOrder(root);
```
中序遍历:左子树 -> 根节点 -> 右子树
```C++
void inOrder(TreeNode* root) {
if (root == NULL) {
return;
}
inOrder(root->left);
cout << root->val << " ";
inOrder(root->right);
}
// 调用方式:inOrder(root);
```
后序遍历:左子树 -> 右子树 -> 根节点
```C++
void postOrder(TreeNode* root) {
if (root == NULL) {
return;
}
postOrder(root->left);
postOrder(root->right);
cout << root->val << " ";
}
// 调用方式:postOrder(root);
```