二叉树的实现_遍历_重构_树形显示

//测试数据 
//1 2 4 7 -1 -1 -1 5 -1 -1 3 -1 6 -1 -1
//1 2 4 11 -1 22 -1 -1 -1 5 -1 -1 3 6 -1 -1 7 -1 -1


#include <iostream>
#include <cstring>
using namespace std;

template<typename T>
struct BinaryNode
{ 
    T element;
    BinaryNode<T> *left;
    BinaryNode<T> *right;

    BinaryNode() : element(0), left(nullptr), right(nullptr) { } 
    BinaryNode(const T &theElement, BinaryNode *lt, BinaryNode *rt)
        : element(theElement), left(lt), right(rt) {}
    
};


template<typename T>
class BinarySearchTree
{
public:
    BinarySearchTree() {
        root = nullptr;
    }
    BinarySearchTree(const BinarySearchTree& rhs) {  //复制构造函数
        root = clone(rhs.root);
    }
    ~BinarySearchTree();
    
    void RootCreate(const T& end); //创建根结点的以下结点 
    
    bool contains(const T& x) const;

    bool getNode(const T& e, const T&sub) {      
        if (getNode(e, root) != nullptr) {
            getNode(e, root)->element = sub;  //得到元素为e的结点 
            return true;
        }
        return false;        
    }
    
    //求父亲的值 
    T getParents(const T& e) const {
        return getParents(root, e);
    }

    bool isEmpty() const {
        if (root == nullptr)
            return true;   
        return false;     
    }                      

    void PreprintTree() const {
        PreprintTree(root);
    }

    void InprintTree() const {
        InprintTree(root);
    }

    void PostprintTree() const {
        PostprintTree(root);
    }

    void LevelprintTree() const {
        LevelprintTree(root);
    }

    void PreprintTree_N() const {
        PreprintTree_N(root);
    }

    void InprintTree_N() const {
        InprintTree_N(root);
    }

    void PostprintTree_N() const {
        PostprintTree_N(root);
    }

    void DisplayTreeShape(int level = 1) const {
        DisplayTreeShape(root, level);
    }
    
    void makeEmpty();

    void remove(const T &x);

    int Depth();
    int CountLeaf() {
        BinaryNode<T> *p = root;
        int count = 0;
        CountLeaf(p, count);
        return count;
    }

    const BinarySearchTree& operator = (const BinarySearchTree& rhs);

private:

    BinaryNode<T> *root;                      //指向树根结点的指针
    
    int Create(BinaryNode<T> *p, T end, int flag);

    void remove(const T & x, BinaryNode<T> * & t, int rh);

    bool contains(const T & x, BinaryNode<T> *t) const;

    BinaryNode<T> * getNode(const T &x, BinaryNode<T> *t);
    
    T getParents(BinaryNode<T> *p, const T& e) const;

    void makeEmpty(BinaryNode<T> * & t);
    //利用 递归 算法 计算树的 深度 
    int Depth(BinaryNode<T> * t, int level, int &depth);
    //利用 递归 算法 计算树的 高度
    void CountLeaf(BinaryNode<T> * t, int &count);


    void PreprintTree(BinaryNode<T> * t) const;           //先序遍历 
    void InprintTree(BinaryNode<T> *t) const;             //中序遍历   
    void PostprintTree(BinaryNode<T> * t) const;          //后序遍历
    void LevelprintTree(BinaryNode<T> * t) const;          //层次遍历 

    void PreprintTree_N(BinaryNode<T> * t) const;          //非递归先序遍历
    void InprintTree_N(BinaryNode<T> * t) const;           //非递归中序遍历二叉树 
    void PostprintTree_N(BinaryNode<T> * t) const;         //非递归后序遍历二叉树 
    void DisplayTreeShape(BinaryNode<T> *bt, int level) const;    //二叉树的树形显示算法 


    BinaryNode<T> * clone(BinaryNode<T> * t) const;
};

template<typename T>
bool BinarySearchTree<T>::contains(const T& x) const
{
    return contains(x, root);
}

template<typename T>
bool BinarySearchTree<T>::contains(const T & x, BinaryNode<T> *t) const
{
    bool judge;
    if (t) {
        if (t->element == x)
            return true;
        judge = contains(x, t->left);
        if (judge) return true;
        judge = contains(x, t->right);
        if (judge) return true;
    }
    return false;
}

