二叉树遍历算法集合(前中后序遍历的递归和非递归算法,层序遍历算法)

二叉树遍历算法集合(前中后序遍历的递归和非递归算法,层序遍历算法)

费了两天时间写的,包括前中后序遍历的递归和非递归算法,还有层序遍历总共2*3 + 1 = 7中遍历二叉树的算法,感觉其中后序遍历的非递归算法比较困难,想了很久最后的实现还是不够优雅,请大家指正~~

总共三个文件,一个头文件,一个对应的cpp文件,还有一个用于测试的文件.

头文件:

/********************************************************************
created:2006/07/04
filename:BinaryTree.h
author:李创
http://www.cppblog.com/converse/

purpose:演示二叉树的算法
*********************************************************************/

#ifndefBinaryTree_H
#defineBinaryTree_H

#include<stdlib.h>
#include<stack>

classBinaryTree
{
private:
typedefintItem;
typedefstructTreeNode
{
ItemNode;
TreeNode*pRight;
TreeNode*pLeft;

TreeNode(Itemnode=0,TreeNode*pright=NULL,TreeNode*pleft=NULL)
:Node(node)
,pRight(pright)
,pLeft(pleft)
{
}

}TreeNode,*PTreeNode;

public:
enumTraverseType
{
PREORDER=0,//前序
INORDER=1,//中序
POSTORDER=2,//后序
LEVELORDER=3//层序
};

BinaryTree(ItemArray[],intnLength);
~BinaryTree();

PTreeNodeGetRoot()
{
returnm_pRoot;
}

//遍历树的对外接口
//指定遍历类型和是否是非递归遍历,默认是递归遍历
voidTraverse(TraverseTypetraversetype,boolbRec=true);

private:
PTreeNodeCreateTreeImpl(ItemArray[],intnLength);
voidDetroyTreeImpl(PTreeNodepTreenode);

voidPreTraverseImpl(PTreeNodepTreenode);//递归前序遍历树
voidInTraverseImpl(PTreeNodepTreenode);//递归中序遍历树
voidPostTraverseImpl(PTreeNodepTreenode);//递归后序遍历树

voidNoRecPreTraverseImpl(PTreeNodepTreenode);//非递归前序遍历树
voidNoRecInTraverseImpl(PTreeNodepTreenode);//非递归中序遍历树
voidNoRecPostTraverseImpl(PTreeNodepTreenode);//非递归后序遍历树

voidLevelTraverseImpl(PTreeNodepTreenode);

PTreeNodem_pRoot;//根结点

//采用STL里面的stack作为模拟保存链表结点的stack容器
typedefstd::stack<BinaryTree::PTreeNode>TreeNodeStack;
};

#endif

实现文件:

/********************************************************************
created:2006/07/04
filename:BinaryTree.cpp
author:李创
http://www.cppblog.com/converse/

purpose:演示二叉树的算法
*********************************************************************/

#include<iostream>
#include<assert.h>
#include<queue>
#include"BinaryTree.h"

BinaryTree::BinaryTree(ItemArray[],intnLength)
:m_pRoot(NULL)
{
assert(NULL!=Array);
assert(nLength>0);

m_pRoot=CreateTreeImpl(Array,nLength);
}

BinaryTree::~BinaryTree()
{
DetroyTreeImpl(m_pRoot);
}

//按照中序递归创建树
BinaryTree::PTreeNodeBinaryTree::CreateTreeImpl(ItemArray[],intnLength)
{
intmid=nLength/2;
PTreeNodep=newTreeNode(Array[mid]);

if(nLength>1)
{
p->pLeft=CreateTreeImpl(Array,nLength/2);
p->pRight=CreateTreeImpl(Array+mid+1,nLength/2-1);
}

returnp;
}

voidBinaryTree::DetroyTreeImpl(PTreeNodepTreenode)
{
if(NULL!=pTreenode->pLeft)
{
DetroyTreeImpl(pTreenode->pLeft);
}
if(NULL!=pTreenode->pRight)
{
DetroyTreeImpl(pTreenode->pRight);
}

deletepTreenode;
pTreenode=NULL;
}

