Binary Tree is the most often used Data structure in the programming world and is also the basis of other complex data structures. So as a Computer Science student, it is very important to understand it thoroughly. The following paragraph is quoted by Standford Univ.’s Website explaining Binary Tree:
A binary tree is made of nodes, where each node contains a “left” pointer, a “right” pointer, and a data element. The “root” pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller “subtrees” on either side. A null pointer represents a binary tree with no elements — the empty tree. The formal recursive definition is: a binary tree is either empty (represented by a null pointer), or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a binary tree.
The following code section is my Binary Tree implementation in C++:
//define the node of tree;
typedef struct _Node
{
char value;
struct _Node* left;
struct _Node* right;
bool tag;//used to the non-recursion postorder algorithm
} Node;
You can see the definition of the tree node has a bool tag member. It is used to implement the second post order traversal algorithm, and the algorithm is implemented in the function void postorder2(Node* tree).For each traversal method I have implement 2 versions. One is the normal version which uses the recursion call, the other use the stack method.
// recursion version of traverse the tree in preorder
void preorder(Node* tree)
{
if(!tree)
return;
cout<<tree->value;
preorder(tree->left);
preorder(tree->right);
}
// non-recursion version
void preorder2(Node* tree)
{
stack<Node*> sn;
Node* p=tree;
while(!sn.empty() || p) {
while(p)//go to the deepest left child
{
cout<<p->value;
sn.push(p);
p=p->left;
}
if(!sn.empty())
{
p=sn.top();
p=p->right;// go to the right child
sn.pop();
}
}
}
// recursion version of traverse the tree in inorder
void inorder(Node* tree)
{
if(!tree)
return;
inorder(tree->left);
cout<<tree->value;
inorder(tree->right);
}
// non-recursion version
void inorder2(Node* tree)
{
stack<Node*> sn;
Node* p=tree;
sn.push(p);
while(!sn.empty())//stack not empty
{
// go to the deepest left child
while((p=sn.top())!=NULL)
sn.push(p->left);
sn.pop(); //pop the NULL pointer;
if(!sn.empty())
{
p=sn.top();
cout<<p->value;
sn.pop();
sn.push(p->right);
}
}
}
// recursion version of traverse the tree in postorder
void postorder(Node* tree)
{
if(tree==NULL)
return;
else
{
postorder(tree->left);
postorder(tree->right);
cout<<tree->value;
}
}
//non-recursion version
//use a tag to represent whether a node's right child has been visited.
void postorder2(Node* tree)
{
stack<Node*> sn;
Node* p=tree;
while(!sn.empty() || p!=NULL) {
while(p!=NULL) {
sn.push(p);
p=p->left;
}
if(!sn.empty()) {
p=sn.top();
//it can been visited after the right child is visited
if(p->tag) {
cout<<p->value;
sn.pop();
p=NULL;
//now that both the right and left child of the current
//node have been visited
}
else {
// now the node's right child has been visited
p->tag=true;
p=p->right;
}
}
}
}
There is an addition version void postorder3(Node* tree) for post order traversal which does not need the bool tag member. I just use Node* r_child" to store the information whether the current node’s right child has been visited yet or not. If the current node’s right child has been visited, then r_child should equal it. In this situation we can visit the current node and at the same time we let the r_child be the current node.
// non-recursion version use a pointer which points
// to the current node's right child which has been visited.
// In this implementation we do not need to use the node's "tag" field.
void postorder3(Node* tree)
{
stack<Node*> sn;
Node* p=tree;
//the important pointer that store the right child
//wehther has been visited or not
Node* r_child=NULL;
while(p!=NULL || !sn.empty()) {
while(p!=NULL) {
sn.push(p);
p=p->left;
}
if(!sn.empty()) {
p=sn.top();
if(p->right==NULL || p->right==r_child)
//the right child has been visited or has no right child
{
cout<<p->value;
sn.pop();
r_child=p;
p=NULL;
}
else
p=p->right;
}
}
}
Another useful algorithm is that a binary tree can be constrcuted from its preorder traversal and inorder traversal. Here are the rules you should know:
- The first element of the preorder traversal list is the root of the tree.
- Find the position of the element specified by the step in the inorder traversal list. The elements on the left side of the position constitute the left subtree of the element and the elements on the right side constitute the right subtree.
- Determine the position specified in the step 1 and apply it on the left and right subtree recursively. You can notice that the length of the left subtree and right subtree are equal in the each recursive call, thus pr-pl=ir-il, where “pl” and “pr” is the left and right border of the current preorder traversal list and “il” and “ir” is the same in the inorder traversal. They are both the parameters of the
create_fipfunction call.
/////////////////////////////////////////////////////////////
// create the tree from preorder and inorder traversal list
// string& pre => the preorder list;
// string& in => the inorder list
// int pl => left index of the preorder list;
// int pr => right index of the preorder list;
// int il => left index of the inorder list;
// int ir => right index of the inorder list;
//////////////////////////////////////////////////////////////
Node* create_fip(string& pre,string& in,int pl,int pr,int il,int ir)
{
if(pl>pr)return NULL;
if(il>ir)return NULL;
char element = pre[pl];
Node* root = new Node;
root->value=element;
int i=il;
while(in[i]!=element && i<=ir)
i++;
root->left=create_fip(pre,in,pl+1,pl+(i-il),il,i-1);
root->right=create_fip(pre,in,pl+(i-il)+1,pr,i+1,ir);
return root;
}