二叉树遍历的非递归算法的实现

二叉树是数据结构中经常用到的一种，而平衡二叉树是实现快速查找的一种数据结构，本文分析了二叉树的递归遍历算法，在此基础上是实现了二叉树的非递归遍历。现将算法描述如下：

先看一棵二叉树

我们先来分析一下他的中根遍历过程 (即左根右的遍历过程)，

1,—– 首先找到 1，然后找到 2，然后找到 4，此时 4 既没有左子树，也没有右子树，输出 4，(一直向左寻找，直到没有左子树，输出该节点)

2—— 此时退到 2，然后输出 2，(没有左子树了，则回退到当前根节点，输出, 寻找右子树)

3—— 然后找到 2 的右子树 5，5 有左子树，则找到 5 的左子树 8，此时 8 既没有左子树，有没有右子树，输出 8，(当前右子树的节点为起点，向左寻找左子树，直到没有，则输出)

4—— 此时退到 5，然后输出 5，(没有左子树了，则会退到当前根结点)

5—— 此时 5 没有右子树，则退到 1，输出 1，(没有右子树，则会退到，当前结点的祖父结点。即 5 的祖父 1)

6——1 此时有右子树，则找到 3，向左进行遍历，到 6,6 没有左子树，则输出 6，(没有左子树了就输出)

7—— 此时退到 3，输出 3(6 没有右子树，则回退到 3)

8—– 3 有右子树，则找到右子树 7,7 有左子树，则找到 9，9 没有左子树，则输出 9(没有左子树就输出)

9—–9 没有右子树，则会退到 7，输出 7(没有右子树就回退)

10—-7 也没有右子树则回退到 3，再回退到 3，再回退到 1，遍历结束

下面是递归运算是的堆栈变化过程。(由于屏幕限制，没有完全显示，共有十四列)

经过对上面的分析过程，我们发现了以下几点

1，当左子树不为空时，左子树入栈，直到左子树为空。

2，出栈，输出

3，右子树不为空，右子树入栈，否则出栈输出, 用流程图表示如下

现将代码公布如下其中1,2,3分别对应流程图上面的1,2,3

//1.
void BinaryTree::pushLeftChild()
{
    while(NULL != current->leftChild)
    {
        nodeStack.Push(current->leftChild);
        current=current->leftChild;
    }
}


//2.
void BinaryTree::popAndPrintNode()
{
    current = nodeStack.Pop();
    if(NULL != current )
    {
        cout<<"Node data:"<<current->data<<endl;
    }
}
//3
void BinaryTree::popRightChild()
{
    while(true)
    {
        if(NULL != current)
        {
            if(NULL != current->rightChild)
            {
                nodeStack.Push(current->rightChild);
                current = current->rightChild;
                break;
            }
            else
            {
                popAndPrintNode();
            }
        }
        else
        {
            break;
        }
    }
}
//中序遍历的函数如下
void BinaryTree::inOrder()
{
    nodeStack.Push(root);
    current = root;
 
    while(!nodeStack.isEmpty())
    {
        pushLeftChild();
        popAndPrintNode();
        popRightChild();
    }
}

文章目录