include<iostream>

include<stack>

include<queue>

include <list>

using namespace std;

/*
二叉树定义
*/
typedef struct BTNode{
char data;

struct BTNode *lchild;
struct BTNode *rchild;

}BTNode;

/*
构建二叉树
*/
BTNode *Create(BTNode T){
char ch;
cin >> ch;
if (ch == '#'){
T = NULL;
}
else{
T = (BTNode)malloc(sizeof(BTNode));
T->data = ch;
T->lchild = Create(T->lchild);
T->rchild = Create(T->rchild);
}
return T;
}

/*

• 先序遍历递归
  */
  void Preorder(BTNode *T){

  if (T != NULL){
  cout << T->data << " ";
  Preorder(T->lchild);
  Preorder(T->rchild);
  }
  }

/*

• 先序遍历非递归
  */

void Preorder2(BTNode *T){
stack<BTNode *> sta;
BTNode *p = T;
if (T != NULL){
sta.push(T);
while (!sta.empty()){
p = sta.top();
cout << p->data << " ";
sta.pop();

        if (p->rchild != NULL){
            sta.push(p->rchild);
        }

        if (p->lchild != NULL){
            sta.push(p->lchild);
        }
    }
}

}
/*

• 中序遍历递归
  */
  void Inorder(BTNode *T){
  if (T != NULL){
  Inorder(T->lchild);
  cout << T->data << " ";
  Inorder(T->rchild);
  }
  }

/*

• 中序遍历非递归
  */

void Inorder2(BTNode *T){
stack<BTNode *> sta;
BTNode *p = T;

if (T != NULL){
    while (!sta.empty() || p != NULL){
        while (p != NULL){
            sta.push(p);
            p = p->lchild;
        }
        if (!sta.empty()){
            p = sta.top();
            sta.pop();
            cout << p->data << "    ";
            p = p->rchild;
        }
    }
}

}
/*

• 后序遍历递归
  */

void Postorder(BTNode *T){
if (T != NULL){
Postorder(T->lchild);
Postorder(T->rchild);
cout << T->data << " ";
}
}

/*
后序遍历非递归
*/
void Postorder2(BTNode *T){
stack<BTNode *> sta;
BTNode *p = T;
BTNode *q=NULL;

while (p != NULL || !sta.empty())
{
    while (p != NULL){
        sta.push(p);
        p = p->lchild;
    }
    p = sta.top();              //访问栈顶，判断若有右节点则右节点进栈，否则出栈。
    if (p->rchild == NULL || p->rchild == q){
        cout << p->data << "    ";
        q = p;
        sta.pop();
        p = NULL;
    }
    else{
        p = p->rchild;
    }
}

}
/*
双栈法 后序遍历非递归
*/
void Postorder3(BTNode *T){
stack<BTNode *> sta,stb;
BTNode *p = T;
sta.push(p);
while (!sta.empty()){
p = sta.top();
sta.pop();
stb.push(p);

    if (p->lchild != NULL){
        sta.push(p->lchild);
    }

    if (p->rchild != NULL){
        sta.push(p->rchild);
    }

}

while (!stb.empty()){
    cout << stb.top()->data << "    ";
    stb.pop();
}

}

/*
层次遍历
*/

void Levelorder(BTNode *T){
queue<BTNode *> qu;
BTNode *p = T;
if (p!=NULL)
{
qu.push(p);
while (!qu.empty()){
p = qu.front();
cout << p->data << " " ;
qu.pop();
if (p->lchild != NULL){
qu.push(p->lchild);
}

        if (p->rchild!=NULL){
            qu.push(p->rchild);
        }
    }
}

}

/*

• 求二叉树的深度
  */
  int GetDepth(BTNode *T) {

  /* if(T!=NULL){
  ++n;
  n=GetDepth(T->lchild,n)>GetDepth(T->rchild,n) ? GetDepth(T->lchild,n) : GetDepth(T->rchild,n);
  }*/
  int ld, rd;
  if (T == NULL) {
  return 0;
  }
  else {
  ld = GetDepth(T->lchild);
  rd = GetDepth(T->rchild);

    return (ld > rd ? ld : rd) + 1;
  

  }
  }

/*

• 查找data为k的节点是否存在
  */

int FindData(BTNode *T, char k) {
//queue<BTNode *> qu;
BTNode p = T;
/ if(T!=NULL){
qu.push(p);
while(!qu.empty()){ //层次遍历查找
p=qu.front();
if(p->data==k){
return 1;
}
qu.pop();
if(p->lchild!=NULL){
qu.push(p->lchild);
}
if(p->rchild!=NULL){
qu.push(p->rchild);
}

}
return  0;
}*/

if (T == NULL) {
    return 0;
}
else {
    if (T->data == k) {        //先序遍历查找
        return 1;
    }

    if (FindData(T->lchild, k) > 0) {
        return 1;
    }
    else {
        return FindData(T->rchild, k);
    }

}

}