template<typename T>
BinaryNode<T>* BinarySearchTree<T>::getNode(const T & x, BinaryNode<T> *t)
{
    BinaryNode<T>* ptemp;
    if (t)
    {
        if (t->element == x) return t;
        ptemp = getNode(x, t->left);
        if (ptemp) return ptemp;
        ptemp = getNode(x, t->right);
        if (ptemp) return ptemp;    
    } 
    return nullptr;
}

template<typename T>
T BinarySearchTree<T>::getParents(BinaryNode<T> *p, const T& e) const
{
    const int maxn = 1024;
    BinaryNode<T> *Queue[maxn], *ptemp;
    int front = 0, rear = 0;
    if (p != nullptr && e != root->element) //为空，没有父节点, 且不为根结点 
    {
        Queue[rear++] = p;               //让根结点入队列,rear加1 
        while (front != rear)            //栈不为空 
        {
            ptemp = Queue[front++];      //将队列的结点依次出队
            if ((ptemp->left && ptemp->right->element == e )|| (ptemp->right && ptemp->left->element == e))
                return ptemp->element;   //如果是，则返回 
            else 
            {
                if (ptemp->left) Queue[rear++] = ptemp->left;    //左结点不为空，则入栈 
                if (ptemp->right) Queue[rear++] = ptemp->right;  //右不为空，则入栈 
            }
        }
    }
    return -1; 
}


template<typename T>
void BinarySearchTree<T>::RootCreate(const T& end)       //创建二叉树 
{
    cout << "请按先序序列的顺序输入二叉树,-1为空指针域标志：" << endl;
    BinaryNode<T> *p;
    int x;
    cin >> x;
    if (x == end) return;
    p = new BinaryNode<T>(x, nullptr, nullptr);
    root = p;
    Create(p, end, 1);
    Create(p, end, 2);
}

template<typename T>
int BinarySearchTree<T>::Create(BinaryNode<T> *p, T end, int flag)
{
    BinaryNode<T> *t;
    T x;
    cin >> x;
    if (x != end)
    {//子节点的左右结点先赋值 
        t = new BinaryNode<T>(x, nullptr, nullptr);
        if (flag == 1) p->left = t;    //标志i=1,代表左孩子
        if (flag == 2) p->right = t;   //i=2结点为右孩子 
        Create(t, end, 1);             //递归调用，直到 x == end 
        Create(t, end, 2);
    }
    return 0;
}

template<typename T>
void BinarySearchTree<T>::remove(const T &x)
{
    remove(x, root, 1);
    remove(x, root, 2);
}

/************************************************************************/
/* x is item to remove                                                  */
/* t is the node that roots the subtree                                 */
/* Set the new root of the subtree                                      */
/* 1.结点是一片树叶时 -- 可被立即删除*/
/* 2.结点有一个儿子, 则该结点可以在其父节点调整他的链 以绕过该结点后被删除 */
/* 3.结点有两个儿子, 则其右子树的最小数据代替该结点的数据，并递归删除那个结点 */
/* 注: 右子树中的最小的结点不可能有左结点                               */
/************************************************************************/
template<typename T>
void BinarySearchTree<T>::remove(const T &x, BinaryNode<T> * & t, int rh)
{
    if (t == nullptr) return;
    if (t->element == x && rh == 1)
    {
        makeEmpty(t->left);
    }
    else {
        makeEmpty(t->right);
    }
    remove(x, t->left, rh);
    remove(x, t->right, rh);
}

/************************************************************************/
///* Destructor for the tree
/************************************************************************/
template<typename T>
BinarySearchTree<T>::~BinarySearchTree()
{
    makeEmpty();
}

template<typename T>
void BinarySearchTree<T>::makeEmpty()       //公有函数
{
    makeEmpty(root);
}

/************************************************************************/
///* Internal method to make subtree empty -- 私有函数
/************************************************************************/
template<typename T>
void BinarySearchTree<T>::makeEmpty(BinaryNode<T> * & t)
{
    if (t != nullptr)
    {
        makeEmpty(t->left);
        makeEmpty(t->right);
        delete t;
    }
    t = nullptr;
}

/************************************************************************/
///* Deep copy
/************************************************************************/
template<typename T>
const BinarySearchTree<T>& BinarySearchTree<T>::operator = (const BinarySearchTree &rhs)
{
    if (this != &rhs) {
        makeEmpty();
        root = clone(rhs.root);
    }
    return *this;
}

/************************************************************************/
///* Internal method to clone subtree.  --  递归复制结点
/************************************************************************/
template<typename T>
BinaryNode<T>* BinarySearchTree<T>::clone(BinaryNode<T> * t) const
{
    if (t == nullptr)
        return nullptr;
    return new BinaryNode<T>(t->element, clone(t->left), clone(t->right));
}

