二进制排序树的介绍和实现

1. 算法介绍

二进制排序树，也称为二进制搜索树，也称为二进制搜索树. 该树属于一种输入数据，并且默认情况下会生成顺序数据结构. 这与本章上一节中描述的在某个数据段中的静态搜索不同. 当动态搜索是输入时，它就是输入. 对于排序后的数据结构，上一个STL中set集合的底部集合是类似的树结构红黑树.

2. 定义

二进制排序树具有以下属性:

a）如果左子树不为空，则左子树上所有节点的值都小于或等于其根节点的值;

b）如果右子树不为空，则右子树上所有节点的值都大于或等于其根节点的值;

c）左右子树也是二进制排序树；

也就是说，对于每个根节点二叉查找树 二叉排序树，左子节点始终小于根节点，右子节点始终大于根节点.

3. 查找

请考虑如果树为空，则搜索结束并且没有匹配项. 如果要搜索的值等于根节点的值，则搜索成功. 否则，继续在子树中搜索. 如果找到的值小于根节点的值，则选择左子树，如果值大于根节点，则选择右子树.

参考代码如下:

typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ 
 
/* 二叉树的二叉链表结点结构定义 */
typedef  struct BiTNode /* 结点结构 */
{
    int data;   /* 结点数据 */
    struct BiTNode *lchild, *rchild;    /* 左右孩子指针 */
} BiTNode, *BiTree;
 
/* 递归查找二叉排序树T中是否存在key, */
/* 指针f指向T的双亲，其初始调用值为NULL */
/* 若查找成功，则指针p指向该数据元素结点，并返回TRUE */
/* 否则指针p指向查找路径上访问的最后一个结点并返回FALSE */
Status SearchBST(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 SearchBST(t->lchild, key, t, p);  /*  在左子树中继续查找 */
    else  
        return SearchBST(t->rchild, key, t, p);  /*  在右子树中继续查找 */
}

4. 插入方法和实现

二进制排序的插入基于对二进制排序的搜索. 插入节点是通过搜索找到该节点的合适插入位置，然后直接放置该节点. 实际上二叉查找树 二叉排序树，第2.2节中逐步构建二进制排序树的过程是节点插入过程，并认为搜索的关键字已在树中，如果搜索的关键字不在树中，则指向数据节点. 树，它指向搜索路径上的最后一个节点.

参考代码

struct BiTree {
    int data;
    BiTree *lchild;
    BiTree *rchild;
};
 
//在二叉排序树中插入查找关键字key
BiTree* InsertBST(BiTree *t,int key)
{
    if (t == NULL)
    {
        t = new BiTree();
        t->lchild = t->rchild = NULL;
        t->data = key;
        return t;
    }
 
    if (key < t->data) 
        t->lchild = InsertBST(t->lchild, key);
    else
        t->rchild = InsertBST(t->rchild, key);
 
    return t;
}
 
//n个数据在数组d中，tree为二叉排序树根
BiTree* CreateBiTree(BiTree *tree, int d[], int n)
{
    for (int i = 0; i < n; i++)
        tree = InsertBST(tree, d[i]);
}

5. 删除方法与实现

删除二叉树不再像插入二叉树那样容易，因为删除节点后，它将影响树的其他部分的结构.

删除时需要考虑以下情况:

a）将该节点删除为叶节点；

b）删除的节点仅具有左子树；

c）删除的节点仅具有正确的子树

d）删除的节点同时具有左右子树.

参考代码如下:

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