周口网站建设电话,网站建设岗位招聘,网站制作公司要文化建设费,宁波网站制作公司排名首先我们要了解二叉树的数据结构是什么#xff0c;本质上二叉树是一个有两个节点的链表#xff0c;我们先了解的单链表的相关定义
单链表 创建一个朴素的单链表
#include iostreamusing namespace std;struct Node{int val;Node* next;Node(int x) : val(x), next(…首先我们要了解二叉树的数据结构是什么本质上二叉树是一个有两个节点的链表我们先了解的单链表的相关定义
单链表 创建一个朴素的单链表
#include iostreamusing 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 iostreamusing 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()
{// 初始化根节点是1TreeNode* root new TreeNode(1); init(root);return 0;
}
前序遍历、中序遍历、后序遍历
这里是利用了递归的思想详细请看洛谷B3642 二叉树的遍历前序、中序、后序-CSDN博客
前序的代码如下中序、后序就不展示了
#include iostreamusing 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()
{// 初始化根节点是1TreeNode* root new TreeNode(1); init(root);dfs(root);return 0;
}
层次遍历
这里讲一下层次遍历以上面那棵树为例
首先要对队列很熟悉层次遍历是每一层从左往右依此遍历那么这棵树的层次遍历就是1234567
那就很明确了从第一层开始从左往右加入队列即可
#include iostream
#include queueusing 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){queueTreeNode* 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()
{// 初始化根节点是1TreeNode* root new TreeNode(1); init(root);bfs(root);return 0;
}
加油
