【数据结构】二叉树基础(带你详细了解二叉树）
🌏个人博客主页：心.c
前言：最近学习了二叉树，和大家分享一下我的理解和感悟，希望对大家有所帮助，话不多说，开整！！！
🔥🔥🔥专题文章：二叉树
😽感谢大家的点赞👍收藏⭐️评论✍您的一键三连是我更新的动力 💓
目录
概念：
二叉树的结构：
图解：
结构体创建：
二叉树的分类：
满二叉树
完全二叉树：
平衡二叉树
二叉搜索树
二叉树遍历：
二叉树遍历方式：
递归遍历演示：
前序遍历：
中序遍历：
后续遍历：
迭代遍历演示（栈）：
前序遍历：
中序遍历：
后续遍历：
概念：
二叉树是一种每个节点最多有两个子节点的数据结构。通常，这两个子节点被称为左子节点和右子节点。
二叉树的结构：
图解：
结构体创建：
// 二叉树节点结构体
struct TreeNode {
int val; // 节点值
TreeNode* left; // 指向左子节点的指针
TreeNode* right; // 指向右子节点的指针
// 默认构造函数
TreeNode() : val(0), left(nullptr), right(nullptr) {}
// 带值的构造函数
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
// 带左右子节点的构造函数
TreeNode(int x, TreeNode* left, TreeNode* right)
: val(x), left(left), right(right) {}
};二叉树的分类：
满二叉树
每个节点都有0或2个子节点的二叉树。满二叉树的每一层都完全填满。
完全二叉树：
一个二叉树，除了最底层外，每层的节点都被填满，且最底层的节点都靠左对齐。
平衡二叉树：
一棵二叉树，任意节点的两个子树的高度差不超过1。常见的平衡二叉树包括 AVL 树和红黑树。
二叉搜索树：
一种特定类型的二叉树，每个节点的左子树的值都小于节点的值，而右子树的值都大于节点的值。这使得搜索、插入和删除操作都具有较高的效率
二叉树遍历：
二叉树遍历方式：
前序遍历：
- 先遍历中间节点
- 然后遍历左孩子
- 最后遍历右孩子
中序遍历：
- 先遍历左孩子
- 再遍历中间节点
- 追回遍历右孩子
后续遍历：
- 先遍历左孩子
- 再遍历右孩子
- 最后遍历中间节点
递归遍历演示：
相关题目链接：
1. 前序遍历
2. 中序遍历
3. 后序遍历
前序遍历：
class Solution {
public:
void postorder(TreeNode* root, vector<int>& res) {
if (!root) {
return;
}
res.push_back(root->val);
postorder(root->left, res);
postorder(root->right, res);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
postorder(root, res);
return res;
}
};中序遍历：
class Solution {
public:
void postorder(TreeNode* root, vector<int>& res) {
if (!root) {
return;
}
postorder(root->left, res);
res.push_back(root->val);
postorder(root->right, res);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
postorder(root, res);
return res;
}
};后续遍历：
class Solution {
public:
void postorder(TreeNode* root, vector<int>& res) {
if (!root) {
return;
}
postorder(root->left, res);
postorder(root->right, res);
res.push_back(root->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
postorder(root, res);
return res;
}
};迭代遍历演示（栈）：
前序遍历：
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
stack<TreeNode*> stack;
vector<int> result;
if (root == nullptr)
return result;
stack.push(root);
while (!stack.empty()) {
root = stack.top();
stack.pop();
result.push_back(root->val);
if (root->right) {
stack.push(root->right);
}
if (root->left) {
stack.push(root->left);
}
}
return result;
}
};中序遍历：
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> stack;
TreeNode* cur = root;
while (cur != nullptr || !stack.empty()) {
if (cur != nullptr) {
stack.push(cur);
cur = cur->left;
} else {
cur = stack.top();
stack.pop();
result.push_back(cur->val);
cur = cur->right;
}
}
return result;
}
};后续遍历：
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
stack<TreeNode*> stack;
vector<int> result;
if (root == nullptr)
return result;
stack.push(root);
while (!stack.empty()) {
root = stack.top();
stack.pop();
result.push_back(root->val);
if (root->left) {
stack.push(root->left);
}
if (root->right) {
stack.push(root->right);
}
}
reverse(result.begin(), result.end());
return result;
}
};这里就分享完了，感谢大家的观看