某人的惨案要我擦屁股=。=
#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> *left = Create_dfs(v, fin, n);
Node<T> *right = Create_dfs(v, fin, n);
Node<T> *p = new Node<T>(val, left, right);
len++;
return p;//记得返回
}
}
void Create(vector<T> &v, T &fin, int n = 0) {//设另外个函数把root接上
root = Create_dfs(v, fin, n);
}
void Create_bfs(vector<T> &v, T &fin)//n为节点数目,root必须加引用,否则函数内的一切操作白搭
{
int i = 0;//a用作输入节点数据,i记录已经加入树中的节点个数(可以不用i,但有时候需要补很多0)
queue<Node<T> *> q;//用于按层输入数据,库函数,随便搜一搜就知道queue怎么用了
root = new Node<T>(v[i++]);//申请根节点
q.push(root);//入队
if (i == v.size()) return;
while (!q.empty()) {
Node<T> *tmp = q.front();//一轮循环为root,以后的循环为temp->R或temp->L;
q.pop();//出队
if (v[i] == fin) {
tmp->Left = NULL;
i++;
}
else {
tmp->Left = new Node<T>(v[i]);//一轮循环为将root指针的左孩子指向一个新节点,向新节点赋值刚输入的数据,并将新节点的左右孩子置NULL
q.push(tmp->Left);
i++;
}
if (i == v.size()) return;
if (v[i] == fin) {
tmp->Right = NULL;
i++;
}
else {
tmp->Right = new Node<T>(v[i]);
q.push(tmp->Right);
i++;
}
if (i == v.size()) return;
}
}
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;
}
bool isValidBST() {
return isValidBST_dfs(root);
}
bool isValidBST_dfs(Node<T> *p) {
if (!p) return true;
if (p->Left && p->data < p->Left->data) return false;
if (p->Right && p->data > p->Right->data) return false;
return isValidBST_dfs(p->Left) && isValidBST_dfs(p->Right);
}
};
int main() {
stringstream ss;
string str;
getline(cin, str);
ss.str(str);
string fin;
ss >> fin;
ss.str("");
ss.clear();
getline(cin, str);
ss.str(str);
string tmp;
vector<string> v;
while (ss >> tmp, v.push_back(tmp), tmp = fin, ss.get() == ' ');
ss.str("");
ss.clear();
BiTree<string> tree;
tree.Create_bfs(v, fin);
tree.write(1);
if (tree.isValidBST())
cout << "true" << endl;
else
cout << "false" << 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层序)遍历树的结果输出
*/
手机扫一扫
移动阅读更方便
你可能感兴趣的文章