//利用递归计算树的深度 
template<typename T>
int BinarySearchTree<T>::Depth()
{
    BinaryNode<T> *t = root;
    int depth = 0;
    if (root == nullptr)
        return 0;
    Depth(t, 1, depth);
    return depth;
}

//由public的函数Depth调用, 完成树的深度的计算，p是根结点，Level是层，depth用来返回树的深度 
template<typename T>
int BinarySearchTree<T>::Depth(BinaryNode<T> *t, int level, int &depth)
{
    if (level > depth) depth = level;                  //层数
    if (t->left) Depth(t->left, level + 1, depth);     //递归遍历左子树，且层数加1 
    if (t->right) Depth(t->right, level + 1, depth);   //递归遍历右子树, 且层数加1 
    return 0;
}

template<typename T>
//利用 递归 算法 计算树的 高度
void BinarySearchTree<T>::CountLeaf(BinaryNode<T> * t, int &count)
{
    if (t == nullptr) return;               //为空时，退出

    //    CountLeaf(t->left, count);
    //    CountLeaf(t->right, count); 
    if (!(t->left) && !(t->right)) {        //儿子为空时 
        count++;
    }
    CountLeaf(t->left, count);
    CountLeaf(t->right, count);
}


/************************************************************************/
///* printTree   ---    前序遍历 
/************************************************************************/
template<typename T>
void BinarySearchTree<T>::PreprintTree(BinaryNode<T> * t) const
{
    if (t != nullptr) {
        cout << t->element << ' ';
        PreprintTree(t->left);
        PreprintTree(t->right);
    }
}

//中序遍历 
template<typename T>
void BinarySearchTree<T>::InprintTree(BinaryNode<T> * t) const
{
    if (t != nullptr) {
        InprintTree(t->left);
        cout << t->element << ' ';
        InprintTree(t->right);
    }
}

//后序遍历 
template<typename T>
void BinarySearchTree<T>::PostprintTree(BinaryNode<T> * t) const
{
    if (t != nullptr) {
        PostprintTree(t->left);
        PostprintTree(t->right);
        cout << t->element << ' ';
    }
}

//利用队列Queue层次遍历二叉树 
template<typename T>
void BinarySearchTree<T>::LevelprintTree(BinaryNode<T> * t) const
{
    const int maxn = 1024;
    BinaryNode<T> *Queue[maxn];                          //一维数组作为队列 
    BinaryNode<T> *tmp;
    int front = 0, rear = 0;                             //队列初始为空 
    if (root) {
        Queue[rear++] = root;                            //二叉树的根结点指针入队列 
        while (front != rear)
        {
            tmp = Queue[front++];                        //队首的元素出队列
            if (tmp) cout << tmp->element << ' ';        //输出结点值
            if (tmp->left) Queue[rear++] = tmp->left;
            if (tmp->right) Queue[rear++] = tmp->right;
        }
    }
}

//先序遍历 (DLR)
template<typename T>
void BinarySearchTree<T>::PreprintTree_N(BinaryNode<T> * t) const          //非递归先序遍历
{
    const int maxn = 1024;
    BinaryNode<T> *Stack[maxn];
    int top = 0;
    BinaryNode<T> *tmp = root;            //将根结点的指针赋值给tmp 

    //    cout << "Debug :
";
    while (tmp || top != 0)
    {
        //        cout << "debug : 
";
        while (tmp) {
            cout << tmp->element << ' ';
            Stack[top++] = tmp;           //右孩子入栈 
            tmp = tmp->left;              //一直递归到最左的结点 
        }
        if (top) {                        //栈不为空, 从栈中取出一个结点指针 
            tmp = Stack[--top];
            tmp = tmp->right;
        }
    }
}

//中序非递归遍历二叉树 (LDR)
template<typename T>
void BinarySearchTree<T>::InprintTree_N(BinaryNode<T> * t) const           //非递归中序遍历二叉树 
{
    const int maxn = 1024;
    BinaryNode<T> *Stack[maxn];
    int top = 0;
    BinaryNode<T> *tmp = root;

    while (tmp || top != 0)
    {
        while (tmp) {                  //迭代到最左的子树 
            Stack[top++] = tmp;        //左子树入栈 
            tmp = tmp->left;
        } 
        if (top) {
            tmp = Stack[--top];            //出栈最左的子树 
            cout << tmp->element << ' ';   //输出该元素 
            tmp = tmp->right;              //并指向右结点开始迭代 
        }
    }

}

