Remember before
I sent out my resume last week as a back-end development engineer. This week, THE interviewer of Tencent gave me a video interview. During the interview he asked about binomial trees. Binary tree related algorithm questions, in the interview very very many times, so I have prepared before the interview. Today, I will talk about binary tree in detail in combination with interview questions, and analyze the establishment method and traversal process of binary tree storage structure with examples.
Interview questions
Interviewer: Your resume says you are familiar with data structures. How about binary tree traversal?
Me :(it doesn’t bother me)
The first sequence traversal
The root node is accessed first, followed by the left child and then the right child
A recursive algorithm
void PreOrder1(BTREE bt) // Recursion starts with root traversal
{
if (bt)
{
if(bt->data ! =The '#')
{
printf(" %c", bt->data);// The node is not empty, print the node value
}
PreOrder1(bt->lchild);// Access the left and right nodes in sequencePreOrder1(bt->rchild); }}Copy the codeNon-recursive algorithms
void PreOrder2(BTREE p)// Non-recursive root traversal, first visits the root node, then visits the left child and then the right child
{
int top = - 1;
node *Q[N];
while(p ! =NULL|| top ! =- 1)
{
while(p ! =NULL)
{
if(p->data ! =The '#')
{
printf(" %c", p->data);
}
Q[++top] = p;
p = p->lchild;
}
if(top ! =- 1) { p = Q[top--]; p = p->rchild; }}}Copy the codeIn the sequence traversal
The left child is accessed first, then the root node and then the right child
A recursive algorithm
void InOrder1(BTREE bt)// recursive order traversal
{
if (bt)
{
InOrder1(bt->lchild);// Access the left node first
if(bt->data ! =The '#')
{
printf(" %c", bt->data);// The node is not empty, print the node value
}
InOrder1(bt->rchild);// Access the right node first}}Copy the codeNon-recursive algorithms
void InOrder2(BTREE p)// Non-recursive sequential traversal, first visits the left child, then the root node, then the right child
{
int top = - 1;
node *Q[N];
while(p ! =NULL|| top ! =- 1)
{
while(p ! =NULL)
{
Q[++top] = p;
p = p->lchild;
}
if(top ! =- 1)
{
p = Q[top--];
if(p->data ! =The '#')
{
printf(" %c",p->data); } p = p->rchild; }}}Copy the codeAfter the sequence traversal
The left child is accessed first, then the right child and then the root node
A recursive algorithm
void PostOrder1(BTREE bt)// after the sequence traversal
{
if (bt)
{
PostOrder1(bt->lchild);// Access the left and right child nodes first
PostOrder1(bt->rchild);
if(bt->data ! =The '#')
{
printf(" %c", bt->data);// Access the root node}}}Copy the codeNon-recursive algorithms
void PostOrder2(BTREE p)// Non-recursive sequential traversal, first visits the left child, then the right child, then the root node
{
int top = - 1;
node *Q[N];
int flag[N] = { 0 };
while(p ! =NULL|| top ! =- 1)
{
while(p ! =NULL)
{
top++;
Q[top] = p;
flag[top] = 1;
p = p->lchild;
}
while(top ! =- 1 && flag[top] == 2)
{
if(Q[top]->data ! =The '#')
{
printf(" %c", Q[top]->data); top--; }}if(top ! =- 1)
{
flag[top] = 2; p = Q[top]->rchild; }}}Copy the codeInterviewer: That’s a good answer. Is there any other way to iterate
I:…
After a few seconds of silence, I (which doesn’t bother me) : There’s also a sort of sequential traversal
Sequence traversal
Start at the root and work your way down, traversing left to right for each level
// sequence traversal
void Sequense(BTREE bt)// Create a stack, press the root node, left child, and right child, and print the top element of the stack
{
node *Q[N];
node *p;
int front = 0, top = 0;
if(bt ! =NULL)
{
Q[++top] = bt;// Push the root node to the stack
while (front < top) / / traversal stack
{
p = Q[++front];
if(p->data ! =The '#')
{
printf(" %c", p->data);// Prints the top element of the stack
}
if (p->lchild)
{
Q[++top] = p->lchild;// Push the left child to the stack
}
if (p->rchild)
{
Q[++top] = p->rchild;// Push the right child to the stack}}}}Copy the codeSummary of ergodic algorithm
Interviewer: How do you tell if it’s a complete binary tree
Me :(it doesn’t bother me)
Judge a complete binary tree
-
Traverses the binary tree level by level, traversing all nodes from left to right at each level
-
If the current node has a right child, but no left child, then it’s not a complete binary tree
-
If the current node has left children but no right children, then all nodes after it must be leaf nodes, otherwise it is not a complete binary tree
-
If the current node has left and right children, continue traversing
int Compnode(BTREE G)// Check whether it is a complete binary tree
{
node *D[N], *p; // create a queue D[N]
int front = 0, last = 0; //front is the head pointer and last is the tail pointer
int tree_signal = 1;//tree_signal is a complete binary tree flag
int odd_signal = 1;//odd_signal is a flag to determine whether a node has no left children
if(G ! =NULL)
{
last++;
D[last] = G; // Push the root node to the end of the queue
while(front ! = last) { front++; p = D[front];if (p->lchild == NULL ||(p->lchild)->data == The '#') //*p node has no left child
{
odd_signal = 0;
if(p->rchild ! =NULL&& (p->rchild)->data ! =The '#') // No left children but right children, not a complete binary tree
tree_signal = 0;
}
else //*p node has left subtree
{
if (odd_signal == 1) // There is no node with no left child
{
last++; // The left child enters the queue
D[last] = p->lchild;
if (p->rchild == NULL || (p->rchild)->data == The '#') //*p has left children but no right children
{
odd_signal = 0;
}
else
{
last++; // The right child enters the queueD[last] = p->rchild; }}else // There exists a node with a left child, not a complete binary tree
{
tree_signal = 0; }}}}else
{
tree_signal = 0;// Assume that the empty tree is not a complete binary tree
}
return tree_signal;
}
Copy the codeconclusion
Let’s have fun. Let’s have fun. Don’t joke about the interview.
Although the traversal of binary tree is simple, there are various traversal methods, including recursive algorithm and non-recursive algorithm. Once you are asked, make sure you give a full answer and don’t forget to get to the point. Binary tree related algorithm questions, the number of times in the interview is very, very many, we should put the binary tree and other data structure foundation before the interview.