//遍历树的对外接口
//指定遍历类型和是否是非递归遍历,默认是递归遍历
voidBinaryTree::Traverse(TraverseTypetraversetype,boolbRec/*=true*/)
{
switch(traversetype)
{
casePREORDER://前序
{
if(true==bRec)
{
std::cout<<"递归前序遍历树\n";
PreTraverseImpl(m_pRoot);
}
else
{
std::cout<<"非递归前序遍历树\n";
NoRecPreTraverseImpl(m_pRoot);
}
}
break;

caseINORDER://中序
{
if(true==bRec)
{
std::cout<<"递归中序遍历树\n";
InTraverseImpl(m_pRoot);
}
else
{
std::cout<<"非递归中序遍历树\n";
NoRecInTraverseImpl(m_pRoot);
}
}
break;

casePOSTORDER://后序
{
if(true==bRec)
{
std::cout<<"递归后序遍历树\n";
PostTraverseImpl(m_pRoot);
}
else
{
std::cout<<"非递归后序遍历树\n";
NoRecPostTraverseImpl(m_pRoot);
}
}
break;

caseLEVELORDER://层序
{
std::cout<<"层序遍历树\n";
LevelTraverseImpl(m_pRoot);
}
}

std::cout<<std::endl;
}

//递归前序遍历树
voidBinaryTree::PreTraverseImpl(PTreeNodepTreenode)
{
if(NULL==pTreenode)
return;

std::cout<<"Item="<<pTreenode->Node<<std::endl;

PreTraverseImpl(pTreenode->pLeft);

PreTraverseImpl(pTreenode->pRight);
}

//非递归前序遍历树
voidBinaryTree::NoRecPreTraverseImpl(PTreeNodepTreenode)
{
if(NULL==pTreenode)
return;

TreeNodeStackNodeStack;
PTreeNodepNode;
NodeStack.push(pTreenode);

while(!NodeStack.empty())
{
while(NULL!=(pNode=NodeStack.top()))//向左走到尽头
{
std::cout<<"Item="<<pNode->Node<<std::endl;//访问当前结点
NodeStack.push(pNode->pLeft);//左子树根结点入栈
}
NodeStack.pop();//左子树根结点退栈
if(!NodeStack.empty())
{
pNode=NodeStack.top();
NodeStack.pop();//当前结点退栈
NodeStack.push(pNode->pRight);//当前结点的右子树根结点入栈
}
}
}

//中序遍历树
//中序遍历输出的结果应该和用来初始化树的数组的排列顺序一致
voidBinaryTree::InTraverseImpl(PTreeNodepTreenode)
{
if(NULL==pTreenode)
return;

if(NULL!=pTreenode->pLeft)
{
InTraverseImpl(pTreenode->pLeft);
}

std::cout<<"Item="<<pTreenode->Node<<std::endl;

if(NULL!=pTreenode->pRight)
{
InTraverseImpl(pTreenode->pRight);
}
}

//非递归中序遍历树
voidBinaryTree::NoRecInTraverseImpl(PTreeNodepTreenode)
{
if(NULL==pTreenode)
return;

TreeNodeStackNodeStack;
PTreeNodepNode;
NodeStack.push(pTreenode);

while(!NodeStack.empty())
{
while(NULL!=(pNode=NodeStack.top()))//向左走到尽头
{
NodeStack.push(pNode->pLeft);
}

NodeStack.pop();

if(!NodeStack.empty()&&NULL!=(pNode=NodeStack.top()))
{
std::cout<<"Item="<<pNode->Node<<std::endl;
NodeStack.pop();
NodeStack.push(pNode->pRight);
}
}
}

//后序遍历树
voidBinaryTree::PostTraverseImpl(PTreeNodepTreenode)
{
if(NULL==pTreenode)
return;

if(NULL!=pTreenode->pLeft)
{
PostTraverseImpl(pTreenode->pLeft);
}

if(NULL!=pTreenode->pRight)
{
PostTraverseImpl(pTreenode->pRight);
}

std::cout<<"Item="<<pTreenode->Node<<std::endl;
}

