Establishment and traversal of binary tree
(1) Establishment of binary tree
Establish a binary tree by traversing in the first order and in the second order:
In the pre order traversal sequence of binary tree, the first element is always the value of the root node of the tree. In the middle order traversal sequence, the value of the node of the left subtree is located to the left of the value of the root node, and the value bit of the node of the right subtree
To the right of the value of the root node.
Recursive solution:
(1) If the preorder traversal is empty or the inorder traversal is empty or the number of nodes is less than or equal to 0, NULL is returned.
(2) Create a root node. The first data of preorder traversal is the data of the root node. If you find the position of the root node in the middle order traversal, you can know the preorder and middle order times of the left subtree and the right subtree respectively
Calendar sequence, reconstruct the left and right subtrees.
The binary tree is established by traversing in middle order and later order:
In the middle order traversal sequence of binary tree, the value of the node of the left subtree is on the left of the value of the root node, and the value of the node of the right subtree is on the right of the value of the root node. In the post order traversal sequence, the value of the node of the left subtree is to the left of the value of the node of the right subtree, and the value of the node of the right subtree is to the left of the value of the root node.
Recursive solution:
(1) If the middle order traversal is empty or the post order traversal is empty or the number of nodes is less than or equal to 0, NULL is returned.
(2) Create a root node. The last data of the post order traversal is the data of the root node. Find the position of the root node in the mid order traversal, and you can know the mid order and post order traversal of the left subtree and the right subtree respectively
Calendar sequence, reconstruct the left and right subtrees.
(2) Traversal of binary tree
Preorder traversal:
a. If the binary tree is empty, empty operation
b. If the binary tree is not empty, access the root node, traverse the left subtree in the preamble, and traverse the right subtree in the preamble
Middle order traversal:
a. If the binary tree is empty, the empty operation.
b. If the binary tree is not empty, the middle order traverses the left subtree, accesses the root node, and the middle order traverses the right subtree
Post order traversal:
a. If the binary tree is empty, empty operation
b. If the binary tree is not empty, the post order traverses the left subtree and the post order traverses the right subtree to access the root node
Sequence traversal:
Equivalent to breadth first search, using queue.
Queue initialization: press the root node into the queue. When the queue is not empty, perform the following operations: pop up a node and access it. If the left child node or right child node is not empty, press it into the queue.
1. Establish structure:
//Bonary tree node.
//Create a node with a structure, and then link the node with a pointer
typedef struct BTNpde{
char element;
BTNode* left;
BTNode* right;
};2. Storage
//A queue with a number of pointers.
//A queue storage node pointer
typedef struct BTNodePtrQueue{
BTNodePtr* nodePtrs;
int front;
int rear;
};3. Initialization:
//InitQueue initialization
ueuePtr initQueue(){
QueuePtr resultQueuePtr = (QueuePtr)malloc(sizeof(struct BTNodePtrQueue));
resultQueuePtr->nodePtrs = (BTNodePtr*)malloc(QUEUE_SIZE * sizeof(BTNodePtr));
resultQueuePtr->front = 0;
resultQueuePtr->rear = 1;
return resultQueuePtr;
4. Judge whether the queue is empty:
//Is the queue empty? Judge whether this queue is empty
bool isQueueEmpty(QueuePtr paraQueuePtr){
if((paraQueuePtr->front + 1)%QUEUE_SIZE == paraQueuePtr->rear){
return true;
}
return false;
}5. Add elements:
Add a pointer to the queue.Add node to queue
void enqueue(QueuePtr paraQueuePtr,BTNodePtr paraBtnodePtr){
printf("dront = %d,rear = %d.\r\n",paraQueuePtr->front,paraQueuePtr->rear);
if((paraQueuePtr->rear + 1)%QUEUE_SIZE == paraQueuePtr->front % QUEUEU_SIZE){
printf("Error,trying to enqueue %c.queue full.\r\n",paraBTNodePtr->element);
return;
}
paraQueuePtr->nodePtrs[paraQueuePtr->rear] = paraBTNodePtr;
paraQueuePtr->rear = (paraQueuePtr->rear + 1) % QUEUE_SIZE;
printf("enqueue %c ends.\r\n",paraBTNodePtr->element);
}
6. establish:
//Remove an element from the queue and return
//Move an element from the queue and return
BTNodePtr dequeue(QueuePtr paraQueuePtr){
if(isQueueEmpty(paraQueuePtr)){
printf("Error,empty queue\r\n");
return NULL;
}
paraQueuePtr->front = (paraQueuePtr->front + 1) % QUEUE_SIZE；
printf("dequeue %c ends.\r\n",paraQueuePtr->nodePtrs[paraQueuePtr->front]->element);
return paraQueuePtr->nodePtrs[paraQueuePtr->front];
}7 create a tree:
//Construct a BTNode using the given char.
//Create a "tree"
BTNodePtr constructBTNode(char paraChar){
BTNodePtr resultPtr = (BTNodePtr)malloc(sizeof(BTNode));
result->element = paraChar;
resultPtr->left = NULL;
resultPtr->right = NULL;
return resultPtr;
}
8. Use string to create binary tree
//Construct a binary tree using the given string.
//Create a binary tree using strings
BTNodePtr stringToBTree(char* paraString){
int i;
char ch;
//Use a queue to manage the pointers
QueuePtr tempQueuePtr = initQueue();
BTNodePtr resultHeader;
BTNodePtr tempParent, tempLeftChild,temRightChild;
i = 0;
ch = paraString[i];
resultHeader = constructBTNode(ch);
enqueue(tempQueuePtr,resultHeader);
while(!isQueueEmpty(tempQueuePtr)){
tempParent = dequeue(tempQueuePtr);
//The left child left subtree
i++;
ch = paraString[i];
if(ch == '#'){
tempParent->left = NULL;
}
else
{
tempLeftChild = constructBTNode(ch);
enqueue(tempQueuePtr, tempLeftChild);
tempParent->left = tempLeftChild;
}
//The right child right subtree
i++;
ch = paraString[i];
if(ch == '#'){
tempParent->right = NULL;
}
else
{
tempLeftChild = constructBTNode(ch);
enqueue(tempQueuePtr, tempRightChild);
tempParent->right = tempRightChild;
}
}
return resultHeader;
}9. Search layer by layer:
//Levelwise.
//Search layer by layer.
void levelwise(BTNodePtr paraTreePtr){
//Use a queue to manage the pointers
char tempString[100];
int i = 0;
QueuePtr tempQueuePtr = initQueue();
BTNodePtr tempNodePtr;
enqueue(tempQueuePtr, paraTreePtr);
while(!isQueueEmpty(tempQueuePtr)){
tempNodePtr - dequeue(tempQueuePtr);
//For output. output
tempString[i] = tempNodePtr->element;
i++;
if(tempNodePtr->left != NULL){
enqueue(tempQueuePtr, tempNodePtr->left);
}
if(tempNodePtr->right != NULL){
enqueue(tempQueuePtr, tempNodePtr->right);
}
}
tempString[i] = '\0';
printf("Levelwise: %s\r\n",tempString);
}10 three stool sequences
//Preorder.
//"Traversing the parent node before the child node" means to visit the parent node before the child node
void preorder(BTNodePtr tempPtr){
if(tempPtr == NULL){
return;
}
printf("%c",tempPtr->element);
preorder(tempPtr->left);
preorder(tempPtr->right);
}
//Inorder. Ergodic middle order
void inorder(BTNodePtr tempPtr){
if(tempPtr == NULL){
return;
}
inorder(tempPtr->left);
printf("%c",tempPtr->element);
inorder(tempPtr->right);
}
//Post order. Postorder traversal
void postorder(BTNodePtr tempPtr){
if(tempPtr == NULL){
return;
}
postorder(tempPtr->left);
postorder(tempPtr->right);
printf("%c",tempPtr->element);
}example:
//The entrance. get into
int main(){
BTNodePtr tempHeader;
tempHeader = constructBTNode('c');
printf("There is only one node. Preorder visit: ");
preorder(tempHeader);
printf("\r\n");
char* tempString = "acde#bf######"
tempHeader = stringToBTree(tempString);
printf("Preorder: ");
preorder(tempHeader);
printf("\r\n");
printf("Inorder: ");
inorder(tempHeader);
printf("\r\n");
printf("Postorder: ");
postorder(tempHeader);
printf("\r\n");
printf("Levelwise: ");
levelwise(tempHeader);
printf("\r\n");
return 1;
}All codes:
#include<stdio.h>
#include<malloc.h>
#define QUEUE_SIZE 5
//Bonary tree node.
//Create a node with a structure, and then link the node with a pointer
typedef struct BTNpde{
char element;
BTNode* left;
BTNode* right;
};
//A queue with a number of pointers.
//A queue storage node pointer
typedef struct BTNodePtrQueue{
BTNodePtr* nodePtrs;
int front;
int rear;
};
//InitQueue initialization
ueuePtr initQueue(){
QueuePtr resultQueuePtr = (QueuePtr)malloc(sizeof(struct BTNodePtrQueue));
resultQueuePtr->nodePtrs = (BTNodePtr*)malloc(QUEUE_SIZE * sizeof(BTNodePtr));
resultQueuePtr->front = 0;
resultQueuePtr->rear = 1;
return resultQueuePtr;
//Is the queue empty? Judge whether this queue is empty
bool isQueueEmpty(QueuePtr paraQueuePtr){
if((paraQueuePtr->front + 1)%QUEUE_SIZE == paraQueuePtr->rear){
return true;
}
return false;
}
Add a pointer to the queue.Add node to queue
void enqueue(QueuePtr paraQueuePtr,BTNodePtr paraBtnodePtr){
printf("dront = %d,rear = %d.\r\n",paraQueuePtr->front,paraQueuePtr->rear);
if((paraQueuePtr->rear + 1)%QUEUE_SIZE == paraQueuePtr->front % QUEUEU_SIZE){
printf("Error,trying to enqueue %c.queue full.\r\n",paraBTNodePtr->element);
return;
}
paraQueuePtr->nodePtrs[paraQueuePtr->rear] = paraBTNodePtr;
paraQueuePtr->rear = (paraQueuePtr->rear + 1) % QUEUE_SIZE;
printf("enqueue %c ends.\r\n",paraBTNodePtr->element);
}
//Remove an element from the queue and return
//Move an element from the queue and return
BTNodePtr dequeue(QueuePtr paraQueuePtr){
if(isQueueEmpty(paraQueuePtr)){
printf("Error,empty queue\r\n");
return NULL;
}
paraQueuePtr->front = (paraQueuePtr->front + 1) % QUEUE_SIZE；
printf("dequeue %c ends.\r\n",paraQueuePtr->nodePtrs[paraQueuePtr->front]->element);
return paraQueuePtr->nodePtrs[paraQueuePtr->front];
}
//Construct a BTNode using the given char.
//Create a "tree"
BTNodePtr constructBTNode(char paraChar){
BTNodePtr resultPtr = (BTNodePtr)malloc(sizeof(BTNode));
result->element = paraChar;
resultPtr->left = NULL;
resultPtr->right = NULL;
return resultPtr;
}
//Construct a binary tree using the given string.
//Create a binary tree using strings
BTNodePtr stringToBTree(char* paraString){
int i;
char ch;
//Use a queue to manage the pointers
QueuePtr tempQueuePtr = initQueue();
BTNodePtr resultHeader;
BTNodePtr tempParent, tempLeftChild,temRightChild;
i = 0;
ch = paraString[i];
resultHeader = constructBTNode(ch);
enqueue(tempQueuePtr,resultHeader);
while(!isQueueEmpty(tempQueuePtr)){
tempParent = dequeue(tempQueuePtr);
//The left child left subtree
i++;
ch = paraString[i];
if(ch == '#'){
tempParent->left = NULL;
}
else
{
tempLeftChild = constructBTNode(ch);
enqueue(tempQueuePtr, tempLeftChild);
tempParent->left = tempLeftChild;
}
//The right child right subtree
i++;
ch = paraString[i];
if(ch == '#'){
tempParent->right = NULL;
}
else
{
tempLeftChild = constructBTNode(ch);
enqueue(tempQueuePtr, tempRightChild);
tempParent->right = tempRightChild;
}
}
return resultHeader;
}
//Levelwise.
//Search layer by layer.
void levelwise(BTNodePtr paraTreePtr){
//Use a queue to manage the pointers
char tempString[100];
int i = 0;
QueuePtr tempQueuePtr = initQueue();
BTNodePtr tempNodePtr;
enqueue(tempQueuePtr, paraTreePtr);
while(!isQueueEmpty(tempQueuePtr)){
tempNodePtr - dequeue(tempQueuePtr);
//For output. output
tempString[i] = tempNodePtr->element;
i++;
if(tempNodePtr->left != NULL){
enqueue(tempQueuePtr, tempNodePtr->left);
}
if(tempNodePtr->right != NULL){
enqueue(tempQueuePtr, tempNodePtr->right);
}
}
tempString[i] = '\0';
printf("Levelwise: %s\r\n",tempString);
}
//Preorder.
//Preorder traversal means to visit the parent node first and then the child node
void preorder(BTNodePtr tempPtr){
if(tempPtr == NULL){
return;
}
printf("%c",tempPtr->element);
preorder(tempPtr->left);
preorder(tempPtr->right);
}
//Inorder. Ergodic middle order
void inorder(BTNodePtr tempPtr){
if(tempPtr == NULL){
return;
}
inorder(tempPtr->left);
printf("%c",tempPtr->element);
inorder(tempPtr->right);
}
//Post order. Postorder traversal
void postorder(BTNodePtr tempPtr){
if(tempPtr == NULL){
return;
}
postorder(tempPtr->left);
postorder(tempPtr->right);
printf("%c",tempPtr->element);
}
//The entrance. get into
int main(){
BTNodePtr tempHeader;
tempHeader = constructBTNode('c');
printf("There is only one node. Preorder visit: ");
preorder(tempHeader);
printf("\r\n");
char* tempString = "acde#bf######"
tempHeader = stringToBTree(tempString);
printf("Preorder: ");
preorder(tempHeader);
printf("\r\n");
printf("Inorder: ");
inorder(tempHeader);
printf("\r\n");
printf("Postorder: ");
postorder(tempHeader);
printf("\r\n");
printf("Levelwise: ");
levelwise(tempHeader);
printf("\r\n");
return 1;
}