树、二叉树、二叉搜索树及其操作

时间：2022-01-28 17:30:47

树

树是什么？
●树：由N(N>=0)个结点构成的集合。对N>1的树，有：有一个特殊的结点，称为根结点，根节点没有前驱结点除根节点外，其余结点被分成M(M>0)个互不相交的集T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。
●如下图即是一棵普通的树：
树、二叉树、二叉搜索树及其操作
●注意：树的子树之间不可以连接，如果连接，那就不可以称之为树。
画图举例：
树、二叉树、二叉搜索树及其操作树、二叉树、二叉搜索树及其操作
下面介绍一下树结构中的一些基本术语：
●节点：包含一个数据结构及若干指向其子树的分支。
●结点的度：结点所拥有子树的个数称为该节点的度。
●叶结点：度为0的节点成为叶结点，叶结点也称为终端结点。
●分支结点：度不为0的结点称为分支结点，分支结点也称为非终端结点。一颗树中除叶结点外的所有结点都是分支结点。
●祖先节点：从根结点到该结点所经分支上的所有结点。
●子孙结点：以某结点为根结点的子树中的所有结点。
●双亲结点：树中某结点有孩子结点，则这个结点称为它孩子结点的双亲结点，双亲结点也称为前驱结点。
●孩子结点：树中一个结点的子树的根结点称为该结点的孩子结点，孩子结点也称为后继结点。
●兄弟结点：具有相同双亲结点的结点称为兄弟结点。
●树的度：树中所有结点的度的最大值称为该树的度。
●结点的层次：从根结点到树中某结点所经路径上的分支数称为该结点的层次，根结点的层次为1，其他结点层次是其双亲结点层次加1。
●树的深度：树中所有结点的层次的最大值称为该树的深度。
●有序树：树中结点的各棵子树T0,T1…是有序的，即为有序树。其中T1叫做根的第一棵子树，T2叫根的第二棵子树。
●无序树：树中结点的各棵子树之间的次序不重要，可以相互交换位置。
●森林：树M棵树的集合（M>=0）。

二叉树

●一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树的二叉树组成。
二叉树的特点：
●每个结点最多有两棵子树，即二叉树不存在度大于2的结点
●二叉树的子树有左右之分，其子树的次序不能颠倒
满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子节点都在同一层上
完全二叉树：如果一棵有N个结点的二叉树，它的前N个结点的结构与满二叉树前N个结点的结构相同，就把它称为完全二叉树

二叉搜索树

●二叉搜索树又称为二叉排序树，它或许是一颗空树，或者是具有以下性质的二叉树
若它的左子树不为空，则它的左子树的结点数值都小于根结点数值
若它的右字数不为空，则它的右子树的结点数值都大于根结点数值
它的左右子树又分别为二叉搜索树
●假设将一组数据建立成二叉搜索树：int array[] = {5,3,4,1,7,8,2,6,0,9};
最优情况：所建立的二叉搜索树为完全二叉树
最差情况：所建立的树退化为单支树

二叉搜索树的操作

二叉搜索树的结构

#define _CRT_SECURE_NO_WARNINGS 1
typedef int BSTDataType;
typedef struct BSTreeNode
{
    struct BSTreeNode* _pLeft;
    struct BSTreeNode* _pRight;
    BSTDataType _data;
}BSTNode;//定义二叉搜索树的结构

首先应该初始化

void InitBSTree(BSTNode** pRoot)
{
    assert(pRoot);//检测二叉搜索树是否存在
    *pRoot = NULL;//若存在先让二叉搜索树指向NULL
}

插入数据

BSTNode* BuyBSTNode(BSTDataType data)
{
    BSTNode* pNewNode = NULL;
    //为新节点申请空间
    pNewNode = (BSTNode*)malloc(sizeof(BSTNode));
    if (NULL == pNewNode)
    {
        assert(0);
        return NULL;
    }

    //给新节点赋值
    pNewNode->_data = data;
    pNewNode->_pLeft = NULL;
    pNewNode->_pRight = NULL;

    return pNewNode;
}
//插入值为data的元素
void InsertBSTree(BSTNode** pRoot, BSTDataType data)
{
    BSTNode* pCur = NULL;
    BSTNode* pParent = NULL;
    assert(pRoot);
    //当二叉搜索树为空时
    if (NULL == *pRoot)
    {
        *pRoot = BuyBSTNode(data);
        return;
    }
    //当二叉搜索树不空时
    //查找带插入节点的位置
    pCur = *pRoot;
    pParent = pCur;
    while (pCur)
    {
        pParent = pCur;
        if (data < pCur->_data)
        {
            pCur = pCur->_pLeft;
        }
        else if (data>pCur->_data)
        {
            pCur = pCur->_pRight;
        }
        else
            return;
    }

    //插入新节点
    if (data < pParent->_data)
    {
        pParent->_pLeft = BuyBSTNode(data);
    }
    else
    {
        pParent->_pRight = BuyBSTNode(data);
    }
}

