♥二叉树前、中、后序遍历代码实现♥

直接上代码：

#include
#include
#include
using namespace std;

//用结构体创建结点，包括创建一个数据域以及两个指向左右结点的指针
template
struct TreeNode {
    DataType val;
    TreeNode *lchild, *rchild;
};

//创建一个树类，这个树包括一个树根（结点），进行创建、释放、以及分别进行前中后序的遍历
template
class Tree {
private:
    TreeNode *root;
    //直接递归创建一棵树，记得设置终止条件
    TreeNode *Create(TreeNode *r) {
        DataType ch;
        cin >> ch;
        if (ch == -1)
            r = NULL;
        else {
            r = new TreeNode;
            r->val = ch;
            r->lchild = Create(r->lchild);
            r->rchild = Create(r->rchild);
        }
        return r;
    }

    //递归释放整一颗树
    void Release(TreeNode *r) {
        if (r != NULL) {
            Release(r->lchild);
            Release(r->rchild);
            delete r;
        }
    }

    void PreOrder(TreeNode *r) {
        if (r == NULL)
            return;
        else {
            cout << r->val <<" ";
            PreOrder(r->lchild);
            PreOrder(r->rchild);
        }
    }

    void InOrder(TreeNode *r) {
        if (r == NULL)
            return;
        else {
            InOrder(r->lchild);
            cout << r->val <<" ";
            InOrder(r->rchild);
        }
    }

    void PostOrder(TreeNode *r) {
        if (r == NULL)
            return;
        else {
            PostOrder(r->lchild);
            PostOrder(r->rchild);
            cout << r->val<<" ";
        }
    }

public:
    Tree() { root = Create(root); }
    Tree(TreeNode *r) {
        root = r;
        root = Create(root);
    }
    ~Tree() { Release(root); }

    TreeNode *getRoot(){return root;}
    void PreOrder() { PreOrder(root); }   //前序遍历
    void InOrder() { InOrder(root); }     //中序遍历
    void PostOrder() { PostOrder(root); } //后序遍历
};

//补充:迭代做法，这里只讲后序的迭代
//后序遍历的迭代做法
template
vector first_postorderTraversal(TreeNode *root) {
    vector res;
    if (!root)
        return res;
    TreeNode *prev = nullptr;
    stack *> st;
    while (root != nullptr || !st.empty()) {
        //如果root不是空的话，一路压到最左边
        while (root) {
            st.emplace(root);
            root = root->lchild;
        }
        //root取栈的顶部，栈弹出一个
        root = st.top();
        st.pop();
        //如果右边为空或右边已经被走过，将root的值压入数组res，然后把root赋值为空
        if (root->rchild == nullptr || root->rchild == prev) {
            res.emplace_back(root->val);
            prev = root;
            root = nullptr;
        } else {
            //如果右边不为空且右边没有被走过，root结点重新入栈，然后root往右走一步
            st.emplace(root);
            root = root->rchild;
        }
    }
    return res;
}

//后序遍历的迭代做法2:先根右左，然后翻转
template
vector second_postorderTraversal(TreeNode *root) {
    vector res;
    if(root == nullptr) return res;
    stack*> st;
    st.push(root);
    while(!st.empty())
    {
        TreeNode* temp=st.top();
        st.pop();
        res.push_back(temp->val);

        //左节点先进栈，后处理
        if(temp->left != nullptr) st.push(temp->left);
        //右节点后进栈，先处理
        if(temp->right != nullptr) st.push(temp->right);
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    TreeNode* BiNode;
    Tree BiTree(BiNode);
    cout<<"前序遍历： ";
    BiTree.PreOrder();
    cout< ans=first_postorderTraversal(BiTree.getRoot());
    cout<<"后序迭代遍历： ";
    for(auto x:ans){
        cout< ans=second_postorderTraversal(BiTree->getRoot());
//    for(auto x:ans){
//        cout< 
输入：
 
1 2 -1 -1 3 4 -1 -1 5 -1 -1
 
输出：
 
前序遍历： 1 2 3 4 5
中序遍历： 2 1 4 3 5
后序递归遍历： 2 4 5 3 1
后序迭代遍历： 2 4 5 3 1

 
 
我是花花，祝自己也祝您变强了~