欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树前序中序后序层序遍历(递归和非递归)

程序员文章站 2022-05-16 14:21:51
...

目录

节点定义 

二叉树

前序遍历

递归

 非递归

中序遍历

递归

非递归

后序遍历

递归

非递归1

非递归2

非递归3

非递归4

层序遍历

序列相同的二叉树


节点定义 

template<typename T>
class TreeNode {
public:
    T data;
    TreeNode<T>* left, * right;
    TreeNode() :left(nullptr), right(nullptr) {}
    TreeNode(const T& data) :data(data), left(nullptr), right(nullptr) {}
};

二叉树

#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<string>
using namespace std;
template<typename T>
class BinaryTree {
private:
    TreeNode<T>* root;
    void destroy(TreeNode<T>**);
    void pre_order_traversal(TreeNode<T>*)const;
    void in_order_traversal(TreeNode<T>*)const;
    void post_order_traversal(TreeNode<T>*)const ;
public:
    BinaryTree();
    void pre_order_traversal()const;
    void pre_order_traversal_non_recursive()const;
    void in_order_traversal()const;
    void in_order_traversal_non_recursive()const;
    void post_order_traversal()const;
    void post_order_traversal_non_recursive()const;
    void post_order_traversal_non_recursive2()const;
    void post_order_traversal_non_recursive3()const;
    void post_order_traversal_non_recursive4()const;
    void level_order_traversal()const;
};

前序遍历

递归

/**
 * 前序遍历
 */
template<typename T>
void BinaryTree<T>::pre_order_traversal()const
{
    if (this->root != nullptr) {
        pre_order_traversal(this->root);
    }
    cout << endl;
}

 非递归

/**
 * 非递归前序遍历
 */
template<typename T>
void BinaryTree<T>::pre_order_traversal_non_recursive()const
{
    stack<TreeNode<T>*> s;
    TreeNode<T>* p = this->root;
    while (p != nullptr || !s.empty()) {
        //一直向左子树访问
        while (p) {
            cout << p->data << ' ';
            if (p->right != nullptr) {
                //存储右子树
                s.push(p->right);
            }
            p = p->left;
        }
        if (!s.empty()) {
            //右子树
            p = s.top();
            s.pop();
        }
    }
    cout << endl;
}

中序遍历

递归

/**
 * 中序遍历
 */
template<typename T>
void BinaryTree<T>::in_order_traversal()const
{
    if (this->root != nullptr) {
        in_order_traversal(this->root);
    }
    cout << endl;
}

非递归

/**
 * 非递归中序遍历
 */
template<typename T>
void BinaryTree<T>::in_order_traversal_non_recursive()const
{
    stack<TreeNode<T>*> s;
    TreeNode<T>* p = this->root;
    while (p != nullptr || !s.empty()) {
        //压入当前节点
        while (p != nullptr) {
            s.push(p);
            p = p->left;
        }
        //左子树已经访问完了,开始访问根
        if (!s.empty()) {
            p = s.top();
            s.pop();
            cout << p->data << ' ';
            //右子树
            p = p->right;
        }
    }
    cout << endl;
}

后序遍历

递归

/**
 * 后序遍历
 */
template<typename T>
void BinaryTree<T>::post_order_traversal()const
{
    if (this->root != nullptr) {
        post_order_traversal(this->root);
    }
    cout << endl;
}

非递归1

/**
 * 非递归后序遍历
 */
template<typename T>
void BinaryTree<T>::post_order_traversal_non_recursive()const
{
    stack<TreeNode<T>*> s;
    TreeNode<T>* p = this->root, *pre = nullptr;
    while (p != nullptr || !s.empty()) {
        //压入当前节点
        while (p!=nullptr) {
            s.push(p);
            p = p->left;
        }
        p = s.top();
        //如果没有右子树或者右子树已经访问过了,那么就可以访问根节点
        if (p->right == nullptr || p->right == pre) {
            cout << p->data << ' ';
            pre = p;
            s.pop();
            p = nullptr;
        }
        else {
            //访问右子树
            p = p->right;
        }
    }
    cout << endl;
}

非递归2

/**
 * 非递归后序遍历
 */
template<typename T>
void BinaryTree<T>::post_order_traversal_non_recursive2()const
{
    stack<TreeNode<T>*> s;
    TreeNode<T>* p = this->root, * pre = nullptr;
    if (p == nullptr)return;
    s.push(p);
    while (!s.empty()) {
        p = s.top();
        //没有左子树和右子树,或者上次访问的的节点是左子树或右子树
        if ((p->left == nullptr && p->right == nullptr) ||
            ((p->left == pre || p->right == pre) && pre != nullptr)) {
            cout << p->data << ' ';
            pre = p;
            s.pop();
        }
        else {
            //先压入右子树,再压入左子树,这样取的时候是反过来的
            if (p->right != nullptr) {
                s.push(p->right);
            }
            if (p->left != nullptr) {
                s.push(p->left);
            }
        }
    }
    cout << endl;
}

非递归3

/**
 * 非递归后序遍历
 */
template<typename T>
void BinaryTree<T>::post_order_traversal_non_recursive3()const
{
    stack<TreeNode<T>*> s;
    TreeNode<T>* p = this->root, *pre = nullptr;
    //一直往左子树访问
    while (p != nullptr) {
        s.push(p);
        p = p->left;
    }
    while (!s.empty()) {
        p = s.top();
        //如果右子树为空或者访问过,则可以访问根
        if (p->right == nullptr || p->right == pre) {
            cout << p->data << ' ';
            s.pop();
            pre = p;
        }
        else {
            //访问右子树
            p = p->right;
            //一直往左子树访问
            while (p) {
                s.push(p);
                p = p->left;
            }
        }
    }
    cout << endl;
}

非递归4

/**
 * 非递归后序遍历
 */
template<typename T>
void BinaryTree<T>::post_order_traversal_non_recursive4()const
{
    stack<TreeNode<T>*> s;
    //当前节点的右子树是否访问过的栈
    stack<bool> visited;
    bool flag;
    TreeNode<T>* p = this->root;
    while (p != nullptr || !s.empty()) {
        //一直往左子树访问
        while (p) {
            s.push(p);
            //还没有访问过右子树
            visited.push(false);
            p = p->left;
        }
        p = s.top();
        flag = visited.top();
        //右子树为空或访问过了
        if (p->right == nullptr || flag) {
            cout << p->data << ' ';
            s.pop();
            visited.pop();
            p = nullptr;
        }
        else {
            p = p->right;
            visited.pop();
            //访问过右子树
            visited.push(true);
        }
    }
    cout << endl;
}

层序遍历

/**
 * 层序遍历
 */
template<typename T>
void BinaryTree<T>::level_order_traversal()const
{
    queue<TreeNode<T>*> q;
    if (this->root != nullptr) {
        q.push(this->root);
    }
    TreeNode<T>* p;
    while (!q.empty()) {
        p = q.front();
        q.pop();
        cout << p->data << ' ';
        if (p->left != nullptr) {
            q.push(p->left);
        }
        if (p->right != nullptr) {
            q.push(p->right);
        }
    }
    cout << endl;
}

序列相同的二叉树

 

前序遍历和后序遍历相同的二叉树

TLR

LRT

显然只有根节点

 

前序遍历和中序遍历相同的二叉树

TLR

LTR

---去掉L----->

TR

显然:非叶子结点只有右子树的二叉树

 

中序遍历和后序遍历相同的二叉树

LTR

LRT

---去掉R----->

LT

显然:非叶子结点只有左子树的二叉树