二叉树基础模板
2022/4/14 6:17:06
本文主要是介绍二叉树基础模板,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#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层序)遍历树的结果输出 */
这篇关于二叉树基础模板的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?