Improvement of binary tree traversal algorithm (non recursive implementation)

Improvement of binary tree traversal algorithm

The depth first traversal algorithms of binary tree are implemented by recursive functions, which is very inefficient. The reason is that the system calls a stack and does complex operations such as protecting the site and restoring the site, so that the traversal can be realized by very simple code. Non recursive stack traversal algorithm can be used to improve the efficiency of non recursive stack traversal algorithm.

Non recursive implementation of depth first traversal algorithm of binary tree

(1) Preorder traversal non recursive algorithm

To write its traversal non recursive algorithm, its main task is to use its own defined stack to replace the function of the system stack.

Taking the binary tree shown in Figure 1 as an example, the process is shown in Figure 2

Initial state of stack empty

  1. Node 1 is stacked.
  2. Out of the stack, output the top node 1 of the stack, and put the left and right child nodes (2 and 4) of 1 into the stack; The right child enters the stack first, and the left child enters the stack later, because the access to the left child is prior to the right child, and those who enter the stack later will access out of the stack first.
  3. Out of the stack, output the top node 2 of the stack, and put the left and right child nodes (3 and 5) of 2 into the stack.
  4. Out of the stack, output the top node 3 of the stack. 3 is a leaf node without children. In this step, there is no node in the stack.
  5. Out of stack, output stack top node 5.

Exit the stack and output the top node 4 of the stack. At this time, the stack is empty and enters the final state.

The traversal sequence is 1, 2, 3, 5, 4.

The code is as follows

void preorderNonrecursion(BTNode *bt)
{
    if(bt != NULL)
    {
        BTNode *Stack[maxSize];				//Define a stack
        int top = -1;						//Initialization stack
        BTNode *p;
        Stack[++top] = bt;					//Root node stack
        while(top != -1)					//Stack empty loop end
        {
            p = Stack[top--];				//Exit the stack and output the top node of the stack
            Visit(p);						//Visit() is a function that accesses p
            if(p->rchild != NULL)			//If the right child of the top node of the stack exists, the right child enters the stack
            	Stack[++top] = p->rchild;
            if(p->lchild != NULL)			//If the left child of the top node of the stack exists, the left child enters the stack
            	Stack[++top] = p->lchild;
        }
    }
}
(2) Middle order traversal non recursive algorithm

Similar to preorder traversal, the binary tree in Figure 1 is traversed in order. The process of each node entering and leaving the stack is shown in Figure 3.

The initial stack is empty.

  1. Node 1 enters the stack, and 1 left child exists.
  2. Node 2 is stacked, and 2 left children exist.
  3. Node 3 into the stack, 3 left child does not exist.
  4. Out of stack, the right child of output stack top node 3 and 3 does not exist.
  5. Out of the stack, output the top node of the stack. 2. The right child exists, 5. The right child enters the stack, and 5. The left child does not exist.
  6. Out of the stack, the right child of output stack top node 5 and 5 does not exist.
  7. Out of the stack, output the top node of the stack. 1. The right child exists, 4. The right child enters the stack, and 4. The left child does not exist.

Exit the stack and output the top node 4 of the stack. At this time, the stack is empty and enters the final state.

The traversal sequence is 3, 2, 5, 1, 4.

As can be seen from the above steps, the middle order non recursive traversal process is as follows:

  1. Start root node stacking
  2. The loop performs the following operations: if the left child at the top node of the stack exists, the left child enters the stack; If the left child of the stack top node does not exist, exit the stack and output the stack top node, and then check whether its right child exists. If so, the right child enters the stack.
  3. When the stack is empty, the algorithm ends.

The code is as follows

