首页 > 代码库 > 【算法与数据结构】二叉树的 中序 遍历

【算法与数据结构】二叉树的 中序 遍历

 

前一篇写了二叉树的先序遍历,本篇记录一下二叉树的中序遍历,主要是非递归形式的中序遍历。

由于距离上篇有好几天了,所以这里把二叉树的创建和存储结构也重复的写了一遍。

二叉树如下

 

 

二叉树的存储方式依然是二叉链表方式,其结构如下

typedef struct _tagBinTree
{
    unsigned char value;
    struct _tagBinTree* left;
    struct _tagBinTree* right;
}BinTree, *PBinTree;

 

 

先序递归形式的创建二叉树代码如下:

void InitBinTree(PBinTree& pRoot)
{
    cout<<"请输入节点的值, #表示NULL:";
    unsigned char ch = 0;
    cin >> ch;
    if (# == ch)
    {
        pRoot = NULL;    
    }
    else
    {
        pRoot = new BinTree();
        if (NULL == pRoot)
        {
            exit(-1);
        }
        pRoot->value =http://www.mamicode.com/ ch;

        InitBinTree(pRoot->left);
        InitBinTree(pRoot->right);
    }
}

执行情况





访问二叉树,这里只是打印了一下节点的值

void Visit(PBinTree pNode)
{
    cout << "节点的值为 "<<pNode->value<<endl;
}

 

非递归方式中序遍历二叉树原理
/************************************************************************/
/* 非递归中序遍历二叉树
   存储方式为二叉链表,原理如下:
   中序遍历的次序为左子树,根节点,右子树

   首先将根节点入栈
   while(栈不空)
   {
       取栈顶元素a
       if(a不为NULL)
       {
           将栈顶元素的左子树入栈            
       }
       else
       {
           栈顶元素a(为NULL)出栈
           if(此时栈不为空)
           {
               将栈顶元素b出栈,访问此节点,将b的右子树入栈 
           }
       }
   }

/************************************************************************/

 


非递归中序遍历代码
void MidOrderTraverse(PBinTree& pRoot)
{
    stack<PBinTree> stBinTree;

    //根节点入栈
    stBinTree.push(pRoot);

    while(! stBinTree.empty())
    {
        //取栈顶元素
        PBinTree pNode = stBinTree.top();
        //栈顶元素不为NULL
        if (pNode != NULL)
        {
            stBinTree.push(pNode->left);
        }
        else
        {
            //栈顶元素为NULL,将其出栈
            stBinTree.pop();

            //如果此时栈不为空
            if (! stBinTree.empty())
            {
                //将栈顶元素出栈,访问此节点,并将其右子树入栈
                pNode = stBinTree.top();
                stBinTree.pop();
                Visit(pNode);
                stBinTree.push(pNode->right);
            }
        }
    }
}

 

main函数
int _tmain(int argc, _TCHAR* argv[])
{
    cout << "\r\n-----------开始 递归先序构造二叉树 -----------\r\n";
    PBinTree pRoot = NULL;
    InitBinTree(pRoot);
    cout << "\r\n-----------结束 递归先序构造二叉树 -----------\r\n";

    cout << "\r\n\r\n----------开始 非递归中序遍历二叉树------------\r\n";
    MidOrderTraverse(pRoot);
    cout << "-----------结束 非递归中序遍历二叉树------------\r\n\r\n"; 

    return 0;
}

 

执行情况