//递归实现搜索二叉树插入
int InsertBSTreeR(BSTNode** pRoot, BSTDataType data)
{
    assert(pRoot);
    if (NULL == *pRoot)
    {
        *pRoot = BuyBSTNode(data);
        return 1;
    }
    else if (data < (*pRoot)->_data)
        InsertBSTreeR(&(*pRoot)->_pLeft, data);
    else if (data > (*pRoot)->_data)
        InsertBSTreeR(&(*pRoot)->_pRight, data);
    return 0;
}

其他操作
在二叉搜索树中查找值为data的节点

BSTNode* FindBSTree(BSTNode** pRoot, BSTDataType data)
{
    BSTNode* pFind = NULL;//用pFind来标记找到的结点
    assert(pRoot);
    pFind = *pRoot;//让pFind从根结点的位置开始查找
    while (pFind)
    {
        if (data == pFind->_data)
            return pFind;
        else if (data < pFind->_data)
        {
            pFind = pFind->_pLeft;
        }
        else
        {
            pFind = pFind->_pRight;
        }
    }
    return NULL;
}

//递归实现搜索二叉树查找
BSTNode* FindBSTreeR(BSTNode** pRoot, BSTDataType data)
{
    assert(pRoot);
    if (NULL == *pRoot)
        return NULL;
    if (data == (*pRoot)->_data)
        return *pRoot;
    else if (data < (*pRoot)->_data)
        return FindBSTreeR(&(*pRoot)->_pLeft, data);
    else if (data > (*pRoot)->_data)
        return FindBSTreeR(&(*pRoot)->_pRight, data);
    return NULL;
}

删除二叉搜索树中值为data的结点

void Swap(BSTDataType* Left, BSTDataType* Right)
{
    BSTDataType tmp = *Left;
    *Left = *Right;
    *Right = tmp;
}
void DeleteBSTree(BSTNode** pRoot, BSTDataType data)
{
    BSTNode* pCur = NULL;
    BSTNode* pParent = NULL;
    BSTNode* MaxInLeft = NULL;
    BSTNode* pDel = NULL;
    assert(pRoot);

    pCur = *pRoot;

    //寻找要删除的节点
    while (pCur &&  data != pCur->_data)
    {
        if (data < pCur->_data)
            pCur = pCur->_pLeft;
        else
            pCur = pCur->_pRight;
    }
    //如果要删除的数字不在二叉树中就退出
    if (NULL == pCur)
        return;

    //用pDel标记要删除的节点
    pDel = pCur;
        //a.要删除的结点无孩子结点 
        //b.要删除的结点只有左孩子结点 
    if ((pDel->_pLeft && NULL == pDel->_pRight)||(NULL == pDel->_pLeft&&NULL ==pDel->_pRight))
    {
        //让要删除节点的双亲节点指向要删除节点的左孩子
        pCur = *pRoot;
        pParent = *pRoot;

        //找要删除节点的双亲节点
        while (pCur != pDel)
        {
            pParent = pCur;
            if (data < pCur->_data)
            {
                pCur = pCur->_pLeft;
            }
            else
            {
                pCur = pCur->_pRight;
            }
        }

        if (pParent == pDel)//要删除的节点是根节点
        {
            pRoot = &(*pRoot)->_pLeft;
            free(pDel);
            pDel = NULL;
            return;
        }

        //判断要删除的节点是双亲结点的左孩子还是右孩子
        if (pParent->_pLeft == pDel)
        {
            //要删除的节点不是根节点
            pParent->_pLeft = pDel->_pLeft;
            free(pDel);
            pDel = NULL;
            return;
        }
        else
        {
            pParent->_pRight = pDel->_pLeft;
            free(pDel);
            pDel = NULL;
            return;
        }
    }
        //c.要删除的结点只有右孩子结点 
    else if (pDel->_pRight && NULL == pDel->_pLeft)
    {
        pCur = *pRoot;
        pParent = pCur;

        //找要删除节点的双亲结点
        while (pCur != pDel)
        {
            pParent = pCur;
            if (data < pCur->_data)
            {
                pCur = pCur->_pLeft;
            }
            else
            {
                pCur = pCur->_pRight;
            }
        }

        if (pParent == pDel)//要删除的节点是根节点
        {
            pRoot = &(*pRoot)->_pRight;
            free(pDel);
            pDel = NULL;
            return;
        }

        //要删除的节点不是根节点

        //判断要删除的节点是双亲节点的左孩子还是右孩子
        if (pParent->_pRight == pDel)
        {
            pParent->_pRight = pDel->_pRight;
            free(pDel);
            pDel = NULL;
            return;
        }
        else
        {
            pParent->_pLeft = pDel->_pRight;
            free(pDel);
            pDel = NULL;
            return;
        }
    }
        //d.要删除的结点有左、右孩子结点 
    if (pDel->_pLeft&&pDel->_pRight)
    {
        pCur = *pRoot;
        pParent = pCur;

        //找要删除节点的双亲结点
        while (pCur != pDel)
        {
            pParent = pCur;
            if (data < pCur->_data)
            {
                pCur = pCur->_pLeft;
            }
            else
            {
                pCur = pCur->_pRight;
            }
        }

        if (pParent == pDel)//要删除节点是根节点
        {
            //找到根节点左子树中最右边的节点与他的双亲节点
            pCur = (*pRoot)->_pLeft;
            pParent = *pRoot;
            while (pCur->_pRight)
            {
                pParent = pCur;
                pCur = pCur->_pRight;
            }
            //交换节点的数值
            Swap(&pCur->_data, &pDel->_data);
            //根节点的左子树就是最大的节点
            if (pParent == *pRoot)
            {
                pParent->_pLeft = pCur->_pLeft;
                free(pCur);
                pCur = NULL;
                return;
            }
            pParent->_pRight = pCur->_pRight;
            return;
        }

        //要删除的节点不是根节点
        //将要要删除的节点作为根节点
        DeleteBSTree(&pDel, data);
    }
}