void inorderNonrecursion(BTNode *bt)
{
    if(bt != NULL)
    {
        BTNode *Stack[maxSize];
        int  top = -1;
        BTNode *p;
        p = bt;
        /*The lower loop completes the middle order traversal. Note: in Figure 3, the stack will be empty in the process of entering and leaving the stack in 7, but the traversal has not ended at this time. Because the right subtree of the root node has not been traversed, p is not empty at this time. Maintain the cycle according to this point*/
        while(top != -1 || p != NULL)
        {
            while(p != NULL)		//If the left child exists, the left child enters the stack
            {
                Stack[++top] = p;
                p = p->lchild;
            }
            if(top != -1)			//When the stack is not empty, exit the stack and output the exit node
            {
                p = Stack[top--];
                Visit(p);
                p = p->rchild;
            }
        }
    }
}
(3) Postorder traversal non recursive algorithm

First, write out the sequence of first order traversal and second order traversal of the binary tree in Figure 1.

Preorder traversal sequence: 1, 2, 3, 5, 4

Post order traversal sequence: 3, 5, 2, 4, 1

Reverse the backward traversal sequence to obtain:

Backward traversal sequence: 1, 4, 2, 5, 3

It is found that there is a little connection between the inverse postorder traversal sequence and the preorder traversal sequence. The inverse postorder traversal sequence is just the result of the exchange of the traversal sequence of the left and right subtrees in the preorder traversal process, as shown in Figure 4.

Therefore, we only need to exchange the traversal order of the left and right subtrees in the previous non recursive preorder traversal algorithm to get the inverse postorder traversal sequence, and then reverse the inverse postorder traversal sequence to get the postorder traversal sequence. Therefore, two stacks are needed. One stack stack1 is used to assist in reverse postorder traversal (the traversal method of exchanging the traversal order of the left and right subtrees of the first order traversal is called reverse postorder traversal), and the traversal result sequence is pressed into another stack stack2, and then all the elements in stack2 are out of the stack. The obtained sequence is the postorder traversal sequence. The specific process is shown in Figure 5.

The initial stack is empty.

  1. Node 1, such as stack1.
  2. Stack1 element is out of the stack, and the out of stack node 1 is put into stack2. The left and right children of node 1 exist, the left child node 2 is put into stack1, and the right child node 4 is put into stack1. Here, pay attention to the comparison with the process of first traversing in and out of the stack. It happens that the left and right children are put into the stack in order to realize the exchange of access order.
  3. stack1 element is out of the stack, and the out of stack node 4 is put into stack2. The left and right children of node 4 do not exist.
  4. Stack1 element is out of the stack, and the out of stack node 2 is put into stack2. The left and right children of node 2 exist, the left child node 3 is put into stack1, and the right child node 5 is put into stack1.
  5. stack1 element is out of the stack, and the out of stack node 5 is put into stack2.
  6. stack1 element is out of the stack, and the out of stack node 3 is put into stack2.

At this time, stack1 is empty, and the top-down elements in stack2 are: 3, 5, 2, 4 and 1, which is exactly the post order traversal sequence.

The code is as follows:

void postorderNonrecursion(BTNode *bt)
{
    if(bt != NULL)
    {
        /*Define two stacks*/
        BTNode *Stack1[maxSize];int top1 = -1;
        BTNode *Stack2[maxSize];int top2 = -1;
        BTNode *p = NULL;
        Stack1[++top1] = bt;
        while(top1 != -1)
        {
            p = Stack1[top1--];
            Stack2[++top2] = p;//Note the difference between this and preorder traversal. The output is changed to Stack2
            /*Note the difference between the two if statements below and the preorder traversal. The stacking order of the left and right children is opposite*/
            if(p->lchild != NULL)
                Stack1[++top1] = p->lchild;
            if(p->rchild != NULL)
                Stack1[++top1] = p->rchild;
        }
        while(top2 != -1)
        {
            /*The out of stack sequence is the post order traversal sequence*/
            p = Stack2[top2--];
            Visit(p);
        }
    }
}

->rchild;
}
while(top2 != -1)
{
/The out of stack sequence is the post order traversal sequence/
p = Stack2[top2–];
Visit§;
}
}
}

Tags: Algorithm data structure Binary tree

Posted by Verrou on Sun, 22 May 2022 02:06:38 +0300