Struct node {
The int data;
Struct node * left;
Struct node * right;
};
//non-recursive code template
Sequence traversal first:
Void preOrder (struct node * root)
{
Struct node * * stack [500];
Int top=1;
Struct node * p=root;
While (p!=NULL | | top>=0)
{
If (p!=NULL)// start from here, it is difficult to understand this if else block I, making them step by step I know how to get the code, but I don't understand why do you go, what bosses want to?
{
Printf (" % d ", p - & gt; The data);
Stack [+ + top]=p;
P=p - & gt; The left;
}
The else// the else block feel very spiritual, in particular, how to better understand the else block?
{
P=stack [top --];
P=p - & gt; Right;
}
}
}
In the sequence traversal:
Void inOrder (struct node * root)
{
Struct node * * stack [500];
Int top=1;
Struct node * p=root;
While (p!=NULL | | top>=0)
{
If (p!=NULL)// is the same as the sequence traversal in doubt
{
Stack [+ + top]=p;
P=p - & gt; The left;
}
The else
{
P=stack [top --];
Printf (" % d ", p - & gt; The data);
P=p - & gt; Right;
}
}
}
After the sequence traversal:
Void postOrder (struct node * root)
{
Struct node * * stack [500];
Int top=1;
Struct node * p=root, * r=NULL;
While (p!=NULL | | top>=0)
{
If (p!=NULL)
{
Stack [+ + top]=p;
P=p - & gt; The left;
}
The else
{
P=stack [top];
If (p - & gt; Right!=NULL& & P - & gt; Right!=r)
P=p - & gt; Right;
The else
{
Top -;
Printf (" % d ", p - & gt; The data);
R=p;
P=NULL;
}
}
}
}
CodePudding user response:
This depends on individual thinking ability, thinking is actually quite simple, just look at your imagination to the stack into the stack control ability,Preorder traversal of the idea is, first traverse the parent node, then traverse the nodes on the left, after traversal right node,
So
If (p!=NULL) is whether the left node is empty, if not empty, that can still left, has been through the left node (print the parent node is table first traversal parent node, and then after the parent node pressure stack p=left node to traverse the left from the parent node)
Is the else if left node is empty, also said there was no left node (left) no, just right to traverse the nodes (the parent node stack, then p=parent node right to continue to traverse the nodes from right)
Sequence traversal in the way of thinking is that traverse the nodes left first, then traverse the parent node, after traversal right node
So
If (p!=NULL) and whether the left node is empty, if not empty, that can still left, has been through the left node (the parent node pressure stack, then p=left section of the parent node to traverse the nodes from left)
Else is if the left node is empty, that is, not the left node (to go to the left), the parent node stack, then print the parent node (said after traversal left node then traverse the parent node), then p=parent node right nodes continue to traverse the right node
Sequence traversal idea is that after first traversal left node, then traverse the nodes, right after traversal parent node
So
If (p!=NULL) and whether the left node is empty, if not empty, that can still left, has been through the left node (the parent node pressure stack, p=left node traversal first left from the parent node)
Else is if the left node is empty, that is, not the left node (left) no, just continue to traverse the node right, note that the parent node at this time and not the stack (because right after traversal to traverse the parent node, so the parent node for a will also stay in the stack, traverse the nodes to the stack from right), at the same time in order to avoid repeated traversal right node (because the parent node at the top of the stack will also get to the same parent node, this node will be the same from right), so use a r is to record the right node traversal, which is in the else if the meaning of the else, if the right node has been through, then the parent node will start out of the stack, and then print the parent node traverse the parent node (said)
CodePudding user response:
I suspect were written by your own code too
CodePudding user response:
All the recursion into non-recursive, can use list<> Their saving, stack, and then traverse list<> To solve