C++ binary tree several traversal algorithm
- 2020-04-01 21:33:36
- OfStack
1. Preorder/in-order/post-order traversal (recursive implementation)
//The former sequence traversal
void BT_PreOrder(BiTreePtr pNode){
if (!pNode) return;
visit(pNode);
BT_PreOrder(pNode->left);
BT_PreOrder(pNode->right); }
//In the sequence traversal
void BT_PreOrder(BiTreePtr pNode){
if (!pNode) return;
BT_PreOrder(pNode->left);
visit(pNode);
BT_PreOrder(pNode->right);}
//Void BT_PreOrder(BiTreePtr pNode){& NBSP;
if (!pNode) return;
BT_PreOrder(pNode->left);
BT_PreOrder(pNode->right);
visit(pNode);}
2. Preorder traversal (non-recursive implementation)
//Use stack to achieve
void BT_PreOrderNoRec1(BiTreePtr pNode){
stack<BiTreePtr> s;
while (!pNode || !s.empty())
{
if (!pNode)
{
visit(pNode);
s.push(pNode);
pNode = pNode->left;
}
else
{
pNode = s.pop();
pNode = pNode->right;
}
}
}
//Use stack to achieve
void BT_PreOrderNoRec2(BiTreePtr pNode){
if (!pNode)
{
stack<BiTreePtr> s;
s.push(pNode);
while (!s.empty())
{
BiTreePtr pvNode = s.pop();
visit(pvNode);
s.push(pvNode->right);
s.push(pvNode->left);
}
}}
//
Non-stack implementation Each node contains the parent node pointer and isVisited The default is false State variable And the binary tree contains a head node
void BT_PreOrderNoRec3(BiTreePtr pNode){
while (!pNode)
//Exit & NBSP when tracing back to the head node that points to the root node;
{
if( !pNode->bVisited )
//Determine whether or not it has been visited & NBSP;
{
visit(pNode);
pNode->isVisited = true;
}
if ( pNode->left && !pNode->left->isVisited )
pNode = pNode->left;
else if( pNode->right && !pNode->right->isVisited )
pNode = pNode->right;
else
//Back
pNode = pNode->parent;
}}
3. Middle order traversal (non-recursive implementation)
//Use stack to achieve
void BT_InOrderNoRec1(BiTreePtr pNode){
stack<BiTreePtr> s;
while (!pNode || !s.empty())
{
if (!pNode)
{
s.push(pNode);
pNode = pNode->left;
}
else
{
pNode = s.pop();
visit(pNode);
pNode = pNode->right;
}
}}
//The state variable of each node containing the parent node pointer and isVisited (false by default) is implemented without a stack, and the binary tree contains a header node
void BT_InOrderNoRec2(BiTreePtr pNode){
while (!pNode)
//Exits when backtracking to the header node that points to the root node
{
while (pNode->left && !pNode->left->isVisited)
pNode = pNode->left;
if (!pNode->isVisited)
{
visit(pNode);
pNode->isVisited=true;
}
if (pNode->right && !pNode->right->isVisited)
pNode = pNode->right;
else
pNode = pNode->parent;
}}
4. Sequential traversal (non-recursive implementation)
void BT_PostOrderNoRec(BiTreePtr pNode){
if(!pNode) return;
stack<BiTreePtr> s;
s.push(pNode);
while (!s.empty())
{
BiTreePtr pvNode = s.pop();
if (pvNode->isPushed)
//To indicate that its left and right subtrees have been pushed, visit the node & cake;
visit(pvNode);
else
{
if (pvNode->right)
{
pvNode->right->isPushed = false;
S.push(pvNode->right);
}
if (pvNode->left)
{
pvNode->left->isPushed = false;
s.push(pvNode->left);
}
pvNode->isPushed = true;
s.push(pvNode);
}
}}
5. Sequence traversal (using queues)
void BT_LevelOrder(BiTreePtr pNode){
if (!pNode) return;
queue<BiTreePtr> q;
q.push(pNode);
BiTreePtr pvNode;
while (!q.empty())
{
pvNode = q.pop();
visit(pvNode);
if (pvNode->left)
q.push(pvNode->left);
if (pvNode->right)
q.push(pvNode->right);
}}