The first sequence traversal In the sequence traversal After the sequence traversal
Root – left subtree – right subtree Left subtree – Root subtree – Right subtree Left subtree right subtree root

Recursive implementation:

// order traversal first
void preOrder(Btree T){
	if(T){
		putchar(T->data); preOrder(T->lchild); preOrder(T->rchild); }}// middle order traversal
void inOrder(Btree T){
	if(T){
		inOrder(T->lchild);
		putchar(T->data); inOrder(T->rchild); }}// after the sequence traversal
void postOrder(Btree T){
	if(T){
		postOrder(T->lchild);
		postOrder(T->rchild);
		putchar(T->data); }}Copy the code

Non-recursive implementation:

Stack based recursive elimination:

Recursion is when a subroutine (or function) calls itself either directly or indirectly through a series of calling statements. The execution process requires that each node interrupt calls other methods, and the environment information of the interrupt node must be recorded, so that the original program can continue to execute from the last interrupt position after the call ends and the result is returned. In the computer, this effect is achieved through a stack structure (stack: advanced and then out) :

However, the implementation efficiency of recursive algorithm is low, because recursion needs to be repeatedly pushed onto the stack, and the time and space costs are relatively large.

(Recursion, by its very nature, is more convenient for programmers than for machines.)

To avoid this overhead, recursion needs to be eliminated in two main ways:

1. For simple recursion, use iteration to replace recursion;

2. Using stack method: using artificial stack simulation system stack. (This method is versatile, but still recursive in nature, the difference being that humans do what computers do.)

The non-recursive process implemented by stack can be divided into the following steps:

  1. Set up a work stack for storing recursive work records, including arguments, return addresses, etc.
  2. Pushes the arguments and return address passed from the calling function to the stack;
  3. The recursive decomposition process is simulated by loop, and the parameters and return addresses of the recursive process are stacked layer by layer. When the recursive end condition is met, the stack is unstacked one layer at a time and the result is returned to the next layer until the stack is empty.

Non-recursive traversal binary tree:

Sequential traversal: root – left subtree – right subtree

Algorithm idea:

Starting from the root of the binary tree, set the root to the current node P and do the following:

  1. Print while traversing, and store in the stack (current node P is the root node at the beginning) → print the data of current node P first → add current node P to the stack again → set the left child as the current node if the left child exists → repeat this operation until the bottom left corner of the left subtree of the binary tree is reached;
  2. If the right child of the current node P exists, set the right child to the current node P (enter the right subtree)→ Return to Step 1 and repeat 1 and 2 until the stack is empty.
			void preOrder(Btree T){
			        Bnode *p=T;
			        Bnode *stack[MaxSize];
			        int top=0;
			        if(T==NULL) {return;
			        }
			        while(p! =NULL||top>0) {// Print while traversing, and store in the stack. Later, you need to use these root nodes to enter the right subtree
			                while(p! =NULL) {putchar(p->data);
			                        stack[top++]=p;
			                        p=p->lchild;
			                }
			                // When p is null, the root and the left subtree are traversed, and it is time to enter the right subtree
			                if(top>0){
			                        p=stack[--top];
			                        p=p->rchild;
			                }
			        
			        /* / if(p! =NULL){ putchar(p->data); stack[top++]=p; p=p->lchild; }else{ p=stack[--top]; p=p->rchild; } * /}}Copy the code

Middle traversal: left subtree – root subtree – right subtree

Algorithm idea:

Starting from the root of the binary tree, set the root to the current node P and do the following:

  1. The current node P is pushed into the stack (the current node P is the root node at the beginning) → If the current node P has a left child → set the left child as the current node P → repeat the operation until the bottom left corner of the left subtree of the binary tree is reached;
  2. Remove the top element of the stack, set the element of the stack to the current node P → print the data of the node P;
  3. If the current node P has a right child, set the right child as the current node P → go back to Step 1 and repeat 1, 2 and 3 until the stack is empty.
			void inOrder(Btree T){
			        Bnode *p=T;
			        Bnode *stack[MaxSize];
			        int top=0;
			        if(T==NULL) {return;
			        }
			        while(p! =NULL||top>0) {// duplicate the left child of the current node
			                while(p! =NULL) {stack[top++]=p;
			                        p=p->lchild;
			                }
			                / / out of the stack
			                if(top>0){
			                        p=stack[--top];
			                        putchar(p->data);
			                        p=p->rchild;
			                }
			        
			        /* if(p! =NULL){ stack[top++]=p; p=p->lchild; }else{ p=stack[--top]; putchar(p->data); p=p->rchild; } * /}}Copy the code

Back-order traversal: left subtree – right subtree – root

Algorithm idea:

Declare two Pointers to nodes (for temporary storage) : current node -pcur; -plast, the last accessed node, set the root node to the current node pCur:

  1. The current node is pushed (the current node is the root node at the beginning) → If the current node has a left child → set the left child as the current node → repeat this operation until the bottom left corner of the left subtree of the binary tree is reached;

  2. Take the top element and set it to the current node pCur:

  • If the current node pCur has no right child or has just been accessed by the right child (pLast was the last accessed node) → the top element of the stack is removed, and the data of the current node pCur is printed → Assign the current node pCur to pLast→ empty the current node;
  • If the current node pCur has a right child → set the right child as the current node (traversing the right subtree) → go back to Step 1 and repeat 1 and 2 until the stack is empty.
			void postOrder(Btree T){
			        Bnode *pCur=T,*pLast;//pCur is the current node, pLast is the last accessed node
			        Bnode *stack[MaxSize];// define a stack to hold Pointers to nodes
			        int top=0;// Top of stack pointer
			        if(T==NULL) {return;
			        }
			        while(pCur! =NULL||top>0) {// Repeatedly push the left child of the current node until pCur is moved to the bottom of the left subtree
			                while(pCur! =NULL) {stack[top++]=pCur;
			                        pCur=pCur->lchild;
			                }
			                
			                if(top>0){
			                        pCur=stack[top- 1];// fetch the top element of the stack
			                        if(pCur->rchild==NULL||pCur->rchild==pLast){// If the current node has no right child or the right child has just accessed
			                                putchar(pCur->data);// Prints the current node
			                                pLast=pCur;// Assign the current node to pLast
			                                pCur=NULL;// Empty the current node
			                                top--;// The top element goes off the stack
			                        }else{ pCur=pCur->rchild; }}/* if(pCur! =NULL){ stack[top++]=pCur; pCur=pCur->lchild; }else{ pCur=stack[top-1]; / / remove the stack elements if (pCur - > rchild = = NULL | | pCur - > rchild = = pLast) {/ / if the current node without children or children right right has just visited putchar (pCur - > data); // Print the current node pLast=pCur; // Assign the current node to pLast pCur=NULL; top--; }else{ pCur=pCur->rchild; }} * /}}Copy the code