Realization of Non-recursive Algorithm for Preorder, Inorder and Postorder Traversal of Binary Linked List

Article directory

  • Realization of Non-recursive Algorithm for Preorder, Inorder and Postorder Traversal of Binary Linked List
    • preorder traversal
    • Inorder traversal
    • post order traversal

Implementation of non-recursive algorithm for preorder, inorder and postorder traversal of binary linked list

The good things are written in the front: I have been unable to remember the output results of several traversals. I know that I have seen the animation shared by the blog, and it is really easy to understand! Not much to say, go directly to the three traversal processes of the portal binary linked list

Preorder traversal

The key to the preorder traversal non-recursive algorithm: How to find the root pointer of the right subtree of a node after preorder traversing the entire left subtree. Careful analysis of the traversal process shows that after visiting a node, the node should be saved to the stack, so that the right subtree of the node can be found through it.
Assuming that the root pointer to traverse the binary tree is bt, there may be two situations:
①: bt != nulllptr, indicating that the current binary tree is not empty. At this time, the value of the root node bt should be output and bt should be saved in the stack, ready to continue traversing the left subtree of bt
②: bt == nullptr, indicating that the binary tree with bt as the root pointer has been traversed, and bt is the left subtree pointed to by the top pointer of the stack. If the stack is not empty, pop the top pointer of the stack and find the root pointer of the right subtree according to the top pointer of the stack and assign it to bt, and continue traversing. If the stack is empty, it means that the entire binary tree has been traversed.

Code Implementation

#include <iostream>

using namespace std;

template<class T>
struct BiNode
{<!-- -->
T data;
BiNode* lchild, *rchild;
};

template<class T>
class BiTree
{<!-- -->
public:
//constructor to create a binary tree
BiTree()
{<!-- -->
root = Create(root);
}

//The destructor releases the storage space of each node
~BiTree()
{<!-- -->
this->Release(root);
}

// Preorder traversal of the binary tree
void PreOrder();

private:
BiNode<T>* Creat(BiNode<T>* bt);//constructor call
void Release(BiNode<T>* bt);//Destructor call
BiNode<T>* root;//The head pointer pointing to the root node
};

template<class T>
void BiTree<T>::PreOrder()
{<!-- -->
BiNode<T>* bt = root;
BiNode<T>* s[100];//Sequential stack, up to 100 node pointers
int top = -1;//initialize the stack
while (bt != nullptr || top != -1)//Exit the loop only when bt is empty and the stack is empty at the same time
{<!-- -->
while (bt != nullptr)
{<!-- -->
cout << bt->data;
\t\t\t
//root pointer bt into the stack
top ++ ;
s[top] = bt;
bt = bt->lchild;
}

//if the left subtree is empty
if (bt == nullptr)
{<!-- -->
//Pop the stack and traverse the right subtree
bt = s[top];
top--;
bt = bt->rchild;
}
}
}

template<class T>
BiNode<T>* BiTree<T>::Creat(BiNode<T>* bt)
{<!-- -->
char ch;
cout << "Please enter the preorder traversal sequence of the extended binary tree, one character at a time: ";
cin >> ch;//Input the data information of the node, assuming it is a character
if (ch == '#')
{<!-- -->
bt = nullptr;
}
else
{<!-- -->
bt = new BiNode<T>;
bt->data = ch;
bt->lchild = Creat(bt->lchild);//Create the left subtree recursively
bt->rchild = Creat(bt->rchild);//Create the right subtree recursively
}

return bt;
}

template<class T>
void BiTree<T>::Release(BiNode<T>* bt)
{<!-- -->
if (bt == nullptr)
{<!-- -->
return;
}
else
{<!-- -->
Release(bt->lchild);
Release(bt->rchild);
delete bt;//Release the root node
}
}

int main()
{<!-- -->
BiTree<char> t{<!-- -->};
cout << "The preorder traversal sequence of the binary tree is: ";
t. PreOrder();

return 0;
}

/*
Please enter the preorder traversal sequence of the extended binary tree, one character at a time: a
Please enter the preorder traversal sequence of the extended binary tree, one character at a time: b
Please enter the preorder traversal sequence of the extended binary tree, one character at a time: #
Please enter the preorder traversal sequence of the extended binary tree, one character at a time: #
Please enter the preorder traversal sequence of the extended binary tree, one character at a time: c
Please enter the preorder traversal sequence of the expanded binary tree, one character at a time: d
Please enter the preorder traversal sequence of the extended binary tree, one character at a time: #
Please enter the preorder traversal sequence of the extended binary tree, one character at a time: #
Please enter the preorder traversal sequence of the extended binary tree, one character at a time: e
Please enter the preorder traversal sequence of the extended binary tree, one character at a time: #
Please enter the preorder traversal sequence of the extended binary tree, one character at a time: #
The preorder traversal sequence of the binary tree is: abcde
*/

Inorder traversal

In the in-order traversal of a binary tree, the operation of accessing a node occurs when the left subtree of the node has been traversed and the right subtree is ready to be traversed. Therefore, when a node is encountered during the traversal, it cannot be accessed immediately, but Push it onto the stack, wait until its left subtree has been traversed, then pop it from the stack and access it. The non-recursive algorithm of the in-order traversal only needs to move the output operation in the non-recursive algorithm of the pre-order traversal to after the pop operation bt = S[top--].

Code Implementation

#include <iostream>

using namespace std;

template <class T>
struct BiNode
{<!-- -->
T data;
BiNode* lchild, *rchild;
};