//递归实现
int DeleteBSTreeR(BSTNode** pRoot, BSTDataType data)
{
    BSTNode* pCur = NULL;
    BSTNode* pParent = NULL;
    assert(pRoot);
    if (NULL == *pRoot)
        return 0;
    if (data < (*pRoot)->_data)
        return DeleteBSTreeR(&(*pRoot)->_pLeft, data);
    else if (data>(*pRoot)->_data)
        return DeleteBSTreeR(&(*pRoot)->_pRight, data);
    else
    {
        BSTNode* pDel = (*pRoot);

        //如果要删除的节点只有右子树或没有子树
        if (NULL == pDel->_pLeft)
        {
            *pRoot = pDel->_pRight;
            free(pDel);
        }
        //要删除的节点只有右子树
        else if (NULL == pDel->_pRight)
        {
            *pRoot = pDel->_pLeft;
            free(pDel);
        }
        //要删除的节点既有左子树也有右子树
        else
        {
            //在左子树中找最右边的子树
            BSTNode* pSwap = pDel->_pLeft;
            BSTNode* pParent = pSwap;
            while (pSwap && pSwap->_pRight)
            {
                pParent = pSwap;
                pSwap = pSwap->_pRight;
            }

            //交换找到的节点与要删除节点的数值
            Swap(&pDel->_data, &pSwap->_data);

            //找到的节点是根节点的左子树，pSwap和pparent指向同一个节点，删除交换的节点pSwap
            if (pParent == pSwap)
            {
                *pRoot = pSwap->_pLeft;
                free(pSwap);
                pSwap = NULL;
            }
            //pSwap是pParent的右孩子
            else
            {
                pParent->_pRight = pSwap->_pRight;
                free(pSwap);
                pSwap = NULL;
            }
        }
    }
    return 1;
}

销毁二叉搜索树

void DestroyBSTree(BSTNode** pRoot)
{
    assert(*pRoot);
    DestroyBSTree(&(*pRoot)->_pLeft); DestroyBSTree(&(*pRoot)->_pRight); free(*pRoot); *pRoot = NULL; }

二叉搜索树的性能分析

二叉搜索树的插入与删除都必须先进行查找，则查找的效率就代表了二叉搜索树的各个操作的性能
●最优情况下，即二叉搜索树为完全二叉树，其平均比较次数为：log₂N
●最差情况下，即二叉搜索树退化为单支树，其平均比较次数为：N/2

如何使二叉搜索树的性能提升

1.平衡树（AVL树）
●一颗AVL树或者为空树，或者是具有以下性质的二叉搜索树：
它的左右子树都是AVL树
左右子树高度之差（简称平衡因子）的绝对值不超过1
如果一颗二叉搜索树的高度平衡，它就是一颗AVL树。如果它有N个结点，其高度可保持在O（lg n）,平均搜索时间复杂度为O(lg(n))
2.红黑树
●红黑树也是一棵二叉搜索树，它的每个结点上增加了一个存储位来表示该结点的颜色，通常使用红/黑两种颜色，通过对任何一条从根结点到叶子结点简单路径上的颜色来约束，红黑树保证最长路径不超过最短路径的两倍，因而近似平衡
●红黑树的性质
每个结点不是红色就是黑色
根结点是黑色的
如果一个节点是红色的，则它的两个孩子结点是黑色的
对于每个结点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点
每个叶子结点都是黑色的（此处叶子节点指空结点）

标签：

相关文章