文章目录
二叉树
结构体
struct TreeNode(){
char data;
TreeNode *left;
TreeNode *right;
TreeNode(char c){
data=c;
left=right=NULL;
}
};
生成树 : queue
#include<queue>
queue<TreeNode*> arr;
TreeNode *builtTree(string str){
int i=1;
TreeNode *head=new TreeNode(str[0]);
//进队列
arr.push(head);
//队列不空
while(!arr.Empty()&&i<str.length){
//获取队首 front ...... back() 获取队尾
TreeNode *node=arr.front();
node->left=new TreeNode(str[i]);
i++;
if(i<str.length){
node->right=new TreeNode(str[i]);
i++;
}
//出队列
arr.pop();
}
return head;
}
删除树
//递归版本 【非递归半看下面深度遍历非递归部分】
int deleteTree(TreeNode* node){
//使用后序遍历删除
if(node->left!=NULL){
deleteTree(node->left);
}
if(node->right!=NULL){
deleteTree(node->right);
}
//到这里，子树已经删除好了【看最后一步】
delete node;
}
深度遍历（VLR. LVR. LRV）
具体内容
- 前序遍历VLR：先输出节点L的数据，再递归左树，右树
- 中序遍历LVR：先遍历左树，输出节点数据，遍历右树
- 后序遍历LRV：遍历左树，右树，再输出节点
利用遍历结果可推导树的结构： 中序遍历+ 前/后序遍历
- 前序遍历第一个数据是 树头节点 ，后序遍历最后一个数据是 树头节点
- 中序遍历划分左右树
递归
//前序遍历 先输出节点，再左右树
void pre_order(TreeNode* node){
cout<<node->data;
per_other(node->left);
per_other(node->right);
}
//中序遍历：LVR
void middle_other(TreeNode* node){
middle_other(node->left);
cout<<node->data;
middle_other(node->right);
}
//后序遍历：左右树，再输出节点
void back_other(){
back_middle(node->left);
back_middle(node->right);
cout<<node->data;
}
非递归（栈 : LIFO）
//深度遍历:非递归版 stack
stack<TreeNode*> ARR;
//前序遍历: 节点输出，深度左树，栈顶右树
void pro_DFS(TreeNode* node) {
while (node || !ARR.empty()) {
while (node)
{
cout << node->data;
ARR.push(node);
node = node->left;
}
node = ARR.top();
ARR.pop();
node = node->right;
}
}
//中序遍历：深度左树，节点输出，栈顶右树
void middle_DFS(TreeNode* node) {
while (node||!ARR.empty())
{
while (node)
{
ARR.push(node);
node = node->left;
}
node = ARR.top();
cout << node->data;
ARR.pop();
node = node->right;
}
}
后序遍历 【233333】
//后序遍历：深度左树,放节点、标志，访问栈顶{弹出节点}，访问节点右树，修改标记
stack<bool> flag;
void back_DFS(TreeNode* node) {
while (node||!ARR.empty())
{
while (node) {
ARR.push(node);
flag.push(false);
node = node->left;
}
node = ARR.top();
//弹出节点
while(flag.top()) {
cout << node->data;
ARR.pop();
flag.pop();
//栈空则 完成了。
if (ARR.empty()) return;
node = ARR.top();
}
//访问右树，修改标记
flag.pop();
flag.push(true);
node = node->right;
}
}
STL - stack
- top()：返回一个栈顶元素的引用，类型为 T&。如果栈为空，返回值未定义。
- push(const T& obj)：可以将对象副本压入栈顶。这是通过调用底层容器的 push_back() 函数完成的。
- push(T&& obj)：以移动对象的方式将对象压入栈顶。这是通过调用底层容器的有右值引用参数的 push_back() 函数完成的。
- pop()：弹出栈顶元素。
- size()：返回栈中元素的个数。
- empty()：在栈中没有元素的情况下返回 true。
- emplace()：用传入的参数调用构造函数，在栈顶生成对象。
- swap(stack<T> & other_stack)：将当前栈中的元素和参数中的元素交换。参数所包含元素的类型必须和当前栈的相同。对于 stack 对象有一个特例化的全局函数 swap() 可以使用。
广度遍历（层次遍历）
非递归（队列：FIFO）
#include<queue>
using namespace std;
queue<TreeNode*> arr;
void BFS(TreeNode* node) {
//空树判断。放头结点
if (node == NULL) return;
arr.push(node);
while (!arr.empty()) {
node = arr.front();
arr.pop();
cout << node->data;
if(node->left!=NULL)arr.push(node->left);
if(node->right!=NULL)arr.push(node->right);
}
}
STL queue
- front()：返回 queue 中第一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。
- back()：返回 queue 中最后一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。
- push(const T& obj)：在 queue 的尾部添加一个元素的副本。这是通过调用底层容器的成员函数 > - push_back() 来完成的。
- push(T&& obj)：以移动的方式在 queue 的尾部添加元素。这是通过调用底层容器的具有右值引用参数的成员函数 push_back() 来完成的。
- pop()：删除 queue 中的第一个元素。
- size()：返回 queue 中元素的个数。
- empty()：如果 queue 中没有元素的话，返回 true。
- emplace()：用传给 emplace() 的参数调用 T 的构造函数，在 queue 的尾部生成对象。
- swap(queue &other_q)：将当前 queue 中的元素和参数 queue 中的元素交换。它们需要包含相同类型的元素。也可以调用全局函数模板 swap() 来完成同样的操作。
参考