当前位置:网站首页>C中二叉排序树的非递归和递归插入操作以及中序遍历代码实现【可运行】

C中二叉排序树的非递归和递归插入操作以及中序遍历代码实现【可运行】

2020-11-10 14:49:21 油炸蘑菇鱼

C中二叉排序树的非递归和递归插入操作以及中序遍历代码实现【可运行】

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

typedef int KeyType;

typedef struct  node
{
    KeyType  key;
    struct node* lchild, * rchild;
}BSTNode, * BSTree;
//二叉排序树递归插入操作
int InsertBST1(BSTree& T, int k) {
    if (T == NULL) {//原树为空,新插入的结点为根结点
        
        T = (BSTree)malloc(sizeof(BSTNode));
        if (T == NULL) {
            return 0;//内存分配失败的情况
        }
        T->key = k;
        T->lchild = T->rchild = NULL;
        return 1;//返回1, 插入成功
    }
    else if (k == T->key) {//树中存在相同关键字的结点,插入失败
        return 0; 
    }
    else if (k < T->key) {
        return InsertBST1(T->lchild, k); //如果插入的值小于结点的值,则递归插入函数进行查找
    }
    else {
        return InsertBST1(T->rchild, k); //如果插入的值大于结点的值,则递归插入函数进行查找
    }
}
//二叉排序树非递归插入操作
int  InsertBST2(BSTree& T, KeyType  k)
{
    BSTree   q, s;//新增两个结点q,s
    s = (BSTree)malloc(sizeof(BSTNode));//分配一个新节点
    if (s == NULL) {
        return 0;//内存分配失败的情况
    }
    s->key = k;//新结点存储的数据为插入的值
    s->lchild = NULL;
    s->rchild = NULL;
    if (T == NULL)//如果当前结点为空则将新分配的结点s赋给当前结点
    {
        T = s;
        return  1;
    }
    q = T;//
    while (q) {//
        BSTree p = q;
        if (k == q->key){//如果插入的值等于结点的值,则释放新分配出的内存
            free(s);
            return 0;
        }
        if (k < q->key){//如果插入的值小于结点的值,则令该结点等于其左孩子结点
            q = q->lchild;
            if (q == NULL)
                p->lchild = s;//如果该结点的还在结点等于空,则令其孩子结点等于结点s,否则继续找孩子为空的结点
        }
        else {//如果插入的值大于结点的值,则令该结点等于其右孩子结点
            q = q->rchild;
            if (q == NULL)
                p->rchild = s;//如果该结点的还在结点等于空,则令其孩子结点等于结点s,否则继续找孩子为空的结点
        }
    }
    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);//这个前置为先序遍历,后置为后序遍历
        InOrder(T->rchild);
    }
}
int main()
{
    BSTree T;
    printf("建立二叉排序树,请输入序列:\n");
    CreateBST(T);
    printf("中序遍历输出序列为:");
    InOrder(T);
}
//34
//25
//56
//79
//12
//38
//先序遍历输出序列为:34  25  12  56  38  79
//中序遍历输出序列为:12  25  34  38  56  79
//后序遍历输出序列为:12  25  38  79  56  34

结果为
在这里插入图片描述

版权声明
本文为[油炸蘑菇鱼]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/Sawye-sxy/p/13953734.html