二叉树的遍历（非递归不用栈空间O(1)）

作者: Magic11 | 来源:发表于2018-03-21 09:57 被阅读0次

Morris Traversal
三种方法（递归、迭代、Morris Traversal）遍历二叉
二叉树
二叉树，非递归法
二叉树的相关操作（一）
二叉树基础算法
面试题----树
不一样的二叉树非递归遍历
二叉树的遍历（非递归不用栈空间O(1)）
二叉树递归非递归遍历算法整理

#include <iostream>

using namespace std;

enum OrderType
{
    PRE_ORDER,
    IN_ORDER,
    POST_ORDER
};

typedef struct TreeNode
{
    int m_data;
    TreeNode* pLChild;
    TreeNode* pRChild;
    TreeNode* pParent;
    //标记是否已访问
    bool visited; 

    TreeNode(int data, TreeNode *parent) {
        this->m_data = data;
        pParent = parent;
        visited = false;
        pLChild = NULL;
        pRChild = NULL;
    }
} *PTreeNode;
/************************************************************************/
/* 先序遍历二叉树                                                       */
/************************************************************************/
void PreOrderTree(TreeNode * root)
{
    while (root != NULL)
    {
        if (!root->visited){
            cout << root->m_data << " ";
            root->visited = true;
        }
        while (root->pLChild && !root->pLChild->visited)
        {
            root = root->pLChild;
            cout << root->m_data <<" ";
            root->visited = true;
        }
        if (root->pRChild != NULL && !root->pRChild->visited)
        {
            root = root->pRChild;
        }
        else
        {
            root = root->pParent;
        }       
    }
    cout << endl;
}

/************************************************************************/
/* 中序遍历二叉树                                                       */
/************************************************************************/
void InOrderTree(TreeNode * root)
{
    while (root != NULL)
    {
        while (root->pLChild && !root->pLChild->visited)
        {
            root = root->pLChild;
        }
        if (!root->visited)
        {
            cout << root->m_data << " ";
            root->visited = true;
        }
        if (root->pRChild != NULL && !root->pRChild->visited)
        {
            root = root->pRChild;
        }
        else
        {
            root = root->pParent;
        }           
    }
    cout << endl;
}
/************************************************************************/
/* 后序遍历二叉树                                                       */
/************************************************************************/
void PostOrderTree(TreeNode *root)
{
    while (root)
    {
        while (root->pLChild && !root->pLChild->visited)
        {
            root = root->pLChild;
        }

        if (root->pRChild && !root->pRChild->visited)
        {
            root = root->pRChild;
        }
        else
        {
            cout << root->m_data << " ";
            root->visited = true;
            root = root->pParent;
        }
    }
    cout << endl;
}

void orderTree(TreeNode *root, OrderType order)
{
    switch(order)
    {
        case PRE_ORDER:
            PreOrderTree(root);
            break;      
        case IN_ORDER:
            InOrderTree(root);
            break;
        case POST_ORDER:
            PostOrderTree(root);
            break;
        default:
            break;
    }
}
/***************************************/
/*     创建测试的二叉树
/*            1
/*          /   \
/*         2     3
/*        / \     \
/*       4   5     6
/*          / \   / \
/*         7   8 9   10
****************************************/
TreeNode* createTree() 
{
    PTreeNode root = new TreeNode(1, NULL);

    PTreeNode node2 = new TreeNode(2, root);
    PTreeNode node3 = new TreeNode(3, root);

    root->pLChild = node2;
    root->pRChild = node3;

    PTreeNode node4 = new TreeNode(4, node2);
    PTreeNode node5 = new TreeNode(5, node2);
    node2->pLChild = node4;
    node2->pRChild = node5;

    PTreeNode node6 = new TreeNode(6, node3);
    node3->pRChild = node6;

    PTreeNode node7 = new TreeNode(7, node5);
    PTreeNode node8 = new TreeNode(8, node5);
    node5->pLChild = node7;
    node5->pRChild = node8;

    PTreeNode node9 = new TreeNode(9, node6);
    PTreeNode node10 = new TreeNode(10, node6);
    node6->pLChild = node9;
    node6->pRChild = node10;

    return root;
}

void main() {

    cout << "前序遍历" << endl;
    orderTree(createTree(), PRE_ORDER);
    cout << "中序遍历" << endl;
    orderTree(createTree(), IN_ORDER);
    cout << "后序遍历" << endl;
    orderTree(createTree(), POST_ORDER);

    getchar();
}