在二叉树的应用中，很多使用二叉树的操作都是通过遍历来进行节点的修改。
所以对于遍历而言是学习二叉树的要点，今天就来总结一下。
假设二叉树的结构为：
计算
安全
数据库
网络和加速
企业服务
template<class T>
struct BinaryTreeNode
{
BinaryTreeNode(const T& x)
:_data(x)
,_left(NULL)
,_right(NULL)
{}
T _data;
BinaryTreeNode<T>* _left;
BinaryTreeNode<T>* _right;
};前序遍历：
void PrevOrder()
{
_PrevOrder(_root);
cout<<endl;
}
void _PrevOrder(BinaryTreeNode<T>* root)
{
if (root==NULL)
return;
cout<<root->_data<<" ";
_PrevOrder(root->_left);
_PrevOrder(root->_right);
}
void PrevOrder_Non_R()
{
stack<BinaryTreeNode<T>*> s;
if (_root)
s.push(_root);
while(!s.empty())
{
BinaryTreeNode<T>* top = s.top();
cout<<top->_data<<" ";
s.pop();
if (top->_right)
s.push(top->_right);
if (top->_left)
s.push(top->_left);
}
cout<<endl;
}
2.中序遍历：
void InOrder()
{
_InOrder(_root);
cout<<endl;
}
void _InOrder(BinaryTreeNode<T>* root)
{
if (root == NULL)
return;
_InOrder(root->_left);
cout<<root->_data<<" ";
_InOrder(root->_right);
}
void InOrder_Non_R()
{
stack<BinaryTreeNode<T>*> s;
BinaryTreeNode<T>* cur = _root;
while (cur || !s.empty())
{
// 1.压左节点
while (cur)
{
s.push(cur);
cur = cur->_left;
}
// 取栈顶节点数据访问
// 前序遍历top节点的右树
if (!s.empty())
{
BinaryTreeNode<T>* top = s.top();
s.pop();
cout<<top->_data<<" ";
cur = top->_right;
}
}
cout<<endl;
}3.后序遍历：
void PostOrder()
{
_PostOrder(_root);
cout<<endl;
}
void _PostOrder(BinaryTreeNode<T>* root)
{
if (root == NULL)
return;
_PostOrder(root->_left);
_PostOrder(root->_right);
cout<<root->_data<<" ";
}
void PostOrder_Non_R()
{
stack<BinaryTreeNode<T>*> s;
BinaryTreeNode<T>* cur = _root;
BinaryTreeNode<T>* prevVisited = NULL;
while (cur || !s.empty())
{
// 1.压左节点
while (cur)
{
s.push(cur);
cur = cur->_left;
}
BinaryTreeNode<T>* top = s.top();
if (top->_right == NULL
|| top->_right == prevVisited)
{
cout<<top->_data<<" ";
s.pop();
prevVisited = top;
}
else
{
cur = top->_right;
}
}
cout<<endl;
}4.层次遍历
void LevelOrder()
{
queue<BinaryTreeNode<T>* > q;
if (_root)
q.push(_root);
while(!q.empty())
{
BinaryTreeNode<T>* front = q.front();
cout<<front->_data<<" ";
q.pop();
if (front->_left)
q.push(front->_left);
if (front->_right)
q.push(front->_right);
}
cout<<endl;
}以上
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
