二叉树先序、中序、后序三种遍历的非递归.txt
#include
#define STACK_MAXLEN 30 //using namespace std; typedef struct BTreeNode {
int where;
struct BTreeNode *rightChild;
struct BTreeNode *leftChild;
}TYPE_B_TREE_NODE,*TYPE_pB_TREE_NODE;
//堆栈的结构
class TStack
{
public:
void push(TYPE_pB_TREE_NODE pNode);//入栈
TYPE_pB_TREE_NODE pop();//出栈
int empty()
{
if ( top == base )
return 1;
else
return 0;
}
TStack()
{
top=base=stackArray;
for(int i=0; i < STACK_MAXLEN; i++)
stackArray[i]=NULL;
//cout<<"堆栈初始化完毕～"<>NodeNum;
pBTreeArray=new TYPE_B_TREE_NODE[NodeNum];
for(i=1; i <= NodeNum/2-1; i++)
{
pBTreeArray[i-1].where=i;
pBTreeArray[i-1].leftChild=pBTreeArray+(2*i-1);
pBTreeArray[2*i-1].where=2*i;
pBTreeArray[i-1].rightChild=pBTreeArray+(2*i);
pBTreeArray[2*i].where=2*i+1;
}
if(2*i+1 == NodeNum )
{
pBTreeArray[i-1].where=i;
pBTreeArray[i-1].leftChild=pBTreeArray+(2*i-1);
pBTreeArray[2*i-1].where=2*i;
pBTreeArray[i-1].rightChild=pBTreeArray+(2*i);
pBTreeArray[2*i].where=2*i+1;
}
else
{
pBTreeArray[i-1].where=i;
pBTreeArray[i-1].leftChild=pBTreeArray+(2*i-1);
pBTreeArray[2*i-1].where=2*i;
pBTreeArray[2*i].rightChild=NULL;
}
for( int j=i+1; j <=NodeNum; j++ )
{
pBTreeArray[j-1].leftChild=NULL;
pBTreeArray[j-1].rightChild=NULL;
}
return pBTree=pBTreeArray+0;
}
//
void PrintBTree(TYPE_pB_TREE_NODE pBTreeRoot)
{
if( pBTreeRoot != NULL )
{
cout<where<leftChild);
PrintBTree(pBTreeRoot->rightChild);
}
}
//先序遍历
void PreOrder(TYPE_pB_TREE_NODE pBTreeRoot)
{
cout<<"先序遍历"<where<leftChild;
}
while( stack.empty() != 1 )
{
pTemporary=stack.pop();
if( pTemporary->rightChild == NULL )
{
continue;
}
else
{
pTemporary=pTemporary->rightChild;
while( pTemporary != NULL )
{
cout<where<leftChild;
}
}
}
}
//中序遍历
void InOrder(TYPE_pB_TREE_NODE pBTreeRoot)
{
cout<<"中序遍历"<where<leftChild;
}
while( stack.empty() != 1 )
{
pTemporary=stack.pop();
cout<where<rightChild == NULL )
{
continue;
}
else
{
pTemporary=pTemporary->rightChild;
while( pTemporary != NULL )
{
//
stack.push(pTemporary);
pTemporary=pTemporary->leftChild;
}
}
}
}
//后序遍历
void PostOrder(TYPE_pB_TREE_NODE pBTreeRoot)
{
cout<<"后序遍历"<where<rightChild !=NULL )
{
stack.push(pTemporary->rightChild);
pFlag++;
// withNoChild++;
}
if( pTemporary->leftChild !=NULL )
{
stack.push(pTemporary->leftChild);
pFlag++;
//withNoChild++;
}
}
}
}
void main()
{
TYPE_pB_TREE_NODE pBTreeRoot;
pBTreeRoot=CreateBTree();
// PrintBTree(pBTreeRoot);
PreOrder(pBTreeRoot);
InOrder(pBTreeRoot);
PostOrder(pBTreeRoot);
}
浙公网安备 33021202002483