二叉树是数据结构中经常用到的一种，而平衡二叉树是实现快速查找的一种数据结构，本文分析了二叉树的递归遍历算法，在此基础上是实现了二叉树的非递归遍历。现将算法描述如下：
先看一棵二叉树
我们先来分析一下他的中根遍历过程 (即左根右的遍历过程)，
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();
}
}
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。