古人云:温故而知新可以为师矣。平时使用的都是线性的数据结构,非线性的都忘记的差不多了。于是,又看了看。回味一下。
下面的这个文章,是温习后自己写了二叉树的3种遍历方式。各位看官如果发现小弟的实现有不对的地方,还麻烦不吝赐教。3Q。上代码。
二叉树的相关代码:
/*
只是为了实现二叉树的几种遍历方式。L:左,M:根,R:右
测试的二叉树的结构是这样的
1
2 3
4 5 6 7
这里创建二叉树的CreateTree函数暂时没实现,当然,内存释放的问题,也没有考虑。
目前只是为了理解3种遍历树的方式。
*/
#include <iostream>
using namespace std;
class CNode
{
public:
CNode(int Va)
{
m_Value = Va;
m_Left = 0;
m_Right = 0;
}
CNode* m_Left;
CNode* m_Right;
int m_Value;
};
class CBinaryTree
{
public:
CBinaryTree()
{
m_pNode = NULL;
}
//待实现
~CBinaryTree()
{
}
//创建2叉树,暂时临时创建
void CreateTree()
{
m_pNode = new CNode(1);
CNode* pNode2 = new CNode(2);
CNode* pNode3 = new CNode(3);
CNode* pNode4 = new CNode(4);
CNode* pNode5 = new CNode(5);
CNode* pNode6 = new CNode(6);
CNode* pNode7 = new CNode(7);
m_pNode->m_Left = pNode2;
m_pNode->m_Right = pNode3;
pNode2->m_Left = pNode4;
pNode2->m_Right = pNode5;
pNode3->m_Left = pNode6;
pNode3->m_Right = pNode7;
}
//中根序遍历
void LMR_Order(CNode* pNode)
{
if(pNode == 0)
{
}
else
{
//左孩子操作
LMR_Order(pNode->m_Left);
//当前根节点操作
OperNode( pNode );
//右孩子操作
LMR_Order(pNode->m_Right);
//是不是很EASY。左,根,右。
}
}
//先根序遍历
void MLR_Order(CNode* pNode)
{
if(pNode == 0)
{
}
else
{
OperNode( pNode );
MLR_Order(pNode->m_Left);
MLR_Order(pNode->m_Right);
}
}
//后根序遍历
void LRM_Order(CNode* pNode)
{
if(pNode == 0)
{
}
else
{
LRM_Order(pNode->m_Left);
LRM_Order(pNode->m_Right);
OperNode( pNode );
}
}
//对每个NODE的动作,这里只是输出每个NODE的值
void OperNode(CNode* pNode)
{
if(pNode)
cout << "pNode->m_Value = " << pNode->m_Value << endl;
}
CNode* m_pNode;
};
调用代码:
int main(int argc,char** argv)
{
CBinaryTree btree;
btree.CreateTree();
cout << "中序遍历树" << endl;
btree.LMR_Order(btree.m_pNode);
cout << "前序遍历树" << endl;
btree.MLR_Order(btree.m_pNode);
cout << "后序遍历树" << endl;
btree.LRM_Order(btree.m_pNode);
return 0;
}