# Implementation of non recursive and recursive insert operation and traversal code of binary sort tree in C

2020-11-10 14:49:21

# C The non recursive and recursive insert operation of binary sort tree and the code implementation of middle order traversal 【 Can run 】

``````#include <stdio.h>
#include <stdlib.h>

typedef int KeyType;

typedef struct  node
{
KeyType  key;
struct node* lchild, * rchild;
}BSTNode, * BSTree;
// Binary sort tree recursive insert operation
int InsertBST1(BSTree& T, int k) {
if (T == NULL) {// The original tree is empty , The newly inserted node is the root node

T = (BSTree)malloc(sizeof(BSTNode));
if (T == NULL) {
return 0;// Memory allocation failure
}
T->key = k;
T->lchild = T->rchild = NULL;
return 1;// return 1,  Insert the success
}
else if (k == T->key) {// There are nodes with the same keyword in the tree , Insert the failure
return 0;
}
else if (k < T->key) {
return InsertBST1(T->lchild, k); // If the inserted value is less than the node value , Then recursively insert the function to find
}
else {
return InsertBST1(T->rchild, k); // If the inserted value is greater than the node value , Then recursively insert the function to find
}
}
// Binary sort tree non recursive insert operation
int  InsertBST2(BSTree& T, KeyType  k)
{
BSTree   q, s;// Add two nodes q,s
s = (BSTree)malloc(sizeof(BSTNode));// Assign a new node
if (s == NULL) {
return 0;// Memory allocation failure
}
s->key = k;// The data stored in the new node is the inserted value
s->lchild = NULL;
s->rchild = NULL;
if (T == NULL)// If the current node is empty, the newly assigned node will be s Assign to the current node
{
T = s;
return  1;
}
q = T;//
while (q) {//
BSTree p = q;
if (k == q->key){// If the inserted value is equal to the value of the node , The newly allocated memory is released
free(s);
return 0;
}
if (k < q->key){// If the inserted value is less than the node value , Let the node be equal to its left child node
q = q->lchild;
if (q == NULL)
p->lchild = s;// If the node is still empty , Make the child node equal to the node s, Otherwise, continue to find the node where the child is empty
}
else {// If the inserted value is greater than the node value , Let the node be equal to its right child node
q = q->rchild;
if (q == NULL)
p->rchild = s;// If the node is still empty , Make the child node equal to the node s, Otherwise, continue to find the node where the child is empty
}
}
q = s;
return 1;

}
void  CreateBST(BSTree &T)
{
KeyType key;
T = NULL;
scanf_s("%d", &key);
while (key!=0)
{
InsertBST2(T, key);
//InsertBST1(T, key);
scanf_s("%d", &key);
}
}
void  InOrder(BSTree T)
{
if (T != NULL)
{

InOrder(T->lchild);
printf("%d  ", T->key);// This is preceded by preorder traversal , Postposition is postorder traversal
InOrder(T->rchild);
}
}
int main()
{
BSTree T;
printf(" Building a binary sort tree , Please enter sequence :\n");
CreateBST(T);
printf(" The output sequence of the middle order traversal is :");
InOrder(T);
}
//34
//25
//56
//79
//12
//38
// The output sequence of preorder traversal is :34  25  12  56  38  79
// The output sequence of the middle order traversal is :12  25  34  38  56  79
// The output sequence of post order traversal is :12  25  38  79  56  34
``````

The result is 