数据结构—二叉树的三种遍历方式

•  树的概念：

        树是n(n>=0)个有限个数据的元素集合，形状像一颗倒过来的树。

•  二叉树的概念：

         二叉树是一颗特殊的树，二叉树每个节点最多有两个孩子结点，分别称为左孩子、右孩子

• 遍历二叉树三种种方式(递归实现，非递归实现)：

       测试用例

       int array[10]={1,2,3,'#','#','4','#','#',5,6};

         前序遍历(先根遍历):（1）：先访问根节点； （2）：前序访问左子树；（3）：前序访问右子树； 【1 2 3 4 5 6】
        中序遍历: （1）：中序访问左子树；（2）：访问根节点； （3）：中序访问右子树； 【3 2 4 1 6 5】
        后序遍历(后根遍历):（1）：后序访问左子树；（2）：后序访问右子树；（3）：访问根节点； 【3 4 2 6 5 1】

 

struct BinaryTreeNode
{
    T _data;
    BinaryTreeNode<T>* _left;
    BinaryTreeNode<T>* _right;

    BinaryTreeNode(const T& x)
        :_data(x)
        , _left(NULL)
        , _right(NULL)
    {}
};
template<class T>
class BinaryTree
{
public:
    BinaryTree()
        :_root(NULL)
    {}

    BinaryTree(const T* a, size_t size)
    {
        size_t index = 0;
        _root = _CreateTree(a, size, index);
    }

    ~BinaryTree()
    {
        _Destroy(_root);
        _root = NULL;
    }

    BinaryTree(const BinaryTree<T>& t)
    {
        _root = _Copy(t._root);
    }
    BinaryTree<T>& operator= (BinaryTree<T> t)
    {
        swap(_root, t._root);

        return *this;
    }
    //递归前序
    void PrevOrder(BinaryTreeNode<T>* root)
    {
        if (root == NULL)
            return;

        cout << root->_data << " ";
        PrevOrder(root->_left);
        PrevOrder(root->_right);
    }
    //非递归前序
    void PrevOrder_NonR()
    {
        stack<BinaryTreeNode<T>*> s;
        if (_root)
            s.push(_root);

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

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

            if (top->_left)
            {
                s.push(top->_left);
            }
        }

        cout << endl;
    }
    //递归中序
    void MidOrder(BinaryTreeNode<T>* root)
    {
        if (root == NULL)
            return;
        MidOrder(root->_left);
        cout << root->_data << " ";
        MidOrderr(root->_right);
    }
    //非递归中序
    void MidOrder_NonR()
    {
        stack<BinaryTreeNode<T>*> s;
        BinaryTreeNode<T>* cur = _root;
        while (cur || !s.empty())
        {
             将cur指向树的所有左路节点入栈
            while (cur)
            {
                s.push(cur);
                cur = cur->_left;
            }
            if (!s.empty())
            {
                BinaryTreeNode<T>* top = s.top();
                cout << top->_data << " ";
                s.pop();

                cur = top->_right;
            }
        }
      cout << endl;
    }
    //递归后序
    void PostOrder(BinaryTreeNode<T>* root)
    {
        if (root == NULL)
            return;
        PostOrder(root->_left);
        PostOrder(root->_right);
        cout << root->_data << " ";
    }
    //非递归后序
    void PostOrder_NonR()
    {
        stack<BinaryTreeNode<T>*> s;
        BinaryTreeNode<T>* cur = _root;
        BinaryTreeNode<T>* prevVisited = NULL;
        while (cur || !s.empty())
        {
            while (cur)
            {
                s.push(cur);
                cur = cur->_left;
            }

            BinaryTreeNode<T>* top = s.top();
            if (top->_right == NULL
                || top->_right == prevVisited)
            {
                cout << top->_data << " ";
                prevVisited = top;
                s.pop();
            }
            else
            {
                cur = top->_right;
            }
        }

        cout << endl;
    }
    void Size(BinaryTreeNode<T>* root, int& size)
    {
        if (root == NULL)
            return;
        else
            ++size;

        Size(root->_left, size);
        Size(root->_right, size);
    }

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

        int leftDepth = Depth(root->_left);
        int rightDepth = Depth(root->_right);

        return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
    }
    void GetLeafNum(BinaryTreeNode<T>* root, int& num)
    {
        if (root == NULL)
            return;

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

        GetLeafNum(root->_left, num);
        GetLeafNum(root->_right, num);
    }

    BinaryTreeNode<T>* Find(BinaryTreeNode<T>* root,const T& x)
    {
        if (root == NULL)
        {
            return NULL;
        }
        else if (root->_data == x)
        {
            return root;
        }
        else
        {
            BinaryTreeNode<T>* ret = Find(root->_left, x);
            if (ret)
                return ret;
            else
                return Find(root->_right, x);
        }
    }
    size_t GetKlevel(BinaryTreeNode<T>* root, int k)
    {
        if (root == NULL||k==0)
        {
            return 0;
        }
        if (k == 1)
        {
            return 1;
        }
        else
            return GetKlevel(root->_left, k - 1) + GetKlevel(root->_right, k - 1)
    }
    protected:
        BinaryTreeNode<T>* _Copy(BinaryTreeNode<T>* root)
        {
            if (root == NULL)
            {
                return NULL;
            }

            BinaryTreeNode<T>* newRoot = new BinaryTreeNode<T>(root->_data);
            newRoot->_left = _Copy(root->_left);
            newRoot->_right = _Copy(root->_right);

            return newRoot;
        }

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

            if (root->_left == NULL && root->_right == NULL)
            {
                delete root;
                root = NULL;
                return;
            }

            _Destroy(root->_left);
            _Destroy(root->_right);
            delete root;
        }

        BinaryTreeNode<T>* _CreateTree(const T* a,
            size_t size, size_t& index)
        {
            BinaryTreeNode<T>* root = NULL;
            if (index < size && a[index] != '#')
            {
                root = new BinaryTreeNode<T>(a[index]);
                root->_left = _CreateTree(a, size, ++index);
                root->_right = _CreateTree(a, size, ++index);
            }

            return root;
        }

    private:
        BinaryTreeNode<T>* _root;
};