二叉树的递归和非递归遍历

// 本次练习的是  二叉树的  递归和非递归  遍历   以及二叉树的  节点数  高度  叶子节点数   和查找功能  
//如果要是变量在函数栈回归时不回归原值，则可以用引用
//


#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stack>
#include<queue>
using namespace std;


template<class T>
struct BinaryTreeNode
{
    BinaryTreeNode(const T& date)
    :_date(date)
    , _left(NULL)
    , _right(NULL)
    {}

    T _date;
    BinaryTreeNode<T>* _left;
    BinaryTreeNode<T>* _right;
};

template<class T>
class BinaryTree
{
public:
    BinaryTree(const T* date,size_t size)
    {
        size_t index = 0;      
        _root = _CreateBinaryTree(date, index, size);
    }

    ~BinaryTree()
    {
        Destory(_root);
    }

    void PreOrder()
    {
        _PreOrder(_root);
        cout << endl;
    }

    void MiddleOrder()
    {
        _MiddleOrder(_root);
        cout << endl;
    }

    void LastOrder()
    {
        _LastOrder(_root);
        cout << endl;
    }

    void Size()
    {
        cout<<_Size(_root)<<endl;
    }

    void Hight()
    {
        cout << _Hight(_root) << endl;
    }

    void LeafOfNumber()
    {
        cout<< _LeafOfNumber(_root)<<endl;
    }

    BinaryTreeNode<T>* Find(const T& data)
    {
        return _Find(_root,data);
    }

    void PrevOrder_Non_R()
    {
        _PrevOrder_Non_R(_root);
        cout << endl;
    }

    void MiddleOrder_Non_R()
    {
        _MiddleOrder_Non_R(_root);
        cout << endl;
    }

    void LastOrder_Non_R()
    {
        _LastOrder_Non_R(_root);
        cout << endl;
    }

    void Destory(BinaryTreeNode<T>* root)
    {
        if (root != NULL)
        {
            Destory(root->_left);
            Destory(root->_right);
            delete root;
        }
    }

protected:

    BinaryTreeNode<T>* _CreateBinaryTree(const T* date, size_t& index, size_t size)//注意   index 要用  引用
    {
        if (index >= size || date[index] == '#')
        {    
            return NULL;
        }
            
        BinaryTreeNode<T>* root = new BinaryTreeNode<T>(date[index]);  
        root->_left = _CreateBinaryTree(date, ++index, size);               //要用前置加加而不能用后置加加  因为后置加加会产生一个临时变量
        root->_right = _CreateBinaryTree(date, ++index, size);  
        
        return root;  
    }

    void _PreOrder(BinaryTreeNode<T>* root)
    {
        if (root == NULL)
        {
            return;
        }

        cout << root->_date << "  ";
        
        _PreOrder(root->_left);
        _PreOrder(root->_right);
    }

    void _MiddleOrder(BinaryTreeNode<T>* root)
    {
        if (root == NULL)
        {
            return;
        }

        _MiddleOrder(root->_left);
        cout << root->_date<<"  ";
        _MiddleOrder(root->_right);
    }

    void _LastOrder(BinaryTreeNode<T>* root)
    {
        if (root == NULL)
        {
            return;
        }

        _LastOrder(root->_left);
        _LastOrder(root->_right);
        cout << root->_date << "  ";
    }

    int _Size(BinaryTreeNode<T>* root)
    {
        if (root == NULL)
        {
            return 0;
        }

        return _Size(root->_left) + _Size(root->_right) + 1;
    }

    int _Hight(BinaryTreeNode<T>* root)      //求二叉树的高度
    {
        if (root == NULL)
        {
            return 0;
        }

        int left = _Hight(root->_left) ;
        int right = _Hight(root->_right);

        return (left > right ? (left + 1) :( right + 1));
    }

    int _LeafOfNumber(BinaryTreeNode<T>* root)
    {
        if (root == NULL)
        {
            return 0;
        }

        if (root->_left == NULL && root->_right == NULL)
        {
            return 1;
        }
        return _LeafOfNumber(root->_left) + _LeafOfNumber(root->_right);
        
    }

