二叉树是很有用的一种数据结构，遍历则是其基本操作，这里列出实是保证完整性。几个备用的结构定义和函数：
|
//二叉树节点定义
class TreeNodeElement
{
public:
TreeNodeElement();
TreeNodeElement(int value);
TreeNodeElement(int value,TreeNodeElement* l,TreeNodeElement* r);
~TreeNodeElement();
private:
public:
int _value;
TreeNodeElement* _l;
TreeNodeElement* _r;
};
typedef TreeNodeElement* TreeNode; |
|
//递归实现（visit）
void Visit(TreeNode node)
{
cout<<node->_value<<" ";
} |
二叉树前序遍历的递归和非递归实现：
|
//递归遍历
void PreRetriveATree(TreeNode root,void (* visit)(TreeNode))
{
if (root)
{
(*visit)(root);
PreRetriveATree(root->_l,visit);
PreRetriveATree(root->_r,visit);
}
} |
|
//非递归遍历，添加#include <stack>
void PreRetriveATreeWithoutRecurve(TreeNode root,void (* visit)(TreeNode))
{
stack<TreeNode> tree;
TreeNode tmp = NULL;
//根节点入栈
tree.push(root);
while (!tree.empty())
{
tmp = tree.top();
tree.pop();
(*visit)(tmp);
if (tmp->_r != NULL)
{
tree.push(tmp->_r);
}
if (tmp->_l != NULL)
{
tree.push(tmp->_l);
}
}
} |
发表评论 
打印本文
推荐本文
加入收藏
返回顶部
关闭窗口
