Java教程
二叉树基础模板
本文主要是介绍二叉树基础模板，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
#include <bits/stdc++.h>
using namespace std;
template<class T>
struct Node{
T data;
Node<T> *Left, *Right;
Node(const T &val,Node<T> *Lptr = nullptr, Node<T> *Rptr = nullptr):data(val),Left(Lptr),Right(Rptr){}
};
template<class T>
class BiTree
{
Node<T> *root;
int len;
public:
BiTree():root(nullptr),len(0){}
BiTree(const T &val):root(new Node<T>(val)),len(1){}
~BiTree(){
clear();
}
void clear_dfs(Node<T> *p){
if(!p) return;//注意跳出
clear_dfs(p->Left);
clear_dfs(p->Right);
delete p;
len--;
}
void clear(){
clear_dfs(root);
root = nullptr;//不能忘
}
void Revolute_dfs(Node<T> *p){
if(!p) return;
Revolute_dfs(p->Left);
Revolute_dfs(p->Right);
Node<T> *tmp = p->Left;
p->Left = p->Right;
p->Right = tmp;
}
void Revolute(){
Revolute_dfs(root);
}
int size()const{
return len;
}
bool empty()const{
return !len;
}
void Leefsize_dfs(Node<T> *p,int &cnt)const{
if(!p) return;
Leefsize_dfs(p->Left,cnt);
Leefsize_dfs(p->Right,cnt);
if(!p->Left && !p->Right){
cnt++;
return;
}
}
int Leefsize()const{
int cnt = 0;
Leefsize_dfs(root,cnt);
return cnt;
}
Node<T> *find_dfs(Node<T> *p,const T &val)const{
if(!p) return nullptr;
if(p->data == val) return p;
Node<T> *tmp = nullptr;
if(tmp = find_dfs(p->Left,val)) return tmp;
if(tmp = find_dfs(p->Right,val)) return tmp;
return nullptr;
}
Node<T> *find(const T &val)const{
return find_dfs(root,val);
}
void Depth_dfs(Node<T> *p,int &dmax,int d = 1)const{
if(!p) return;
dmax = max(dmax,d);
Depth_dfs(p->Left,dmax,d+1);
Depth_dfs(p->Right,dmax,d+1);
}
int Depth()const{
int dmax = 0;
Depth_dfs(root,dmax);
return dmax;
}
int Depth(const T &val)const{
int dmax = 0;
Depth_dfs(find(val),dmax);
return dmax;
}
Node<T> *Create_dfs(vector<T> &v,T &fin,int &n){//必须引用不然没法累加
clear();
T val = v[n++];
if(val == fin)
return nullptr;
else{
Node<T> *p = new Node<T>(val,Create_dfs(v,fin,n),Create_dfs(v,fin,n));
len++;
return p;//记得返回
}
}
void Create(vector<T> &v,T &fin,int n = 0){//设另外个函数把root接上
root = Create_dfs(v,fin,n);
}
void Traverse_dfs(Node<T> *p,vector<T> &v,int mode = 0)const{
if(!p) return;//递归注意跳出
if(mode == 0) v.push_back(p->data);
Traverse_dfs(p->Left,v,mode);
if(mode == 1) v.push_back(p->data);
Traverse_dfs(p->Right,v,mode);
if(mode == 2) v.push_back(p->data);
}
void Traverse_fo_uc(Node<T> *p,vector<T> &v)const{
stack<Node<T> *> s;
Node<T> *ptr = p;///先判断节点，在入栈，可以在出栈把根节点pop，防止死循环，如果先入栈就会麻烦
while(ptr || !s.empty()){
if(ptr){//遍历左树节点
s.push(ptr);
v.push_back(ptr->data);
ptr = ptr->Left;
}
else{//转移到右树
Node<T> *q = s.top();
s.pop();//踢掉根节点
ptr = q->Right;
}
}
}
void Traverse_io_uc(Node<T> *p,vector<T> &v)const{///基本和上面一样
stack<Node<T> *> s;
Node<T> *ptr = p;
while(ptr || !s.empty()){
if(ptr){//遍历左树节点
s.push(ptr);
ptr = ptr->Left;
}
else{//转移到右树
Node<T> *q = s.top();
s.pop();//踢掉根节点
v.push_back(q->data);
ptr = q->Right;
}
}
}
void Traverse_po_uc(Node<T> *p,vector<T> &v)const{
stack<Node<T> *> s;
if(p) s.push(p);
Node<T> *last = nullptr;
while(!s.empty()){
Node<T> *ptr = s.top();
if(!ptr->Left && !ptr->Right || last && last == ptr->Left && !ptr->Right || last && last == ptr->Right){///叶节点||有左孩子&&上次访问左孩子&&无右孩子||有右孩子&&访问了右孩子
v.push_back(ptr->data);
last = ptr;
s.pop();
}
else{
if(ptr->Right) s.push(ptr->Right);
if(ptr->Left) s.push(ptr->Left);
}
}
}
void Traverse_bfs(Node<T> *p,vector<T> &v)const{
queue<Node<T> *> q;
q.push(p);
while(!q.empty()){
v.push_back(q.front()->data);
if(q.front()->Left) q.push(q.front()->Left);
if(q.front()->Right) q.push(q.front()->Right);
q.pop();
}
}
void Traverse(vector<T> &v,int mode = 0)const{
if(mode<=2) Traverse_dfs(root,v,mode);
else if(mode == 3) Traverse_fo_uc(root,v);
else if(mode == 4) Traverse_io_uc(root,v);
else if(mode == 5) Traverse_po_uc(root,v);
else if(mode == 6) Traverse_bfs(root,v);
}
void write(int mode = 0)const{
vector<T> v;
Traverse(v,mode);
for(int i = 0;i<v.size();i++){
cout<<v[i]<<(i == v.size()-1?"":",");
}
cout<<endl;
}
};
int main(){
string fin = "null";
string str = "A B null C D null null E null null F null G null H null null";
stringstream ss;
ss.str(str);
string tmp;
vector<string> v;
while(ss>>tmp,v.push_back(tmp),ss.get() == ' ');
ss.str("");
ss.clear();
BiTree<string> tree;
tree.Create(v,fin);
for(int i = 0;i<=6;i++){
tree.write(i);
}
cout<<tree.empty()<<' '<<tree.size()<<endl;
cout<<tree.Leefsize()<<endl;
tree.Revolute();
for(int i = 0;i<=6;i++){
tree.write(i);
}
cout<<tree.Depth()<<' '<<tree.Depth("C")<<endl;
tree.clear();
cout<<tree.empty()<<' '<<tree.size()<<endl;
return 0;
}
/**
！！递归部分没法内置初值，所以要引用外壳函数的变量
节点
数据
左指针，右指针
构造（值，左指针，右指针）
二叉树
根节点指针
长度
构造：无根节点
构造（值）：有根节点
析构：销毁
clear_dfs（节点指针）:clear的内置递归
clear:清空树，外壳
Revolute_dfs（节点指针）：Revolute的内置递归
Revolute：置换所有左右子树，外壳
size：返回节点总数
Leefsize_dfs（节点指针，计数器）：Leefsize的内置递归
Leefsize：返回叶节点总数，外壳
empty：返回是否为空
find_dfs（节点指针，值）：find的内置递归
find(值)：查找此值的节点地址
Depth_dfs（节点指针，最大值容器，计数器）：Depth的内置递归
Depth：返回树深度
Depth（值）：返回指定值作为根节点的树深度
Create_dfs（vector序列，结束符，计数器）：返回父节点，Create的内置递归
Create（vector序列，结束符，计数器）：创建树，外壳
Traverse_dfs（节点指针，vector容器，模式）：Traverse的内置递归
Traverse_fo_uc（节点指针，vector容器）：Traverse的内置非递归前序
Traverse_io_uc（节点指针，vector容器）：Traverse的内置非递归中序
Traverse_po_uc（节点指针，vector容器）：Traverse的内置非递归后序
Traverse_bfs（节点指针，vector容器）：Traverse的内置广搜
Traverse（vector容器，模式）：以（0先序，1中序，2后序）遍历树，保存到容器，外壳
write（模式）：将以（0~2递归前中后序，3~5非递归前中后序，6层序）遍历树的结果输出
*/
这篇关于二叉树基础模板的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
怎么修改Kafka的JVM参数？-icode9专业技术文章分享12-24
-
线下车企门店如何实现线上线下融合？12-23
-
鸿蒙Next ArkTS编程规范总结12-23
-
物流团队冬至高效运转，哪款办公软件可助力风险评估？12-23
-
优化库存，提升效率：医药企业如何借助看板软件实现仓库智能化12-23
-
项目管理零负担！轻量化看板工具如何助力团队协作12-23
-
电商活动复盘，为何是团队成长的核心环节？12-23
-
鸿蒙Next ArkTS高性能编程实战12-23
-
数据驱动：电商复盘从基础到进阶！12-23
-
从数据到客户：跨境电商如何通过销售跟踪工具提升营销精准度？12-23
-
汽车4S店运营效率提升的核心工具12-23
-
ERP 系统开发案例：用 PERT 图打造高效项目管理12-23
-
初创团队必备！全面解析支持甘特图的项目管理工具与功能特点12-23
-
任务进度跟踪不再难！可视化项目协作工具精选12-23
-
看板工具为汽车销售门店协作赋能：关键方法12-23
栏目导航