    BinaryTreeNode<T>* _Find(BinaryTreeNode<T>* root,const T& data)
    {
        if (root == NULL)
        {
            return NULL;
        }

        if (root->_date == data)
        {
            return root;
        }

        BinaryTreeNode<T>* left =  _Find(root->_left,data);
        if (left != NULL)
        {
            return left;
        }
        BinaryTreeNode<T>* right =  _Find(root->_right,data);
        if (right != NULL)
        {
            return right;
        }
    }
    /*
    void _PrevOrder_Non_R(BinaryTreeNode<T>* root)
    {
        stack<BinaryTreeNode<T>*> s;
        BinaryTreeNode<T>* cur = root;

        while (!s.empty() || cur != NULL)
        {
            s.push(cur);
            BinaryTreeNode<T>* top = s.top();
            cout << top->_date << "  ";

            cur = top->_left;
            
            if (cur == NULL)
            {
                s.pop();
                if (s.top()->_right != NULL)
                {
                    cur = s.top()->_right;
                }
                else
                {
                    s.pop();
                }        
            }
        }
    }
    */

    void _PrevOrder_Non_R(BinaryTreeNode<T>* root)
    {
        stack<BinaryTreeNode<T>* > s;       //栈中每个节点都会存放一次     下面只需把一个节点的 根  左 右 访问一次就行
        BinaryTreeNode<T>* cur = root;

        if (cur != NULL)
        {
            s.push(cur);
        }

        while (!s.empty())
        {
            BinaryTreeNode<T>* top = s.top();
            cout << top->_date << "  ";
            s.pop();

            if (top->_right != NULL)
            {
                s.push(top->_right);
            }

            if (top->_left != NULL)
            {
                s.push(top->_left);
            }
        }
    }
    void _MiddleOrder_Non_R(BinaryTreeNode<T>* root)
    {
        stack<BinaryTreeNode<T>* > s;
        BinaryTreeNode<T>* cur = root;

        while (!s.empty() || cur != NULL)
        {
            while (cur != NULL)        
            {
                s.push(cur);
                cur = cur->_left;
            }

            if (!s.empty())
            {
                BinaryTreeNode<T>* top = s.top();
                s.pop();
                cout << top->_date << "  ";
                cur = top->_right;
            }
        }
    }

    void _LastOrder_Non_R(BinaryTreeNode<T>* root)
    {
        stack<BinaryTreeNode<T>*> s;
        BinaryTreeNode<T>* cur = root;
        BinaryTreeNode<T>* prev = NULL;

        while (cur != NULL || !s.empty())
        {
            while (cur != NULL)
            {
                s.push(cur);
                cur = cur->_left;    //此时左已遍历完  
            }
            
            BinaryTreeNode<T>* top = s.top();

            if (top->_right == NULL || top->_right == prev)  //这两种情况都表示  1. 右  已遍历完
            {
                cout << top->_date << "  ";
                prev = top;
                s.pop();
            }
            else       // 2.右还没有遍历完
            {
                cur = top->_right;
            }
        }                    
        cout << endl;
    }


protected:
    BinaryTreeNode<T>* _root;
};


void Test1()
{
    int arr[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6};
    
    BinaryTree<int> t2(arr, 10);
    cout << "前序：" << endl;
    t2.PreOrder();
    t2.PrevOrder_Non_R();

    cout << "中序：" << endl;
    t2.MiddleOrder();
    t2.MiddleOrder_Non_R();

    cout << "后序：" << endl;
    t2.LastOrder();
    t2.LastOrder_Non_R();

    cout << "节点数：" << endl;
    t2.Size();
    
    cout << "高度：" << endl;
    t2.Hight();

    cout << "叶子节点数：" << endl;
    t2.LeafOfNumber();

    BinaryTreeNode<int>* find = t2.Find(3);
    cout << find->_date << endl;
}


int main()
{
    Test1();
    return 0;
}