二叉排序树的插入（递归、非递归）和构造

目录

插入

递归

非递归

构造

插入

递归

//17、二叉排序树（BST）的插入（其实就是个查找失败点的过程）
typedef struct BiTreeNode{
    int data;
    BiTreeNode *lchild,*rchild;
}BiTreeNode,*BiTree;
//①递归算法
int BSTInsert(BiTree &T,int key){
    //查找到失败点
    if(T == NULL){//这个T其实是上一轮传过来的T1 -> lchild或者T1 -> rchild的本身,
        //现在就是T1 -> lchild 或者 T1 -> rchild 为空，在空的这个地方malloc，
        //实际上是没有断链的，是接上了的
        T = (BiTree)malloc(sizeof(BiTreeNode));//相当于把申请的空间赋给了上一轮的T1 -> lchild或者T1 -> rchild
        T -> data = key;
        T -> lchild = T -> rchild = NULL;
        return 1;
    }
    else if(key == T -> data)//查找失败
        return 0;
    else if(key < T -> data)
        return BSTInsert(T -> lchild,key);
    else
        return BSTInsert(T -> rchild,key);
}

非递归

//②非递归算法
int BSTInsert(BiTree &T,int key){
    //注意非递归和递归的区别：
    //Q1：为什么非递归要用preT标记前驱？因为递归中是一轮接着一轮连着的，是知道要去插到哪里的。
    //Q2：为什么递归中不知道是要插到左边还是右边呢？因为我们只知道某个条件导致while循环结束了，
    //    但并不知道到底是T的lchild是空的，还是rchild是空的。而递归中是直接传递的参数，所以是知道的。
    //Q3：如果整个T就是个空的呢？while根本就不会执行，所以要加个判空。
    if(T == NULL){
        T = (BiTree)malloc(sizeof(BiTreeNode));
        T -> data = key;
        T -> lchild = T -> rchild = NULL;
        return 1;//成功
    }
    BiTree preT;//知道前驱，才能知道插在谁的左孩子或者右孩子之中（因为不知道是从T -> lchild来的，还是从T -> rchild来的）
    int tag;//用tag标记就可以知道应该是插在preT的左，还是插在preT的右，0代表插在左，1代表插在右
    while(T != NULL ){
        if(key < T -> data){
            preT = T;//标记前驱
            tag = 0;
            T = T -> lchild;
        }else if(key > T -> data){
            preT = T;//标记前驱
            tag = 1;
            T = T -> rchild;
        }
        else
            return 0;//失败
    }
    BiTree k = (BiTree)malloc(sizeof(BiTreeNode));
    k -> data = key;
    k -> lchild = k -> rchild = NULL;
    if(tag == 0)
        preT -> lchild = k;
    else
        preT -> rchild = k;
    return 1;//成功
}

构造

//18、二叉排序树的构造（其实就是往一个刚开始为空的T中不断插入新节点的过程）
typedef struct BiTreeNode{
    int data;
    BiTreeNode *lchild,*rchild;
}BiTreeNode,*BiTree;
void BSTCreat(BiTree &T,int str[],int n){
    T = NULL;//刚开始是个空树
    int i = 0;
    while(i < n){
        BSTInsert(T,str[i]);//在17里面
        i++;
    }
}