（十三）、C++二叉排序樹(shù)（BST c風(fēng)格）

#includeusing namespace std;

//BST
using Tree = struct Tree
{int data;
    Tree* lchild, * rchild;
    Tree() :data(), lchild(nullptr), rchild(nullptr) {}
    Tree(int da) :data(da), lchild(nullptr), rchild(nullptr) {}
};

//查找
Tree* BST_Seach(Tree* T, int key)
{//如果樹(shù)空或等于根節(jié)點(diǎn)值，循環(huán)結(jié)束
    while (T != nullptr && key != T->data)
    {if (key< T->data)   //小于，則在右子樹(shù)上查找
        {T = T->lchild;
        }
        else                 //大于，則在右子樹(shù)上查找
        {T = T->rchild;
        }
    }
    return T;
}

//查找
Tree* BSTSeah(Tree* T, int key)
{if (T == nullptr)         //查找失敗
    {return nullptr;
    }
    if (key == T->data)       //查找成功
    {return T;
    }
    else if (key< T->data)   //在左子樹(shù)中找
    {return BSTSeah(T->lchild, key);
    }
    else                      //在右子樹(shù)中找
    {return BSTSeah(T->rchild, key);
    }
}

//插入  （遞歸）
//如果原二叉排序樹(shù)為空，則直接插入節(jié)點(diǎn)；否則，如果關(guān)鍵字k小于根節(jié)點(diǎn)
//值，則插入到左子樹(shù)，如果關(guān)鍵字k大于根節(jié)點(diǎn)值，則插入到右子樹(shù)
int BST_Insert(Tree*& T, int k)
{if (T == nullptr)       //原樹(shù)為空，新插入節(jié)點(diǎn)為根節(jié)點(diǎn)
    {T = new Tree(k);
        return 1;
    }
    else if (k == T->data)  //樹(shù)種存在相同關(guān)鍵字節(jié)點(diǎn)，插入失敗
    {return 0;
    }
    else if (k< T->data)   //插入到T的左子樹(shù)
    {return BST_Insert(T->lchild, k);
    }
    else                    //插入到T的有子樹(shù)
    {return BST_Insert(T->rchild, k);
    }
}

//插入  （非遞歸）
int BST_InsertLive(Tree*& T, int k)
{while (T != nullptr && T->data != k)
    {if (T == nullptr)
        {T = new Tree(k);
            return 1;
        }
        if (k == T->data)
        {return 0;
        }
        else if (k< T->data)
        {T = T->lchild;
        }
        else
        {T = T->rchild;
        }
    }
    return 0;
}

//后繼節(jié)點(diǎn)
int successor(Tree* p)
{p = p->rchild;
    while (p->lchild != nullptr)
    {p = p->lchild;
    }
    return p->data;
}

//前驅(qū)節(jié)點(diǎn)
int predecessor(Tree* p)
{p = p->lchild;
    while (p->rchild != nullptr)
    {p = p->rchild;
    }
    return p->data;
}

Tree* BST_Delete(Tree*& T, int key)
{if (T == nullptr)
    {return nullptr;
    }
    else
    {if (key< T->data)
        {T->lchild = BST_Delete(T->lchild, key);
        }
        else if (key >T->data)
        {T->rchild = BST_Delete(T->rchild, key);
        }
        else
        {if (T->lchild == nullptr && T->rchild == nullptr)
            {T = nullptr;
            }
            else if (T->rchild != nullptr)
            {T->data = successor(T);
                T->rchild = BST_Delete(T->rchild, T->data);
            }
            else
            {T->data = predecessor(T);
                T->lchild = BST_Delete(T->lchild, T->data);
            }
        }
    }
    return T;
}

//構(gòu)造
//int str[] = {50,60,23,14,28,39};
void Create_BST(Tree*& T, int str[], int n)
{T = nullptr;   //初始化T為空樹(shù)
    int i = 0;
    while (i< n)
    {BST_Insert(T, str[i]);
        i++;
    }
}

//遍歷
void Printf(Tree* T)
{if (T != nullptr)
    {Printf(T->lchild);
        cout<< T->data<< " ";
        Printf(T->rchild);
    }
}

int main()
{int str[5] = {50,66,60,26,21 };
    Tree* T = new Tree;
    Create_BST(T, str, 5);
    Printf(T);
    return 0;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

創(chuàng)新互聯(lián)公司專注于企業(yè)全網(wǎng)營(yíng)銷(xiāo)推廣、網(wǎng)站重做改版、和田縣網(wǎng)站定制設(shè)計(jì)、自適應(yīng)品牌網(wǎng)站建設(shè)、H5建站、成都做商城網(wǎng)站、集團(tuán)公司官網(wǎng)建設(shè)、成都外貿(mào)網(wǎng)站建設(shè)公司、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁(yè)設(shè)計(jì)等建站業(yè)務(wù)，價(jià)格優(yōu)惠性價(jià)比高，為和田縣等各大城市提供網(wǎng)站開(kāi)發(fā)制作服務(wù)。
當(dāng)前文章：數(shù)據(jù)結(jié)構(gòu)（十三）、C++二叉排序樹(shù)（BSTc風(fēng)格）-創(chuàng)新互聯(lián)
文章轉(zhuǎn)載：http://weahome.cn/article/dodcee.html