非递归方式遍历二叉树(前序,中序,后序)代码

#include <iostream>
#include <string>
#include <stack>
using namespace std;

struct Node {
    int val;
    Node *left, *right;
    Node(int v) :val(v) {
        left = right = NULL;
    }
};

void deleteTree(Node *tree) {
    if (tree->left) deleteTree(tree->left);
    if (tree->right) deleteTree(tree->right);
    delete(tree);
    tree = NULL;
}

/******************************************************
* 递归遍历二叉树
******************************************************/

string preOrderTraverse(Node* tree) {
    string s = to_string(tree->val) + ",";
    if (tree->left) s += preOrderTraverse(tree->left);
    if (tree->right) s += preOrderTraverse(tree->right);
    return s;
}

string inOrderTraverse(Node* tree) {
    string s;
    if (tree->left) s = inOrderTraverse(tree->left);
    s += to_string(tree->val) + ",";
    if (tree->right) s += inOrderTraverse(tree->right);
    return s;
}

string postOrderTraverse(Node* tree) {
    string s;
    if (tree->left) s = postOrderTraverse(tree->left);
    if (tree->right) s += postOrderTraverse(tree->right);
    s += to_string(tree->val) + ",";
    return s;
}

/*********************************************************
* 循环遍历二叉树
*********************************************************/

// 前序遍历循环方式
string getPreOrder(Node* tree) {

#ifdef TEACH

    // 先访问根结点
    string s = to_string(tree->val) + ",";  
    // 如果直接使tree指向左子树会丢失右子树的位置,所以需要先将右子树入栈,当左子树访问完时从栈中取出右子树继续访问
    // 因为左子树里面还可能遇到这个问题,所以左子树里还会用到这个栈暂存结点,所以要用栈而不是队列,因为根结点的右子树要在左子树全部访问完后访问
    stack<Node*> S;
    S.push(tree->right);
    // 暂存右子树后就可以安心访问左子树
    tree = tree->left;
    // 此时又回到问题的开始,将以上过程写成循环如下:

#endif // TEACH

    // 先生成栈
    stack <Node *> S;
    // 生成返回结果
    string s = "";
    // 确定基本思想空指针不入栈,统一操作,新结点的两种获取方式:
    // 1. 由父结点下沉到左子结点得到的当前结点,下沉得到的当前结点可以为NULL,此时切换成方式2获取新结点
    // 2. 由栈中得到,所以先将根结点入栈

    // 循环继续的条件是满足两种获取方式其一即可,所以tree不为空或栈不为空
    while (tree != NULL || !S.empty()) {
        // 如果方式1可行
        if (tree != NULL) {
            // 先访问当前结点
            s += to_string(tree->val) + ",";
            // 再暂存右子树
            if (tree->right) S.push(tree->right);
            // 再继续下沉到左子树,允许为NULL,这样下次循环进来时就会弹栈
            tree = tree->left;
        }
        // 方式1不可行时切换到方式2,从栈中取暂存的结点访问
        else {
            // 从栈中取出新的根结点
            tree = S.top();
            S.pop();
            // 取出结点后不做操作,而是继续循环,因为访问结点的操作会在前面那个if中完成,当前只要使tree不为空即可
        }
    }
    return s;
}

// 中序遍历循环方式
string getInOrder(Node* tree) {
    // 因为是左中右的访问顺序,所以与前序的区别就是不是暂存右子树,而是要暂存当前结点,然后同样是下沉到左子树
    stack<Node *> S;    // 空指针禁止入栈
    string s = "";
    // 取结点的两种方式
    // 1. 来自父结点的向左下沉,允许为NULL,为NULL时切换到方式2,不为NULL时入栈并向左下沉
    // 2. 从栈中弹数据,不为NULL,其左子树已全部访问,现在访问此结点并向右下沉即可
    while (tree != NULL || !S.empty()) {
        if (tree != NULL) {
            // 方式1,入栈后向左下沉
            S.push(tree);
            tree = tree->left;
        }
        else {
            // 方式2,tree已经为NULL了,从栈中取不为NULL的新结点
            tree = S.top();
            S.pop();
            // 左子树已经访问过,开始访问当前结点
            s += to_string(tree->val) + ",";
            // 向右下沉,不要继续操作,留给循环完成后续操作
            tree = tree->right;
        }
    }
    return s;
}