//非递归后序遍历二叉树 (LRD)
template<typename T>
void BinarySearchTree<T>::PostprintTree_N(BinaryNode<T> * t) const
{
    const int maxn = 1024;
    struct Mystack {
        BinaryNode<T> * link;
        int flag;
    };

    Mystack Stack[maxn];
    BinaryNode<T> * p = root, *tmp;

    if (root == nullptr) return;

    int top = -1,                  //栈顶初始化 
        sign = 0;                  //为结点tmp 的标志量 

    while (p != nullptr || top != -1)
    {
        while (p != nullptr)       //遍历到最左 
        {
            Stack[++top].link = p; //并且一直入栈 
            Stack[top].flag = 1;   //设置flag为第一次入栈 
            p = p->left;
        }

        if (top != -1)
        {
            tmp = Stack[top].link;
            sign = Stack[top].flag;
            top--;                 //出栈 

            if (sign == 1)         //结点第一次进栈 
            {
                top++;
                Stack[top].link = tmp;
                Stack[top].flag = 2;            //标记为第二次出栈 
                p = tmp->right;
            }
            else {                                //第二次出栈就输出 
                cout << tmp->element << ' ';      //访问该结点数据域 
                p = nullptr;
            }
        }

    }

}

//树形显示二叉树，也是中序遍历 
template<typename T>
void BinarySearchTree<T>::DisplayTreeShape(BinaryNode<T> *bt, int level) const
{    
    if (bt)                                         //二叉树的树形显示算法
    {
        DisplayTreeShape(bt->right, level + 1);     //空二叉树不显示
        cout << endl;
        for (int i = 0; i < level - 1; i++)
            cout << "   ";                            //确保在第level列显示结点 
        cout << bt->element;
        DisplayTreeShape(bt->left, level + 1);        //显示左子树
    }
}

//先序(preorder) -- 中序(inorder)  ===>   得到后序遍历(postorder)
//先序为了得到根结点，  中序为了得到左右两个子序列 
template<typename T>
void BinaryTreeFromOrderings(const T *inorder, const T *preorder, int length)
{
    if (length == 0) return;
    T node_value = *preorder;                 //得到先序序列的第一个元素 ==> 根结点 
    int rootIndex = 0;                        //根结点的索引 
    for (; rootIndex < length; rootIndex++) { //在中序序列中，遍历到(先序遍历的)根结点的地方终止 
        if (inorder[rootIndex] == *preorder)  
            break;
    }

    /******************* Left Root Right *********************/
    //left   -- 中序遍历开始的位置，后序遍历开始的位置 可以遍历的总长度 
    BinaryTreeFromOrderings(inorder, preorder + 1, rootIndex);
    //Right
    BinaryTreeFromOrderings(inorder + rootIndex + 1, preorder + rootIndex + 1, length - (rootIndex + 1));    
    cout << node_value << ' ';
}


int main()
{
    int testData;
    BinarySearchTree<int> test;
    cout << "创建树: 
";
    test.RootCreate(-1);

    cout << "
全部元素为: 
";
    test.PreprintTree();

    cout << endl;

    cout << "输入查找元素: 
";
    cin >> testData;
    cout << "是否包含 " << testData << " : " << test.contains(testData) << endl;
    
    cout << testData << "的父亲是:	";
    cout << test.getParents(testData) << endl;

    cout << endl;
    cout << "输入修改元素: 
";
    cin >> testData;
    if (test.getNode(testData, 1000))
        cout << "OK !
";
    test.PreprintTree();
    cout << "
";

    cout << "
树的高度: " << test.Depth() << endl;
    cout << "
叶子的个数: " << test.CountLeaf() << endl;
    cout << endl;

    cout << "先序遍历树元素: 
";
    test.PreprintTree();

    cout << "

中序遍历树元素: 
";
    test.InprintTree();

    cout << "

后序遍历树元素: 
";
    test.PostprintTree();

    cout << "

层次遍历树元素: 
";
    test.LevelprintTree();

    cout << "

先序遍历树元素(非递归): 
";
    test.PreprintTree_N();

    cout << "

中序遍历树元素(非递归): 
";
    test.InprintTree_N();

    cout << "

后序遍历树元素(非递归): 
";
    test.PostprintTree_N();

    cout << "

二叉树的树形显示算法(下面是逆时针旋转了90°的树): 
";
    test.DisplayTreeShape(43);

    cout << endl;
    
    const char* pr = "ABCDEFGHI";            //GDAFEMHZ
    const char* in = "BCAEDGHFI";            //ADEFGHMZ
    BinaryTreeFromOrderings(in, pr, strlen(pr));
    
    cout << endl;    
    
    return 0;
}