【无标题】

• 二叉搜索树

使用C语言实现了二叉搜索树，直接贴代码

#include 
#include 
#include 

#define arrsort arrisort
#define NULL ((void *)0)
//定义树节点
struct TreeNode {
    struct TreeNode* pnode;//父节点
    struct TreeNode* lnode;//左孩子节点
    struct TreeNode* rnode;//右孩子节点
    int val;//节点值
};
typedef struct TreeNode Tree;
//树节点占用存储
const int TREE_NODE_SIZE=sizeof(struct TreeNode);
const int INT_SIZE = sizeof(int);
const null = 0;

//声明函数调用
void arrprintf(const int[], int);//数组打印
void arrsort(int arr[], int l, int r);//数组排序
Tree* treeBuild(int val[], int l, int r);//二叉树建立
void treeFree(struct TreeNode* proot);//二叉树资源释放
void treeWalkPre(struct TreeNode* proot,int rflag);//先序遍历
void treeWalkPos(struct TreeNode* proot, int rflag);//后续遍历
void treeWalkIno(struct TreeNode* proot, int rflag);//中序遍历
struct TreeNode* treeSearch(struct TreeNode* p, int key);//二叉树搜索
struct TreeNode* treeMax(struct TreeNode* p);//最大直
struct TreeNode* treeMin(struct TreeNode* p);//最小值
struct TreeNode* treePreNode(struct TreeNode* pnode);//前置节点
struct TreeNode* treeNextNode(struct TreeNode* pnode);//后置节点
void treeInsert(struct TreeNode* proot, struct TreeNode* pnew);//节点新增
struct TreeNode* nodeBuild();//创立node
Tree* treeDelete(struct TreeNode* proot, struct TreeNode* pdelete);