/*

• 输出先序遍历第K个节点的值
  */

void ShowK(BTNode T, int k) {
if (T != NULL) {
/ ++n; //定义全局变量n
if(n==k){
cout<<"第"<<k<<"个节点的值为: "<<T->data<<endl;
return;
}*/

    ShowK(T->lchild, k);
    ShowK(T->rchild, k);
}

}

/*

• 求二叉树的宽度
  */
  int GetWidth(BTNode *T) {

  queue<BTNode *> qu;
  int width = 1;
  int currwidth = 1;
  int nextwidth = 0;
  BTNode *p = T;
  if (T != NULL) {
  qu.push(p);
  while (!qu.empty()) {
  while (currwidth > 0) {
  p = qu.front();
  currwidth--;
  qu.pop();

            if (p->lchild != NULL) {
                qu.push(p->lchild);
                nextwidth++;
            }
            if (p->rchild != NULL) {
                qu.push(p->rchild);
                nextwidth++;
            }
        }
  
        if (nextwidth > width)
            width = nextwidth;
        currwidth = nextwidth;
        nextwidth = 0;
    }
  
    return width;
  

  }
  return 0;
  }

/*

• 二叉树第K层的节点个数
  */

int GetNum(BTNode *T, int k) {
queue<BTNode *> qu;
BTNode *p = T;
int currwidth = 1;
int nextwidh = 0;
int i = 0;
if (p != NULL) {
qu.push(p);
while (!qu.empty()) {
++i;
if (i == k) {
return currwidth;
}
while (currwidth > 0) {
p = qu.front();
currwidth--;
qu.pop();

            if (p->lchild != NULL) {
                qu.push(p->lchild);
                nextwidh++;
            }

            if (p->rchild != NULL) {
                qu.push(p->rchild);
                nextwidh++;
            }
        }
        currwidth = nextwidh;
        nextwidh = 0;
    }
}

return 0;

}

/*

• 求叶子节点个数
  */

int Getleaves(BTNode *T) {
queue<BTNode *> qu;
BTNode *p = T;
int n = 0;
if (p != NULL) {
qu.push(p);
while (!qu.empty()) {
p = qu.front();

        qu.pop();
        if (p->lchild != NULL) {
            qu.push(p->lchild);
        }

        if (p->rchild != NULL) {
            qu.push(p->rchild);
        }

        if (p->lchild == NULL && p->rchild == NULL) {
            ++n;
        }
    }
}
return n;

}

/*
*前序和中序重建二叉树
*/

BTNode *RecreateByPI(char *pre, char *in, int nodeNum) {

if (pre == NULL || in == NULL || nodeNum < 1) {
    return NULL;
}
int i = 0;
BTNode *T;
T = (BTNode *)malloc(sizeof(BTNode));

for (; i < nodeNum; ++i) {
    if (*(in + i) == *pre) {      //先序遍历的第一个节点为根节点
        break;
    }
}
T->data = *pre;

T->lchild = RecreateByPI(pre + 1, in, i);      //i左边递归建立左子树
T->rchild = RecreateByPI(pre + i + 1, in + i + 1, nodeNum - 1 - i);    //i右边递归建立右子树
return T;

}

/*

• 中序和后序重建树
  */

BTNode *RecreateByIL(char *last, char *in, int nodeNum) {
if (last == NULL || in == NULL || nodeNum < 1) {
return NULL;
}
int i = 0;
BTNode *T = (BTNode )malloc(sizeof(BTNode));
for (; i < nodeNum; ++i) {
if ((in + i) == *(last + nodeNum - 1)) {
break;
}
}

T->data = *(in + i);
T->lchild = RecreateByIL(last, in, i);
T->rchild = RecreateByIL(last + i, in + i + 1, nodeNum - i - 1);

return T;

}

/*

• 两个节点的公共祖先
  */

BTNode *FindAns(BTNode *T, char a, char b) {
if (T == NULL) {
return NULL;
}
if (T->data == a || T->data == b) {
return T;
}

BTNode *left = FindAns(T->lchild, a, b);
BTNode *right = FindAns(T->rchild, a, b);

if (left != NULL && right != NULL) {
    return T;
}

return (left != NULL) ? left : right;

}

/*

• 记录路径寻找公共祖先
  */

bool FindPath(BTNode *T, list<char> &li, char c) {
if (T == NULL) {
return false;
}
li.push_back(T->data);
if (T->data == c) {
return true;
}

bool find = FindPath(T->lchild, li, c) || FindPath(T->rchild, li, c);

if (find) {
    return true;
}
li.pop_back();       //在左树没找到,就弹出左树元素
return false;

}

char FindAns2(BTNode *T, char a, char b) {
if (T == NULL) {
return -1;
}

list<char> l1, l2;
bool b1 = FindPath(T, l1, a);
bool b2 = FindPath(T, l2, b);
char ans;

list<char>::iterator i1 = l1.begin();
list<char>::iterator i2 = l2.begin();
if (b1 && b2) {

    while (i1 != l1.end() && i2 != l2.end()) {
        if (*i1 == *i2) {
            ans = *i1;
        }
        else {
            break;
        }

         
        i1++;
        i2++;
    }
}

return ans;

}

