儿童学习数据结构（15）: 二元排序树

该指针的指针将在二进制排序树中使用. 在学习二进制排序树之前，请先了解

儿童学习C语言（41）: 两级指针和多级指针

代码:

#include<iostream>
using namespace std;
typedef struct BiTNode
{
    int data;
    struct BiTNode *lchild, *rchild;
}BiTnode, *Bitree;
typedef bool status;
status biSearch(Bitree t, int key, Bitree f, Bitree *p)
{
    if (!t)
    {
        *p = f;
        return false;
    }
    else if (key == t->data)
    {
        *p = t;
        return true;
    }
    else if(key < t->data)
    {
        return biSearch(t->lchild, key, t, p);
    }
    else
    {
        return biSearch(t->rchild, key, t, p);
    }
}
status biInsert(Bitree *root, int key)
{
    Bitree p, s;
    if (!biSearch(*root, key, NULL, &p))
    {
        s = (Bitree)malloc(sizeof(BiTnode));
        s->data = key;
        s->lchild = s->rchild = NULL;
        if (!p)
        {
            *root = s;
        }
        else if (key < p->data)
        {
            p->lchild   = s;
        }
        else
        {
            p->rchild = s;
        }
        return true;
    }
    else
    {
        return false;
    }
}
status Delete(Bitree *p)
{
    Bitree q, s;
    if ((*p)->lchild == NULL)
    {
        q = *p;
        *p = (*p)-> lchild;
        free(q);
    }
    else if ((*p)->rchild == NULL)
    {
        q = *p;
        *p = (*p)-> rchild;
        free(q);
    }
    else
    {
        q = *p;
        s = (*p)->lchild;
        while (s->rchild)
        {
            q = s;
            s = s->rchild;
        }
        (*p)->data = s->data;
        if (q != *p)
        {
            q->rchild = s->lchild;
        }
        else
        {
            q->lchild = s->lchild;
        }
        free(s);
    }
    return true;
}
status biDel(Bitree *t, int key)
{
    if (!*t)
    {
        return false;
    }
    else
    {
        if (key == (*t)->data)
        {
            return Delete(t);
        }
        else if (key < (*t)->data)
        {
            return biDel(&(*t)->lchild, key);
        }
        else
        {
            return biDel(&(*t)->rchild, key);
        }
    }
}
void inOrder(Bitree &root)
{
    if (NULL != root)
    {
        inOrder(root->lchild);
        printf("%d ", root->data);  //访问结点
        inOrder(root->rchild);
    }
}
int main()
{
    int a[] = {62, 88, 58, 47, 35, 73, 51, 99, 37, 93, 29, 49, 56, 36, 48, 50};
    int len = sizeof(a) / sizeof(int);
    Bitree t = NULL;
    for (int i = 0; i < len; i++)
    {
        biInsert(&t, a[i]);
    }
    inOrder(t);
    cout << endl;
    Bitree p = NULL;
    cout << biSearch(t, 99, NULL, &p) << endl;
    cout << biDel(&t, 47) << endl;
    inOrder(t);
    cout << endl;
    return 0;
}

运行结果:

29 35 36 37 47 48 49 50 51 56 58 62 73 88 93 99
1
1
29 35 36 37 48 49 50 51 56 58 62 73 88 93 99

请添加QQ307591841（微信和QQ数量相同）或QQ组581357582二叉排序树代码二叉排序树代码，以学习编程.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-180218-1.html