当前位置:网站首页>Implementation of non recursive and recursive insert operation and traversal code of binary sort tree in C

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

2020-11-10 14:49:21 Fried mushroom fish

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
 Insert picture description here

版权声明
本文为[Fried mushroom fish]所创,转载请带上原文链接,感谢