BiTree.cpp

/*
The teacher asked us to use the stack to turn the recursive algorithm into non-recursive, so I wrote this.🤣
#1 
*/
#include <algorithm>
#include <iostream>
#include <memory>
#include <cstdlib>
#include <stack>
using namespace std;
/********************************
已知二叉树的逻辑结构如下：
          A
         / \
        B   D
         \
          C
请完成：
1根据先缀串建立二叉树
2输出先序、中序和后序遍历的结果
3输出叶子节点的数量
4输出二叉树的深度
5输出非递归中序遍历的结果

输入用例:AB#C##D##
输出用例:
         ABCD
         BCAD
         CBDA
         2
         3
         BCAD
用例说明：
1输入用例中'#'表示空树
2输出用例的前三行分别代表三种遍历的结果
3输出用例的第四行表示叶子节点的数量
4输出用例的第五行表示树的深度
5输出用例的第六行表示非递归中序遍历结果

注意：建议在本用例基础上再自行设计1个复杂一点的用例作为测试
*********************************/
struct BiTNode//二叉树结点结构
{
    string data;
    std::shared_ptr<BiTNode> lchild, rchild;
};
using BiTree = std::shared_ptr<BiTNode>;
void CreateBiTree(BiTree &T)//根据先缀串建树
{
    /**请完善该函数**/
    char ch;
    cin >> ch;
    if (ch == '#') {
        T = nullptr;
        return;
    }
    T = std::make_shared<BiTNode>();
    T->data = ch;
    CreateBiTree(T->lchild);
    CreateBiTree(T->rchild);
}

void PreOrderTraver(BiTree T)//先序遍历
{
    /**请完善该函数**/
    if (T == nullptr) return;
    cout << T->data;
    PreOrderTraver(T->lchild);
    PreOrderTraver(T->rchild);
}
void InOrderTraver(BiTree T)//中序遍历
{
    /**请完善该函数**/
    if (T == nullptr) return;
    InOrderTraver(T->lchild);
    cout << T->data;
    InOrderTraver(T->rchild);
}
void PostOrderTraver(BiTree T)//后序遍历
{
    /**请完善该函数**/
    if (T == nullptr) return;
    PostOrderTraver(T->lchild);
    PostOrderTraver(T->rchild);
    cout << T->data;
}
void CountLeaf(BiTree T,int &c)//计算叶子节点数量
{
    /**请完善该函数**/
    if (T == nullptr) return;
    if (T->lchild == nullptr && T->rchild == nullptr) {
        ++c;
        return;
    }
    CountLeaf(T->lchild, c);
    CountLeaf(T->rchild, c);
}

int Depth(BiTree T) //计算二叉树的深度
{
    /**请完善该函数**/
    if (T == nullptr) return 0;
    return 1 + std::max(Depth(T->lchild), Depth(T->rchild));
}
BiTree GoFarLeft(BiTree T,stack<BiTree> &S) //找T的最左下结点
{
    if(!T) return nullptr;
    while(T->lchild)
    {
        S.push(T);
        T=T->lchild;
    }
    return T;
}
void Inorder_I(BiTree T)
{
    /**请完善该函数，需要用到的GoFarLeft函数上面已经定义完毕**/
    stack<BiTree> s;
    BiTree tree = GoFarLeft(T, s);
    while (tree != nullptr) {
        cout << tree->data;
        if (tree->rchild != nullptr)
            tree = GoFarLeft(tree->rchild, s);
        else if (!s.empty()) {
            tree = s.top();
            s.pop();
        }
        else
            tree = nullptr;
    }
}
void Inorder_I_ng(BiTree T)
{
    enum struct jmp_flag {NONE, FIRST, SECOND};
    stack<BiTree> args_stack;
    stack<jmp_flag> status_stack;
    // stack<> local_stack;

    args_stack.push(T);
    status_stack.push(jmp_flag::NONE);
    while (!args_stack.empty()) {
    jmp_flag jflag = status_stack.top();
    status_stack.pop();
    switch (jflag) {
        case jmp_flag::NONE:
        if (args_stack.top() == nullptr) break;

        args_stack.push(args_stack.top()->lchild);
        status_stack.push(jmp_flag::FIRST);
        status_stack.push(jmp_flag::NONE);
        continue;
        case jmp_flag::FIRST:

        cout << args_stack.top()->data;

        args_stack.push(args_stack.top()->rchild);
        status_stack.push(jmp_flag::SECOND);
        status_stack.push(jmp_flag::NONE);
        continue;
        case jmp_flag::SECOND:
        ;
    }
    args_stack.pop();
    }
}
int main()
{
    BiTree T;
    CreateBiTree(T);//建树
    PreOrderTraver(T);//先序遍历
    cout<<endl;
    InOrderTraver(T);//中序遍历
    cout<<endl;
    PostOrderTraver(T);//后序遍历
    cout<<endl;
    int c=0;//叶子数量
    CountLeaf(T,c);//计算叶子数量
    cout<<c;
    cout<<endl;
    cout<<Depth(T);//计算深度并输出
    cout<<endl;
    Inorder_I_ng(T);//中序的非递归遍历
    return 0;
}