/*

• 求二叉树节点的最大距离
  */

int mas = 0;

int MaxLegthTwoNode(BTNode *T) {

if (T == NULL) {
    return 0;
}

if (T->lchild == NULL && T->rchild == NULL) {
    return 0;
}

int a = GetDepth(T->lchild) + GetDepth(T->rchild);
int b = MaxLegthTwoNode(T->lchild);
int c = MaxLegthTwoNode(T->rchild);

int dis = (a > b ? a : b) > c ? (a > b ? a : b) : c;     //最大距离为左子树最大高度,或者右子树最大高度,或者左右深度之和

if (dis > mas) {
    mas = dis;
}
return dis;

}

/*

• 打印根节点到叶子节点路径
  */
  list<char> li;
  void PrintRToL(BTNode T) {
  /queue<BTNode *> qu;
  BTNode *p = T;
  if (p != NULL) {
  qu.push(p);
  while (!qu.empty()) {
  p = qu.front();

  qu.pop();
  if (p->lchild != NULL) {
  qu.push(p->lchild);
  }
  if (p->rchild != NULL) {
  qu.push(p->rchild);
  }

  if (p->lchild == NULL && p->rchild == NULL) {
  list<char> li;
  if (FindPath(T, li, p->data)) {
  list<char>::iterator it = li.begin(); //记录叶子节点路径方法
  while (it != li.end()) {
  cout << it << " ";
  it++;
  }
  }
  cout<<endl;
  }
  }
  }/

  if (T != NULL){
  li.push_back(T->data);
  if (T->lchild == NULL && T->rchild == NULL){
  list<char>::iterator it = li.begin();
  while (it != li.end()){
  cout << *it << " "; //打印栈或队列元素,但不出栈
  it++;
  }
  cout << endl;
  }

    PrintRToL(T->lchild);
    PrintRToL(T->rchild);
    li.pop_back();           //第三次访问的时候,出栈,意味着此节点的左右子树已经遍历完毕,包括叶子节点
  

  }
  }

/*
累加和为指定值的最长路径
*/
int s, i, tmp;
list<char> l2;
void printMaxSum(BTNode *T, int sum){
if (T != NULL){
li.push_back(T->data);
s += (T->data - '0');
++i;
if (s == sum){
if (tmp < i){
tmp = i;
l2.clear();

            if (!li.empty()){
                list<char>::iterator it = li.begin();
                while (it != li.end())
                {
                    l2.push_back(*it);
                    ++it; 
                }
            }
        }
    
    }

    printMaxSum(T->lchild,sum);
    printMaxSum(T->rchild,sum);

    s -= (li.back() - '0');
    --i;
    li.pop_back();
}

if (li.empty()){
    list<char>::iterator it = l2.begin();
    while (it != l2.end())
    {
        cout << *it << "    ";
        ++it;
    }
}

}

/*
按层打印和ZigZag打印
*/

void printZigZag(BTNode T){
queue<BTNode> qu;
stack<char> st;
BTNode *p = T;
int currWidth = 1;
int nextWidth = 0;
int i = 1;
if (p != NULL){
qu.push(p);

    while (!qu.empty()){
        if (i % 2 == 0){
            cout << "Level " << i << " from right to left : ";
        }
        else{
            cout << "Level " << i << " from left to right : ";
        }
        while (currWidth > 0){
            currWidth--;
            p = qu.front();
            qu.pop();
            if (i % 2 == 0){
                st.push(p->data);
            }
            else{
                cout << p->data << " ";
            }
        
            if (p->lchild != NULL){
                qu.push(p->lchild);
                nextWidth++;
            }

            if (p->rchild != NULL){
                qu.push(p->rchild);
                nextWidth++;
            }
        }
        while (!st.empty()){
            cout << st.top() << " ";
            st.pop();
        }
        cout << endl;
        ++i;
        currWidth = nextWidth;
        nextWidth = 0;
       
    }
}

}

void mmain(){
BTNode *T = NULL;
T = Create(T);

cout << "先序遍历:" << endl;
Preorder(T);
cout << endl;
/*
cout << "先序遍历非递归" << endl;
Preorder2(T);
cout << endl;

cout << "中序遍历:" << endl;
Inorder(T);
cout << endl;

cout << "中序遍历非递归:" << endl;
Inorder2(T);
cout << endl;

cout << "后序遍历:" << endl;
Postorder(T);
cout << endl;

cout << "后序遍历非递归:" << endl;
Postorder2(T);
cout << endl;

cout << "后序遍历非递归:" << endl;
Postorder3(T);
cout << endl;

cout << "层次遍历:" << endl;
Levelorder(T);
cout << endl;*/

printZigZag(T);

cout << endl;
system("pause");

}