// 后序遍历循环方式
string getPostOrder(Node* tree) {
    // 后序遍历与前两种不同,当保持左右中的遍历顺序时,根结点向左下沉,就要将根和右子树压栈。但弹栈时会出现两种结点,一种如右子树那种其整棵树未访问过,一种如根结点这种左右子树均已访问过。因此要将两种结点状态也记录进栈
    stack< pair<Node*, bool> > S;   // bool量为true表示左右子树均已访问,为false表示整棵树未访问过
    // 取结点方式分为三种
    // 1. 由父结点左下沉得到,允许为NULL。不为NULL时将根和右子树先后压栈然后向左下沉。为NULL时切换到方式2
    // 2. 从栈S取结点,根据结点状态量进行分类
    //     2.1. 为true,直接访问此结点,继续弹栈循环
    //     2.2. 为false,直接继续循环
    string s = "";
    while (tree != NULL || !S.empty()) {
        if (tree != NULL) {
            // 先压根结点
            S.push({ tree, true });
            // 再压右子树
            if (tree->right) S.push({ tree->right, false });
            // 再让根结点向左下沉
            tree = tree->left;
        }
        else {
            // 从栈中取结点
            tree = S.top().first;
            bool state = S.top().second;
            S.pop();
            // 根据状态分类
            if (state) {
                s += to_string(tree->val) + ",";
                // 将tree置NULL供循环下次再弹栈
                tree = NULL; 
            }
            // state为false时由循环下次处理
        }
    }
    return s;
}

int main() {
    /****************************
    * 此二叉树包含了叶结点、有一个左子结点的结点、有一个右子结点的结点、有两个子结点的结点所有情况
    *          1
    *       /     \
    *      2       3
    *    /   \    / \
    *   4     5  6   7
    *  / \   /    \
    * 8   9 10    12
    ****************************/
    Node* tree = new Node(1);
    Node* t2 = tree->left = new Node(2);
    Node* t3 = tree->right = new Node(3);
    Node* t4 = t2->left = new Node(4);
    Node* t5 = t2->right = new Node(5);
    Node* t6 = t3->left = new Node(6);
    t3->right = new Node(7);
    t4->left = new Node(8);
    t4->right = new Node(9);
    t5->left = new Node(10);
    t6->right = new Node(12);

    string preOrderTraverseString = preOrderTraverse(tree);
    string inOrderTraverseString = inOrderTraverse(tree);
    string postOrderTraverseString = postOrderTraverse(tree);

    // 用循环遍历二叉树
    if (getPreOrder(tree) == preOrderTraverseString) {
        cout << "前序遍历测试通过" << endl;
    }
    else cout << "前序遍历测试失败" << endl;

    if (getInOrder(tree) == inOrderTraverseString) {
        cout << "中序遍历测试通过" << endl;
    }
    else cout << "中序遍历测试失败" << endl;

    if (getPostOrder(tree) == postOrderTraverseString) {
        cout << "后序遍历测试通过" << endl;
    }
    else cout << "后序遍历测试失败" << endl;

    deleteTree(tree);

    return 0;
}

中序遍历和前序遍历无注释版

// 中序遍历
void InOrder(Node* T){
    stack<Node*> S;
    Node* p = T;
    while (p || !S.empty()){
        if (p){
            S.push(p);
            p = p->lchild;
        }
        else {
            p = S.top();
            visit(p);
            S.pop();
            p = p->rchild;
        }
    }
}
// 前序遍历
void preOrder(Node* T){
    Node* p = T;
    stack<Node*> S;
    while (p || !S.empty()){
        if (p){
            visit(p);
            S.push(p->rchild);
            p = p->lchild;
        }
        else {
            p = S.top();
            S.pop();
        }
    }
}

发表评论