//非递归后序遍历树
voidBinaryTree::NoRecPostTraverseImpl(PTreeNodepTreenode)
{
if(NULL==pTreenode)
return;

TreeNodeStackNodeStack;
PTreeNodepNode1,pNode2;
NodeStack.push(pTreenode);
pNode1=pTreenode->pLeft;

boolbVisitRoot=false;//标志位,是否访问过根结点
while(!NodeStack.empty())
{
while(NULL!=pNode1)//向左走到尽头
{
NodeStack.push(pNode1);
pNode1=pNode1->pLeft;
}

pNode1=NodeStack.top();
NodeStack.pop();

if(NULL==pNode1->pRight)//如果没有右子树就是叶子结点
{
std::cout<<"Item="<<pNode1->Node<<std::endl;
pNode2=pNode1;
pNode1=NodeStack.top();

if(pNode2==pNode1->pRight)//如果这个叶子结点是右子树
{
std::cout<<"Item="<<pNode1->Node<<std::endl;
NodeStack.pop();
pNode1=NULL;
}
else//否则访问右子树
{
pNode1=pNode1->pRight;
}
}
else//访问右子树
{
if(pNode1==pTreenode&&true==bVisitRoot)//如果已经访问过右子树那么就退出
{
std::cout<<"Item="<<pNode1->Node<<std::endl;
return;
}
else
{
if(pNode1==pTreenode)
{
bVisitRoot=true;
}

NodeStack.push(pNode1);
pNode1=pNode1->pRight;
}
}
}
}

//按照树的层次从左到右访问树的结点
voidBinaryTree::LevelTraverseImpl(PTreeNodepTreenode)
{
if(NULL==pTreenode)
return;

//层序遍历用于保存结点的容器是队列
std::queue<PTreeNode>NodeQueue;
PTreeNodepNode;
NodeQueue.push(pTreenode);

while(!NodeQueue.empty())
{
pNode=NodeQueue.front();
NodeQueue.pop();
std::cout<<"Item="<<pNode->Node<<std::endl;

if(NULL!=pNode->pLeft)
{
NodeQueue.push(pNode->pLeft);
}
if(NULL!=pNode->pRight)
{
NodeQueue.push(pNode->pRight);
}
}
}

测试文件:

/********************************************************************
created:2006/07/04
filename:main.cpp
author:李创
http://www.cppblog.com/converse/

purpose:测试二叉树的算法
*********************************************************************/

#include"BinaryTree.h"

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<iostream>

voidDisplayArray(intarray[],intlength)
{
inti;

for(i=0;i<length;i++)
{
printf("array[%d]=%d\n",i,array[i]);
}
}

voidCreateNewArray(intarray[],intlength)
{
for(inti=0;i<length;i++)
{
array[i]=rand()%256+i;
}
}

intmain()
{
intarray[10];
srand(time(NULL));

//创建数组
CreateNewArray(array,10);
DisplayArray(array,10);

BinaryTree*pTree=newBinaryTree(array,10);

//测试前序遍历
pTree->Traverse(BinaryTree::PREORDER);
std::cout<<"root="<<pTree->GetRoot()->Node<<std::endl;
std::cout<<"root->left="<<pTree->GetRoot()->pLeft->Node<<std::endl;
std::cout<<"root->right="<<pTree->GetRoot()->pRight->Node<<std::endl;
pTree->Traverse(BinaryTree::PREORDER,false);

//测试中序遍历
pTree->Traverse(BinaryTree::INORDER);
std::cout<<"root="<<pTree->GetRoot()->Node<<std::endl;
std::cout<<"root->left="<<pTree->GetRoot()->pLeft->Node<<std::endl;
std::cout<<"root->right="<<pTree->GetRoot()->pRight->Node<<std::endl;
pTree->Traverse(BinaryTree::INORDER,false);
//测试后序遍历
pTree->Traverse(BinaryTree::POSTORDER);
std::cout<<"root="<<pTree->GetRoot()->Node<<std::endl;
std::cout<<"root->left="<<pTree->GetRoot()->pLeft->Node<<std::endl;
std::cout<<"root->right="<<pTree->GetRoot()->pRight->Node<<std::endl;
pTree->Traverse(BinaryTree::POSTORDER,false);
//测试层序遍历
pTree->Traverse(BinaryTree::LEVELORDER);

system("pause");

deletepTree;

return0;
}