#include<iostream>
#include<stack>
#include<queue>
#include<string>
#include<vector>
using namespace std;
template<class T>
struct Node{
T value;
Node* pLeft;
Node*
PRight;
bool isFirst;
Node(T value){
this->value = value;
pLeft = pRight = NULL;
isFirst = true;
}
};
template<class T>
class Tree{
private:
Node<T>* root;
public:
Tree(){
root = NULL;
}
//插入值
/*1.如果当前节点为空，则插入值到当前节点
*2.如果当前节点不为空，且待插入值大于当前节点，则进入当前节点的右子节点
*3.如果当前节点不为空，且待插入值小于当前节点，则进入当前节点的左子节点
* */
void insert(T value){
mInsert(root, value);
}
//递归前中后遍历
void recursive(){
mRecursive(root);
}
//前序遍历(非递归)
/*
* 1.将二叉树的根节点设为p
* 2.访问节点p，如果p不为空，则将p压入栈
* 3.访问p的左子节点，如果不为空，则将p的值设为p的左子节点，将p压入栈，循环此过程
* 4.如果p的左子节点为空，则弹出栈顶元素，判断top节点的右子节点是否为空
* 5.如果top节点的右子节点不为空，则将p的值设为top节点的右子节点,并将p压入栈，执行3过程
* 6.如果top节点的右子节点为空，则继续弹出栈顶元素，循环此过程，直至找到一个右子节点不为空的top节点
* 7.直到栈空为止结束
* */
void DLR(){
stack<Node<T>*> s;
Node<T>* p = root;
while(p || !s.empty()){
while(p){
cout << p->value << ' ';
s.push(p);
p = p->pLeft;
}
if(!s.empty()){
p = s.top();
s.pop();
p = p->pRight;
}
}
}
//中序遍历(非递归)
/*
* 思路和前序遍历非递归过程十分相似
**/
void LDR(){
stack<Node<T>*> s;
Node<T>* p = root;
while(p || !s.empty()){
while(p){
s.push(p);
p = p->pLeft;
}
if(!s.empty()){
p = s.top();
s.pop();
cout << p->value << ' ';
p = p->pRight;
}
}
}
//后序遍历(非递归需要辅助节点isFirst)
/*
*思路：程序保证满足两个条件：
*1.当一个节点有未访问过的子节点时，需要先访问其子节点
*2.不能重复访问一个节点的子节点
*
*1.将根节点压入栈，设根节点为Node
*2.按照顺序将Node节点的右子节点(不为空并且之前没有访问过)和左子节点(不为空并且之前没有访问过)压入栈
*3.判断Node节点是否等于栈顶节点，如果不等于，则让Node节点等于栈顶节点，继续2过程
*4.如果Node节点等于栈顶节点，此时说明已经到了最底层叶子节点，退出循环
*5.判断栈是否为空，不为空的话，让Node节点等于栈顶节点，输出值，并弹出此节点，让Node节点等于下一个栈顶节点，进入2过程，循环此过程
*6.直到栈为空，结束此过程
* */
void LRD_ONE(){
stack<Node<T>*> s;
Node<T>* p = root;
s.push(p);
p->isFirst = false;
while(p || !s.empty()){
while(p){
if(p->pRight && p->pRight->isFirst){
p->pRight->isFirst = false;
s.push(p->pRight);
}
if(p->pLeft && p->pLeft->isFirst){
p->pLeft->isFirst = false;
s.push(p->pLeft);
}
if(s.empty())
break;
p == s.top() ? p = NULL : p = s.top();
}
if(!s.empty()){
p = s.top();
s.pop();
cout << p->value << ' ';
s.empty() ? p = NULL : p = s.top();
}
}
}
//后续遍历(非递归不需要辅助节点isFirst)
/*
*思路：程序保证满足两个条件：
*1.当一个节点有未访问过的子节点时，需要先访问其子节点
*2.不能重复访问一个节点的子节点
**/
void LRD_TWO(){
stack<Node<T>*> s;
s.push(root);
Node<T>* cur = NULL;
Node<T>* pre = NULL;
while(!s.empty()){
cur = s.top();
//下面这行代码可以满足上面两个条件
if((cur->pLeft == NULL && cur->pRight == NULL) || (pre != NULL && (pre == cur->pLeft || pre == cur->pRight))){
cout << cur->value << ' ';
s.pop();
pre = cur;
}else{
if(cur->pRight != NULL)
s.push(cur->pRight);
if(cur->pLeft != NULL)
s.push(cur->pLeft);
}
}
}
//按层打印
void treeShow(){
queue<Node<T>*> in;
Node<T>* last = NULL;
in.push(root);
while(!in.empty()){
while(!in.empty() && in.front() != last){
Node<T>* p = in.front();
in.pop();
cout << p->value << ' ';
if(p->pLeft){
if(!last) last = p->pLeft;
in.push(p->pLeft);
}
if(p->pRight){
if(!last) last = p->pRight;
in.push(p->pRight);
}
}
cout << endl;
last = NULL;
}
}
//按照层遍历模式进行序列化
//思路：广度优先搜索
string seriaByLayer(){
string result;
queue<Node<T>*> in;
Node<T>* last = NULL;
in.push(root);
while(!in.empty()){
while(!in.empty() && (!last || (last && in.front() != last))){
Node<T>* p = in.front();
in.pop();
if(p) {
result += (p->value+'0');
in.push(p->pLeft);
in.push(p->pRight);
if(p->pLeft && !last) last = p->pLeft;
if(p->pRight && !last) last = p->pRight;
}
else result += '#';
result += '!';
}
last = NULL;
}
return result;
}
//按照层遍历模式进行反序列化
//思路：
/*
* 1.把root放入队列
* 2.读字符串的值，
* 每次遇到一个有效的值，就把该值压入队列，
* 遇到一个空值或者有效的值，就将该值赋给队列首节点的左右子树，
* 当队列首节点的左右子树都赋值后，就弹出首节点
* 继续往下读字符串的值
* 3.循环此过程
* */
void deSeriaByLayer(string str){
if(str.length() < 1) return;
Node<T>* root = new Node<T>(str[0] - 48);
queue<Node<T>*> in;
in.push(root);
int index = 0; //0表示应该赋值给左子树，1表示应该赋值给右子树
for(int i = 1; i < int(str.length()); i++){
if(str[i] == '!') continue;
else if(str[i] == '#'){
if(index == 0) index = 1;
else if(index == 1) {
index = 0;
in.pop();
}
}
else{
Node<T>*& p = in.front();
Node<T>* node = new Node<T>(str[i] - 48);
in.push(node);
if(index == 0) {
p->pLeft = node;
index = 1;
}
else if(index == 1){
p->pRight = node;
in.pop();
index = 0;
}
}
}
this->root = root;
}
protected:
void mInsert(Node<T>*& root, T value){
if(!root){
Node<T>* node = new Node<T>(value);
root = node;
}
else if(value > root->value)
mInsert(root->pRight, value);
else if(value < root->value)
mInsert(root->pLeft, value);
}
void mRecursive(Node<T>* root){
if(root){
cout << root->value << ' ';//前序
mRecursive(root->pLeft);
//cout << root->value << ' ';//中序
mRecursive(root->pRight);
//cout << root->value << ' ';//后序
}
}
//将一个只知道根节点的树赋给指定的树
void setRootToTree(Node<T>* root){
this->root = root;
}
};
int main1(){
Tree<int> tree;
for(int i = 0; i < 100; i++){
if(i%2) tree.insert(i);
else tree.insert(-i);
}
tree.treeShow();
return 0;
}
