A wave of binary tree traversal problem C++ solution example sharing
- 2020-05-09 18:55:15
- OfStack
Title 1:
enters a 2-bit tree, prints each node of the tree layer by layer from top to bottom, and prints the same layer from left to right.
Input sample:
8
/ /
6 10
/ / / /
5 7 9 11
Output sample:
8 6 10 5 7 9 11Thought analysis:
abstracts a two-fork tree into three nodes: root node, left node and right node.
can be sequentially traversed to get the effect of output by line.
For the left subtree, saves the entire left subtree as long as it saves its root node. (1 sample of right subtree)
For two subtrees other than the root node, always accesses the root node of the left subtree first, and then the root node of the right subtree.
can therefore use queue storage.
Code implementation (GCC was compiled and passed) :
#include "stdio.h"
#include "stdlib.h"
//2 Fork tree node
#define size 7
//2 Fork tree node definition
typedef struct node
{
int data;
struct node *left;
struct node *right;
}BTree;
int printLine(BTree * root);
BTree * CreatTree(int a[],int n);
int main(void)
{
int array[size] = {8,6,10,5,7,9,11};
BTree * root;
root = CreatTree(array,size);
printLine(root);
printf("\n");
return 0;
}
int printLine(BTree * root)
{
BTree * queue[size], *p;
int front,rear;
front = rear = 0;
rear = (rear+1)%size;
queue[rear] = root;
// The loop ends with the queue empty
while(front != rear)
{
// A root out of a queue
front = (front +1)%size;
p = queue[front];
printf("%3d",p->data);
// The left child is not free, the team is not satisfied to join the team
if(p->left && ((rear+1)%size != front))
{
rear = (rear+1)%size;
queue[rear] = p->left;
}
// The right child is not empty, the team is not satisfied to join the team
if(p->right && ((rear+1)%size != front))
{
rear = (rear+1)%size;
queue[rear] = p->right;
}
// When the line is full, report an error
if((rear+1)%size == front)
{
printf(" Insufficient queue space, error ....\n");
return 0;
}
}
return 1;
}
// Create from the array 2 Fork sort tree
BTree * CreatTree(int a[],int n)
{
BTree * root ,*p,*cu,*pa;
int i;
root = (BTree *)malloc(sizeof(BTree));
root->data = a[0];
root->left = root->right =NULL;
for(i=1;i<n;i++)
{
p = (BTree *)malloc(sizeof(BTree));
p->data = a[i];
p->left = p->right =NULL;
cu = root;
while(cu)
{
pa = cu;
if(cu->data > p->data)
cu = cu->left;
else
cu = cu->right;
}
if(pa->data > p->data)
pa->left = p;
else
pa->right = p;
}
return root;
}
Topic 2:
Enter an array of integers to determine if the array is the result of a sequential traversal of a 2-bit search tree.
If return true, otherwise return false.
For example, enter 5, 7, 6, 9, 11, 10, 8, because this sequence of 1 integers is the sequential traversal result of the following tree:
8
/ \
6 10
/ \ / \
5 7 9 11
So return true.
If you type 7, 4, 6, 5, none of the tree's sequentially traversed results in this sequence, so false is returned.
Ideas:
Two-fork search features: the left subtree each value is less than the root, the right subtree each value is greater than the heel
Characteristics of sequential traversal: the last one is the root, convenient order, left and right follow. recursive
Well, the summary can be:
The last one is the root. The nodes of the left subtree are the ones with a continuous number smaller than the root at the beginning, and the nodes of the right subtree are the ones with a continuous number larger than the root (both the left and right subtrees may be empty) at the beginning, and then they are recursively described.
The code is described as follows (GCC was compiled and passed) :
#include "stdio.h"
#include "stdlib.h"
int isPostorderResult(int a[],int n);
int helper(int a[],int s,int e);
int main(void)
{
int a[7] = {5,7,6,9,11,10,8};
int b[4] = {7,4,6,5};
int tmp;
tmp = isPostorderResult(a,7);
printf("%d",tmp);
return 0;
}
int isPostorderResult(int a[],int n)
{
return helper(a,0,n-1);
}
int helper(int a[],int s,int e)
{
int i,j,root;
if(s == e)
return 1;
for(i=0;i<e && a[i]<a[e];i++);
if(i != 0 && helper(a,s,i-1) == 0)
return 0;
for(j=i;j<e && a[j]>a[e];j++);
if(j==e && helper(a,i,j-1) == 1)
return 1;
else
return 0;
}
Title 3:
Enter a 2-bit search tree and convert the tree to its mirror image. That is, in the transformed 2-bit search tree, the nodes of the left subtree are all larger than the nodes of the right subtree.
The tree image is transformed by recursion and loop.
For example, input:
8
/ \
6 10
/\ /\
5 7 9 11
Output:
8
/ \
10 6
/\ /\
11 9 7 5
Analysis:
Recursive programming is simpler
visits a node, exchanges left and right children as long as it is not empty, and recurses the left and right subtrees separately.
The essence of non-recursion is that we have to manually push the stack, and the idea is 1
The code is as follows (GCC was compiled and passed) :
#include "stdio.h"
#include "stdlib.h"
#define MAXSIZE 8
typedef struct node
{
int data;
struct node * left;
struct node * right;
}BTree;
void swap(BTree ** x,BTree ** y);// Swap left and right children
void mirror(BTree * root);// Recursive implementation of function declarations
void mirrorIteratively(BTree * root);// Non-recursive implementation of function declarations
BTree * CreatTree(int a[],int n);// create 2 Fork tree (produces 2 Cross sort tree)
void Iorder(BTree * root);// The middle order traverses to see the results
int main(void)
{
int array[MAXSIZE] = {5,3,8,7,2,4,1,9};
BTree * root;
root = CreatTree(array,MAXSIZE);
printf(" Before the conversion: \n");
Iorder(root);
printf("\n After the transformation: \n");// Two transformations, and before the change 1 to
mirror(root);
mirrorIteratively(root);
Iorder(root);
printf("\n");
return 0;
}
void swap(BTree ** x,BTree ** y)
{
BTree * t = * x;
* x = * y;
* y = t;
}
void mirror(BTree * root)
{
if(root == NULL)// The end condition
return;
swap(&(root->left),&(root->right));// exchange
mirror(root->left);// Left subtree recursion
mirror(root->right);// Right subtree recursion
}
void mirrorIteratively(BTree * root)
{
int top = 0;
BTree * t;
BTree * stack[MAXSIZE+1];
if(root == NULL)
return;
// Manually push stack, pop stack
stack[top++] = root;
while(top != 0)
{
t = stack[--top];
swap(&(t->left),&(t->right));
if(t->left != NULL)
stack[top++] = t->left;
if(t->right != NULL)
stack[top++] = t->right;
}
}
// produce 2 Fork sort tree
BTree * CreatTree(int a[],int n)
{
BTree * root ,*p,*cu,*pa;
int i;
root = (BTree *)malloc(sizeof(BTree));
root->data = a[0];
root->left = root->right =NULL;
for(i=1;i<n;i++)
{
p = (BTree *)malloc(sizeof(BTree));
p->data = a[i];
p->left = p->right =NULL;
cu = root;
while(cu)
{
pa = cu;
if(cu->data > p->data)
cu = cu->left;
else
cu = cu->right;
}
if(pa->data > p->data)
pa->left = p;
else
pa->right = p;
}
return root;
}
// In the sequence traversal
void Iorder(BTree * root)
{
if(root)
{
Iorder(root->left);
printf("%3d",root->data);
Iorder(root->right);
}
}