int main(){
    const int arr[] = { 52,23,43,75,0,37,58,76,79,19,31,14,47,92,74,80,32,62,81,51,68,69,26,27,1,16,25,84,78,28,66,59,100,44,15,50,90,73,87,21,39,97,61,63,40,82,30,10,34,12,95,45,56,71,48,91,33,53,46,29,24,4,67,8,99,85,41,55,88,5,2,42,98,11,7,94,60,9,86,38,13,35,3,20,83,70,57,72,54,89,49,64,77,96,22,65,17,18,93,6 };
    //const int arr[] = { 46,59,16,77,36,49,54,38,6,44,21,63,4,62,99,76};
    const arrlen = sizeof(arr) / sizeof(int);//获取数组大小
    int* parr =NULL;
    struct TreeNode* proot;
    struct TreeNode* ptmp;
    struct TreeNode* ptmp2;
    parr = (int*)malloc(INT_SIZE* arrlen);
    int i;
    if (parr == NULL) {
        return 1;
    }
    memcpy(parr, arr, INT_SIZE * arrlen);
    arrsort(parr,0, arrlen -1);
    arrprintf(arr, arrlen);
    arrprintf(parr, arrlen);
    proot= treeBuild(parr,0,arrlen-1);
    //二叉树遍历
    treeWalkIno(proot,1);
    treeWalkPre(proot,1);
    treeWalkPos(proot, 1);
    //二叉树搜索
    ptmp=treeSearch(proot, 100);
    if (!ptmp) {
        printf("treeSearch,100:ptmp == nulln");
    }
    else {
        printf("treeSearch,100:%dn",ptmp->val);
    }
    ptmp = treeSearch(proot, 77);
    if (!ptmp) {
        printf("treeSearch,77:ptmp == nulln");

    }
    else {
        printf("treeSearch,77:%dn", ptmp->val);
    }




    ptmp = treeSearch(proot, 68);
    if (!ptmp) {
        printf("treeSearch,68:ptmp == nulln");

    }
    else {
        printf("treeSearch,68:%dn", ptmp->val);
    }

    //最大值
    ptmp = treeMax(proot);
    if (!ptmp) {
        printf("treeMax:ptmp == nulln");
    }
    else {
        printf("treeMax:%dn", ptmp->val);
    }
    //最小值
    ptmp = treeMin(proot);
    if (!ptmp) {
        printf("treeMin:ptmp == nulln");
    }
    else {
        printf("treeMin:%dn", ptmp->val);
    }

    //前置节点
    ptmp = treePreNode(treeSearch(proot, 99));
    if (ptmp != NULL) {
        printf("treePreNode(treeSearch(proot, 99)):%dn", ptmp->val);
    }
    ptmp = treePreNode(treeSearch(proot, 2));
    if (ptmp != NULL) {
        printf("treePreNode(treeSearch(proot, 2)):%dn", ptmp->val);
    }
    ptmp = treePreNode(treeSearch(proot, 77));
    if (ptmp != NULL) {
        printf("treePreNode(treeSearch(proot, 77)):%dn", ptmp->val);
    }
    //后置节点
    ptmp = treeNextNode(treeSearch(proot, 99));
    if (ptmp != NULL) {
        printf("ttreeNextNode(treeSearch(proot, 99)):%dn", ptmp->val);
    }
    ptmp = treeNextNode(treeSearch(proot, 2));
    if (ptmp != NULL) {
        printf("ttreeNextNode(treeSearch(proot, 2)):%dn", ptmp->val);
    }
    ptmp = treeNextNode(treeSearch(proot, 77));
    if (ptmp != NULL) {
        printf("ttreeNextNode(treeSearch(proot, 77)):%dn", ptmp->val);
    }
    //插入节点
    ptmp2=nodeBuild();
    if (ptmp2) {
        ptmp2->val = 100;
        treeInsert(proot, ptmp2);
    }
    //插入节点
    ptmp2 = nodeBuild();
    if (ptmp2) {
        ptmp2->val = 1;
        treeInsert(proot, ptmp2);
    }
    //中序遍历打印详情
    treeWalkIno(proot, 1);
    //
    ptmp = treeSearch(proot,100);
    proot=treeDelete(proot, ptmp);
    printf("treeDelete(proot，100)：n");
    treeWalkIno(proot, 1);
    printf("n");
    ///

        //
    ptmp = treeSearch(proot, 1);
    proot = treeDelete(proot, ptmp);
    printf("treeDelete(proot，1)：n");
    treeWalkIno(proot, 1);
    printf("n");
    ///
    for (i = 0; i < arrlen; i++) {
        ptmp = treeSearch(proot, arr[i]);
        proot = treeDelete(proot, ptmp);
        printf("treeDelete(proot，%d)：n",arr[i]);
        treeWalkIno(proot, 1);
        printf("n");
    }
    //资源释放
    treeFree(proot);
    free(parr);
    return 0;
}
void arrswap(int* arr,int i,int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
//快速排序
void arrqsort(int arr[], int l, int r) {
    int key = arr[l];
    int li = l;
    int ri = r;
    if (l >= r) {
        return;
    }
    while (1) {
        //arrprintf(arr, 10);
        while (arr[ri] > key) {
            ri--;
        }
        while (arr[li] <= key && li < ri) {
            li++;
        }
        if (li == ri) {
            break;
        }
        arrswap(arr, li, ri);
    }
    arrswap(arr, l, li);
    arrsort(arr, l, li - 1);
    arrsort(arr, li + 1,r);
}
//插入排序
void arrisort(int arr[], int l, int r) {
    int i = 0, j = 0;
    int tmp = 0;
    for (i = l+1; i <= r; i++) {
        //arrprintf(arr, 10);
        tmp = arr[i];
        for (j = i - 1 ; j >= 0; j--) {
            if (arr[j]>tmp) {
                arr[j+1] = arr[j];
            }else {
                break;
            }
        }
        arr[j + 1] = tmp;

    }
}
void arrprintf(const int valarr[],int vallen) {

    int i;
    printf("arr:");
    for (i = 0; i < vallen; i++) {
        printf("%d ",valarr[i]);
    }
    printf("n");
}
struct TreeNode* nodeBuild() {
    struct TreeNode* p = (struct TreeNode*)malloc(TREE_NODE_SIZE);
    if (p != NULL) {
        memset(p, 0, TREE_NODE_SIZE);
    }
    return p;
}
Tree* treeBuild(int val[],int l,int r) {
    int mid = (l + r) / 2;

    struct TreeNode* proot = NULL;
    if (l > r) {
        return NULL;
    }

    proot = nodeBuild();

    proot->lnode = treeBuild(val,l,mid-1);

    if (proot->lnode != NULL) {
        proot->lnode->pnode = proot;
    }
    proot->rnode = treeBuild(val, mid + 1, r);
    if (proot->rnode != NULL) {
        proot->rnode->pnode = proot;
    }
    proot->val = val[mid];
    return proot;
}
void treeFree(struct TreeNode* proot) {
    if (proot != NULL) {
        treeFree(proot->lnode);
        treeFree(proot->rnode);
        free(proot);
    }
}
//中序遍历
//打印出來的内容加上 包裹可以查看层次结构
void treeWalkIno(struct TreeNode* proot,int rflag) {
    if (proot != NULL) {
        if (!!rflag) {
            printf("");
        }
        if (proot->lnode != NULL) {
            printf("");
            treeWalkIno(proot->lnode,0);
            printf("");
        }
        printf("%d", proot->val);
        if (proot->rnode != NULL) {
            //printf("x");
            printf("");
            treeWalkIno(proot->rnode,0);
            printf("");
        }
        if (!!rflag) {
            printf("");
        }

    }
}
//先序遍历
//打印出來的内容加上 包裹可以查看层次结构
void treeWalkPre(struct TreeNode* proot,int rflag) {
  if (proot != NULL) {
        if (!!rflag) {
            printf("");
        }
        printf("%d", proot->val);
        if (proot->lnode!=NULL) {
            printf("");
            treeWalkPre(proot->lnode,0);
            printf("");
        }
        if (proot->rnode != NULL) {
            //printf("x");
            printf("");
            treeWalkPre(proot->rnode,0);
            printf("");
        }
        if (!!rflag) {
            printf("");
        }

    }
}
//后续遍历
//打印出來的内容加上 包裹可以查看层次结构
void treeWalkPos(struct TreeNode* proot,int rflag) {
    if (proot != NULL) {
        if (!!rflag) {
            printf("");
        }
        if (proot->lnode != NULL) {
            printf("");
            treeWalkPos(proot->lnode,0);
            printf("");
        }
        if (proot->rnode != NULL) {
            //printf("x");
            printf("");
            treeWalkPos(proot->rnode,0);
            printf("");
        }
        printf("%d", proot->val);
        if (!!rflag) {
            printf("");
        }
    }
}
struct TreeNode* treeSearch(struct TreeNode* p,int key) {
    if (p == NULL) {
        return NULL;
    }
    if (p->val == key) {
        return p;
    }
    else if (p->val > key) {
        return treeSearch(p->lnode,key);
    }
    else {
        return treeSearch(p->rnode, key);
    }

}
struct TreeNode* treeMax(struct TreeNode* proot) {
    struct TreeNode* ptmp= proot;
    if (proot == NULL) {
        return NULL;
    }
    while (ptmp->rnode != NULL) {
        ptmp = ptmp->rnode;
    }
    return ptmp;

}
struct TreeNode* treeMin(struct TreeNode* p) {
    struct TreeNode* ptmp = p;
    if (p == NULL) {
        return NULL;
    }
    while (ptmp->lnode != NULL) {
        ptmp = ptmp->lnode;
    }
    return ptmp;

}
//前置节点
struct TreeNode* treePreNode(struct TreeNode* pnode) {
    struct TreeNode* ptmemp;
    if (pnode == NULL) {
        return NULL;
    }
    if (pnode->lnode) {
        return treeMax(pnode->lnode);
    }
    ptmemp = pnode;
    while (1) {
        if (ptmemp->pnode == NULL) {
            return NULL;
        }
        if (ptmemp->pnode->lnode == ptmemp) {
            ptmemp = ptmemp->pnode;
        }else if (ptmemp->pnode->rnode == ptmemp) {
            return ptmemp->pnode;
        }
    }
}
//后置节点
struct TreeNode* treeNextNode(struct TreeNode* pnode) {
    struct TreeNode* ptmemp;
    if (pnode == NULL) {
        return NULL;
    }
    if (pnode->rnode) {
        return treeMin(pnode->rnode);
    }
    ptmemp = pnode;
    while (1) {
        if (ptmemp->pnode == NULL) {
            return NULL;
        }
        if (ptmemp->pnode->rnode == ptmemp) {
            ptmemp = ptmemp->pnode;
        }
        else if (ptmemp->pnode->lnode == ptmemp) {
            return ptmemp->pnode;
        }
    }
}
void treeInsert(struct TreeNode* proot, struct TreeNode* pnew) {
    struct TreeNode* ptmp0;
    if (proot==NULL) {
        return ;
    }
    ptmp0 = proot;
    while (ptmp0 !=NULL) {
        if (pnew->val > ptmp0->val) {
            if (ptmp0->rnode == NULL) {
                //插到这里来
                ptmp0->rnode = pnew;
                pnew->pnode = ptmp0;
                return;
            }
            else {
                ptmp0 = ptmp0->rnode;
            }
        }
        else {
            if (ptmp0->lnode == NULL) {
                //插到这里来
                ptmp0->lnode = pnew;
                pnew->pnode = ptmp0;
                return;
            }
            else {
                ptmp0 = ptmp0->lnode;
            }

        }
    }
}
//如果删除的是根节点，直接返回新的根节点
//如果删除的不是根节点，返回proot
Tree* treeDelete(struct TreeNode* proot, struct TreeNode* pdelete) {


    //Tree* ptree;//子树
    //struct TreeNode* pback;//备份
    struct TreeNode* pfind;//用于替换的节点信息
    //struct TreeNode* ptmp;
   // struct TreeNode* pnew;
    struct TreeNode* prootNew=proot;
    //标志这个节点是父节点的左节点还是右节点0-左节点，1-右节点
    //int pcflag = 0;

    if (!pdelete) {
        return proot;
    }
    //如果右左节点
    if (pdelete->lnode) {


        pfind =treeMax(pdelete->lnode);

        //最大值为欲删除节点的左节点
        if (pfind == pdelete->lnode) {

            pfind->pnode = pdelete->pnode;//建立子父联系
            pfind->rnode = pdelete->rnode;//建立右子树的关系【这种情况是没有右子树的（pfind == pdelete->lnode）】
            if (pfind->pnode) {

                if (pdelete->pnode->lnode == pdelete) {
                    pdelete->pnode->lnode = pfind;//建立父子联系

                }else {
                    pdelete->pnode->rnode = pfind;//建立父子联系

                }
            }
            if (pfind->rnode) {
                pfind->rnode->pnode = pfind;
            }
            free(pdelete);
            //如果原节点右父节点，则删除的不是根节点
            if (pfind->pnode) {
                return proot;
            }
            else {
                return pfind;
            }
        }
        else {
            //做值的交换，然后递归删除pfind
            pdelete->val = pfind->val;
            treeDelete(pdelete, pfind);
            return proot;
        }
    }
    else if (pdelete->rnode) {

        pfind = treeMin(pdelete->rnode);

        //最大值为欲删除节点的左节点
        if (pfind == pdelete->rnode) {

            pfind->pnode = pdelete->pnode;//建立子父联系
            pfind->lnode = pdelete->lnode;//建立右子树的关系【这种情况是没有右子树的（pfind == pdelete->rnode）】
            if (pfind->pnode) {

                if (pdelete->pnode->lnode == pdelete) {
                    pdelete->pnode->lnode = pfind;//建立父子联系

                }
                else {
                    pdelete->pnode->rnode = pfind;//建立父子联系

                }
            }
            free(pdelete);
            //如果原节点有父节点，则删除的不是根节点
            if (pfind->pnode) {
                return proot;
            }
            else {
                return pfind;
            }
        }
        else {
            //做值的交换，然后递归删除pfind
            pdelete->val = pfind->val;
            treeDelete(pdelete, pfind);
            return proot;
        }
    }
    else {
        if (pdelete->pnode) {
            if (pdelete->pnode->lnode==pdelete) {
                pdelete->pnode->lnode = NULL;
            }
            else {
                pdelete->pnode->rnode = NULL;
            }
            //欲删除的节点既没有左节点也没有右节点，直接返回
            free(pdelete);
            return proot;
        }
        else {
            free(pdelete);
            return NULL;
        }

    }

}