首页 | 编程语言 | 网站建设 | 游戏天堂 | 冲浪宝典 | 网络安全 | 操作系统 | 软件时空 | 硬件指南 | 病毒相关 | IT 认证
软讯网络 > 编程语言 > C/C++ > 二叉树遍历算法集合(前中后序遍历的递归和非递归算法,层序遍历算法)
【标  题】：二叉树遍历算法集合(前中后序遍历的递归和非递归算法,层序遍历算法)
【关键字】：
【来  源】：http://www.cppblog.com/converse/archive/2006/07/08/9577.html

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

C++博客 - 创系的技术博客 - 二叉树遍历算法集合(前中后序遍历的递归和非递归算法,层序遍历算法)
有勇气来改变可以改变的事情，有胸怀来接受不可改变的事情，有智慧来分辨两者的不同。
二叉树遍历算法集合(前中后序遍历的递归和非递归算法,层序遍历算法)
费了两天时间写的,包括前中后序遍历的递归和非递归算法,还有层序遍历总共2*3 + 1 = 7中遍历二叉树的算法,感觉其中后序遍历的非递归算法比较困难,想了很久最后的实现还是不够优雅,请大家指正~~

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

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

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

#ifndef?BinaryTree_H
#define?BinaryTree_H

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

class?BinaryTree
{
private:
????typedef?int?Item;
????typedef?struct?TreeNode
????{
????????Item????????Node;
????????TreeNode*???pRight;
????????TreeNode*???pLeft;

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

????}TreeNode,?*PTreeNode;

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

????BinaryTree(Item?Array[],?int?nLength);
????~BinaryTree();

????PTreeNode?GetRoot()
????{
????????return?m_pRoot;
????}

????//?遍历树的对外接口
????//?指定遍历类型和是否是非递归遍历,默认是递归遍历
????void?Traverse(TraverseType?traversetype,?bool?bRec?=?true);

private:
????PTreeNode???CreateTreeImpl(Item?Array[],?int?nLength);
????void????????DetroyTreeImpl(PTreeNode?pTreenode);

????void????????PreTraverseImpl(PTreeNode?pTreenode);????????//?递归前序遍历树
????void????????InTraverseImpl(PTreeNode?pTreenode);????????//?递归中序遍历树
????void????????PostTraverseImpl(PTreeNode?pTreenode);????????//?递归后序遍历树

????void????????NoRecPreTraverseImpl(PTreeNode?pTreenode);????//?非递归前序遍历树
????void????????NoRecInTraverseImpl(PTreeNode?pTreenode);????//?非递归中序遍历树
????void????????NoRecPostTraverseImpl(PTreeNode?pTreenode);????//?非递归后序遍历树

????void????????LevelTraverseImpl(PTreeNode?pTreenode);

????PTreeNode???m_pRoot;????????//?根结点

????//?采用STL里面的stack作为模拟保存链表结点的stack容器
????typedef?std::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(Item?Array[],?int?nLength)
????:?m_pRoot(NULL)
{
????assert(NULL?!=?Array);
????assert(nLength?>?0);

????m_pRoot?=?CreateTreeImpl(Array,?nLength);
}

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

//?按照中序递归创建树
BinaryTree::PTreeNode?BinaryTree::CreateTreeImpl(Item?Array[],?int?nLength)
{
????int?mid?=?nLength?/?2;
????PTreeNode?p?=?new?TreeNode(Array[mid]);

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

????return?p;
}

void?BinaryTree::DetroyTreeImpl(PTreeNode?pTreenode)
{
????if?(NULL?!=?pTreenode->pLeft)
????{
????????DetroyTreeImpl(pTreenode->pLeft);
????}
????if?(NULL?!=?pTreenode->pRight)
????{
????????DetroyTreeImpl(pTreenode->pRight);
????}

????delete?pTreenode;
????pTreenode?=?NULL;
}

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

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

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

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

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

//?递归前序遍历树
void?BinaryTree::PreTraverseImpl(PTreeNode?pTreenode)
{
????if?(NULL?==?pTreenode)
????????return;

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

????PreTraverseImpl(pTreenode->pLeft);

????PreTraverseImpl(pTreenode->pRight);
}

//?非递归前序遍历树
void?BinaryTree::NoRecPreTraverseImpl(PTreeNode?pTreenode)
{
????if?(NULL?==?pTreenode)
????????return;

????TreeNodeStack?NodeStack;
????PTreeNode?pNode;
????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);????????????????//?当前结点的右子树根结点入栈
????????}
????}
}

//?中序遍历树
//?中序遍历输出的结果应该和用来初始化树的数组的排列顺序一致
void?BinaryTree::InTraverseImpl(PTreeNode?pTreenode)
{
????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);
????}
}

//?非递归中序遍历树
void?BinaryTree::NoRecInTraverseImpl(PTreeNode?pTreenode)
{
????if?(NULL?==?pTreenode)
????????return;

????TreeNodeStack?NodeStack;
????PTreeNode?pNode;
????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);
????????}
????}
}

//?后序遍历树
void?BinaryTree::PostTraverseImpl(PTreeNode?pTreenode)
{
????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;
}

//?非递归后序遍历树
void?BinaryTree::NoRecPostTraverseImpl(PTreeNode?pTreenode)
{
????if?(NULL?==?pTreenode)
????????return;

????TreeNodeStack?NodeStack;
????PTreeNode?pNode1,?pNode2;
????NodeStack.push(pTreenode);
????pNode1?=?pTreenode->pLeft;
????
????bool?bVisitRoot?=?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)????//?如果这个叶子结点是右子树