首先我们要了解二叉树的数据结构是什么,本质上二叉树是一个有两个节点的链表,我们先了解的单链表的相关定义
单链表
创建一个朴素的单链表
#include <iostream>
using namespace std;
struct Node{
int val;
Node* next;
Node(int x) : val(x), next(nullptr) {}
};
int main()
{
return 0;
}
Node(int value) : data(value), next(nullptr) {}
-
构造函数定义:
Node(int value)
是构造函数的声明,它接受一个int
类型的参数value
。 -
成员初始化列表:
: data(value), next(nullptr)
是成员初始化列表,用于初始化类成员。data(value)
将构造函数的参数value
赋给data
成员变量。next(nullptr)
将next
指针初始化为nullptr
,表示该节点最初不指向任何其他节点。
-
空体:
{}
表示构造函数的主体,这里是空的,因为所有初始化工作都在成员初始化列表中完成了。
简而言之,这个构造函数创建一个 Node
对象时,设置 data
为提供的 value
值,而 next
则默认指向空,表示没有下一个节点。
创建一颗二叉树
比如我想要创建一颗这样的二叉树
在结构体当中定义两个结点,并且初始化这棵树
#include <iostream>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 初始化
void init(TreeNode* root){
root -> left = new TreeNode(2);
root -> right = new TreeNode(3);
root -> left -> left = new TreeNode(4);
root -> left -> right = new TreeNode(5);
root -> right -> left = new TreeNode(6);
root -> right -> right = new TreeNode(7);
}
int main()
{
// 初始化根节点是1
TreeNode* root = new TreeNode(1);
init(root);
return 0;
}
前序遍历、中序遍历、后序遍历
这里是利用了递归的思想,详细请看洛谷B3642 二叉树的遍历(前序、中序、后序)-CSDN博客
前序的代码如下,中序、后序就不展示了
#include <iostream>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 初始化
void init(TreeNode* root){
root -> left = new TreeNode(2);
root -> right = new TreeNode(3);
root -> left -> left = new TreeNode(4);
root -> left -> right = new TreeNode(5);
root -> right -> left = new TreeNode(6);
root -> right -> right = new TreeNode(7);
}
void dfs(TreeNode* root){
if(root == nullptr) return;
cout << root -> val << " ";
dfs(root -> left);
dfs(root -> right);
}
int main()
{
// 初始化根节点是1
TreeNode* root = new TreeNode(1);
init(root);
dfs(root);
return 0;
}
层次遍历
这里讲一下层次遍历以上面那棵树为例
首先要对队列很熟悉,层次遍历是每一层从左往右依此遍历,那么这棵树的层次遍历就是1234567
那就很明确了,从第一层开始,从左往右加入队列即可
#include <iostream>
#include <queue>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 初始化
void init(TreeNode* root){
root -> left = new TreeNode(2);
root -> right = new TreeNode(3);
root -> left -> left = new TreeNode(4);
root -> left -> right = new TreeNode(5);
root -> right -> left = new TreeNode(6);
root -> right -> right = new TreeNode(7);
}
void bfs(TreeNode* root){
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
TreeNode* node = q.front();
q.pop();
cout << node -> val << " ";
if(node -> left != nullptr) q.push(node -> left);
if(node -> right != nullptr) q.push(node -> right);
}
}
int main()
{
// 初始化根节点是1
TreeNode* root = new TreeNode(1);
init(root);
bfs(root);
return 0;
}
加油
标签:right,TreeNode,++,表到,int,二叉树,new,root,left From: https://blog.csdn.net/AuRoRamth/article/details/142066909