说明：算法中用到了结构体，也用到了递归的方法，你看看怎么样，祝你好运！
#include"stdio.h"
typedef
char
elemtype
typedef
struct
node
//定义链表结构
{
elemtype
data
//定义节点值
struct
note
*lchild
//定义左子节点值
struct
note
*rchild
//定义右节点值
}btree
preorder(btree
*root)
//前序遍历
{
if(roof!=null)
//如果不是空节点
{
printf("%c\n",root->data)
//输出当前节点
preorder(root->lchild)
//递归前序遍历左子节点
preorder(root->rchild)
//递归前序遍历右子节点
}
return
//结束
}
BinaryTree.h:/********************************************************************
created:2006/07/04
filename: BinaryTree.h
author:李创
http://www.cppblog.com/converse/
purpose:演示二叉树的算法
*********************************************************************/
#ifndef BinaryTree_H
#define BinaryTree_H
＃i nclude <stdlib.h>
＃i nclude <stack>
class BinaryTree
{
private:
typedef int Item
typedef struct TreeNode
{
ItemNode
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)
voidDetroyTreeImpl(PTreeNode pTreenode)
voidPreTraverseImpl(PTreeNode pTreenode) // 递归前序遍历树
voidInTraverseImpl(PTreeNode pTreenode) // 递归中序遍历树
voidPostTraverseImpl(PTreeNode pTreenode) // 递归后序遍历树
voidNoRecPreTraverseImpl(PTreeNode pTreenode) // 非递归前序遍历树
voidNoRecInTraverseImpl(PTreeNode pTreenode) // 非递归中序遍历树
voidNoRecPostTraverseImpl(PTreeNode pTreenode) // 非递归后序遍历树
voidLevelTraverseImpl(PTreeNode pTreenode)
PTreeNode m_pRoot // 根结点
// 采用STL里面的stack作为模拟保存链表结点的stack容器
typedef std::stack<BinaryTree::PTreeNode>TreeNodeStack
}
#endif
BinaryTree.cpp:
/********************************************************************
created:2006/07/04
filename: BinaryTree.cpp
author:李创
http://www.cppblog.com/converse/
purpose:演示二叉树的算法
*********************************************************************/
＃i nclude <iostream>
＃i nclude <assert.h>
＃i nclude <queue>
＃i nclude "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)// 如果这个叶子结点是右子树
{
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
}
}
}
}
// 按照树的层次从左到右访问树的结点
void BinaryTree::LevelTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return
// 层序遍历用于保存结点的容器是队列
std::queue<PTreeNode>NodeQueue
PTreeNode pNode
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)
}
}
}
main.cpp
/********************************************************************
created:2006/07/04
filename: main.cpp
author:李创
http://www.cppblog.com/converse/
purpose:测试二叉树的算法
*********************************************************************/
＃i nclude "BinaryTree.h"
＃i nclude <stdio.h>
＃i nclude <stdlib.h>
＃i nclude <time.h>
＃i nclude <iostream>
void DisplayArray(int array[], int length)
{
int i
for (i = 0i <lengthi++)
{
printf("array[%d] = %d\n", i, array[i])
}
}
void CreateNewArray(int array[], int length)
{
for (int i = 0i <lengthi++)
{
array[i] = rand() % 256 + i
}
}
int main()
{
int array[10]
srand(time(NULL))
// 创建数组
CreateNewArray(array, 10)
DisplayArray(array, 10)
BinaryTree *pTree = new BinaryTree(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")
delete pTree
return 0
}