template <class T>
class BiTree
{<!-- -->
public:
BiTree()
{<!-- -->
root = Create(root);
}

void InOrder();

~BiTree()
{<!-- -->
Release(root);
}
private:
BiNode<T>* Create(BiNode<T>* bt);
void Release(BiNode<T>* bt);
BiNode<T>* root;
};
template <class T>
void BiTree<T>::InOrder()
{<!-- -->
BiNode<T>* bt = root;
BiNode<T>* s[100];
int top = -1;

while (bt != nullptr || top != -1)
{<!-- -->
while (bt != nullptr)
{<!-- -->
s[ + + top] = bt;//Push into the stack
bt = bt->lchild;
}
if (top != -1)
{<!-- -->
bt = s[top--];// pop the stack
cout << bt->data;
bt = bt->rchild;
}
}
}

template <class T>
BiNode<T>* BiTree<T>::Creat(BiNode<T>* bt)
{<!-- -->
char ch;
cout << "Please enter the inorder traversal sequence of the extended binary tree, one character at a time: ";
cin >> ch;
if (ch == '#')
{<!-- -->
return nullptr;
}
else
{<!-- -->
bt = new BiNode<T>;//less this step
bt->data = ch;
//Recursively call Creat initialization
bt->lchild = Create(bt->lchild);
bt->rchild = Creat(bt->rchild);
}
return bt;
}

template <class T>
void BiTree<T>::Release(BiNode<T>* bt)
{<!-- -->
if (bt == nullptr)
{<!-- -->
return;
}
else
{<!-- -->
Release(bt->lchild);
Release(bt->rchild);
delete bt;//Can't forget to delete the pointer
}
}

int main()
{<!-- -->
BiTree<char> t{<!-- -->};
cout << "The inorder traversal of the binary tree is: ";
t.InOrder();

return 0;
}

/*
Please enter the inorder traversal sequence of the extended binary tree, one character at a time: a
Please enter the inorder traversal sequence of the extended binary tree, one character at a time: b
Please enter the inorder traversal sequence of the extended binary tree, one character at a time: #
Please enter the inorder traversal sequence of the extended binary tree, one character at a time: #
Please enter the inorder traversal sequence of the extended binary tree, one character at a time: c
Please enter the inorder traversal sequence of the extended binary tree, one character at a time: d
Please enter the inorder traversal sequence of the extended binary tree, one character at a time: #
Please enter the inorder traversal sequence of the extended binary tree, one character at a time: #
Please enter the inorder traversal sequence of the extended binary tree, one character at a time: e
Please enter the inorder traversal sequence of the extended binary tree, one character at a time: #
Please enter the inorder traversal sequence of the extended binary tree, one character at a time: #
The inorder traversal of the binary tree is: badce
*/

Post-order traversal

Post-order traversal is different from the other two. After traversing the left subtree, since the right subtree has not yet been traversed, the top node of the stack cannot be popped out of the stack, but its right subtree is found through the top node of the stack. When traversing Only when the right subtree is completed can the top node of the stack be popped out and accessed.
To distinguish the different processing of the top node of the stack, set the flag variable flag. flag=1 means that after traversing the left subtree, the top node of the stack cannot be popped; flag=2 means that after traversing the right subtree, the top node of the stack can be popped and accessed.

Code Implementation

#include <iostream>

using namespace std;

template <class T>
struct BiNode
{<!-- -->
T data;
BiNode<T>* lchild, * rchild;
};

template <class T>
struct element
{<!-- -->
BiNode<T>* ptr;
int flag;//flag=1 means that the left subtree has been traversed, flag=2 means that the right subtree has been traversed
};

template <class T>
class BiTree
{<!-- -->
public:
BiTree()
{<!-- -->
root = Create(root);
}

void PostOrder();

~BiTree()
{<!-- -->
Release(root);
}
private:
BiNode<T>* Create(BiNode<T>* bt);
void Release(BiNode<T>* bt);
BiNode<T>* root;
};

template <class T>
void BiTree<T>::PostOrder()
{<!-- -->
BiNode<T>* bt = root;
element<T> s[100];
int top = -1;
while (bt != nullptr || top != -1)
{<!-- -->
while (bt != nullptr)
{<!-- -->
top ++ ;
s[top].ptr = bt;
s[top].flag = 1;
bt = bt->lchild;
}
while(top != -1 & amp; & amp; s[top].flag == 2)
{<!-- -->
bt = s[top--].ptr;
cout << bt->data;
}
if (top != -1)
{<!-- -->
//bt = bt->rchlid;
//s[ + + top].ptr = bt;
s[top].flag = 2;
bt = s[top].ptr->rchild;
}
else
{<!-- -->
bt = nullptr;
}
}
}

template <class T>
BiNode<T>* BiTree<T>::Creat(BiNode<T>* bt)
{<!-- -->
char ch;
cout << "Please enter the post-order traversal sequence of the extended binary tree, one character at a time: ";
cin >> ch;
if (ch == '#')
{<!-- -->
return nullptr;
}
else
{<!-- -->
bt = new BiNode<T>;
bt->data = ch;
bt->lchild = Create(bt->lchild);
bt->rchild = Creat(bt->rchild);
}
return bt;
}

template <class T>
void BiTree<T>::Release(BiNode<T>* bt)
{<!-- -->
if (bt == nullptr)
{<!-- -->
return;
}
else
{<!-- -->
Release(bt->lchild);
Release(bt->rchild);
delete bt;
}
}

int main()
{<!-- -->
BiTree<char> t{<!-- -->};
cout << "The post-order traversal sequence of the binary tree is: ";
t.PostOrder();
\t
return 0;
}