- 前序
void PreOrderIteration1(pTree node)
{
if(node == nullptr) return;
stack<pTree> s;
pTree p = node;
s.push(p);
while(!s.empty())
{
p = s.top();
cout<<p->_data<<" ";
s.pop();
if(p->_rchild) s.push(p->_rchild);
if(p->_lchild) s.push(p->_lchild);
}
}
void PreOrderIteration2(pTree node)
{
stack<pTree> s;
pTree p = node;
while(!s.empty() || p != nullptr)
{
while(p != nullptr) //不断左探的过程
{
cout<< p->_data << " ";
s.push(p);
p = p->_lchild;
}
if(!s.empty()) //最后访问右孩子
{
p = s.top();
s.pop();
p = p->_rchild;
}
}
}
- 中序
void InOrderIteration(pTree node)
{
if (node == nullptr) return;
pTree p = node;
stack<pTree> s;
while(!s.empty() || p != nullptr)
{
while(p != nullptr)
{
s.push(p);
p = p->_lchild;
}
if(!s.empty())
{
p = s.top();
cout << p->_data <<" ";
s.pop();
p = p->_rchild;
}
}
}
- 后序
void PostOrderIteration(pTree node)
{
pTree pCur = node; //用来保存当前节点的指针
pTree pPre = nullptr; //保存上一个访问的节点的指针
stack<pTree> s;
s.push(pCur);
while(s.!empty())
{
pCur = s.top();
if((pCur->_lchild == nullptr && pCur->_rchild == nullptr) || //没有左右孩子的情况
(pPre != nullptr && (pPre == pCur->_lchild || pPre == pCur->_rchild))) //左右孩子访问过的情况
{
cout << pCur->_data << " ";
s.pop();
pPre = pCur;
}
else
{
if(pCur->_rchild != nullptr) s.push(pCur->_rchild);
if(pCur->_lchild != nullptr) s.push(pCur->_lchild);
}
}
}
本文地址:https://blog.csdn.net/Mr_Helloworld_/article/details/107499305
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的,请 点击进行留言回复,万千网友为您解惑!
网友评论