數(shù)據(jù)結(jié)構(gòu)（十三）、C++二叉排序樹（BSTc風格）-創(chuàng)新互聯(lián)

（十三）、C++二叉排序樹（BST c風格）
#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)
{//如果樹空或等于根節(jié)點值，循環(huán)結(jié)束
    while (T != nullptr && key != T->data)
    {if (key< T->data)   //小于，則在右子樹上查找
        {T = T->lchild;
        }
        else                 //大于，則在右子樹上查找
        {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)   //在左子樹中找
    {return BSTSeah(T->lchild, key);
    }
    else                      //在右子樹中找
    {return BSTSeah(T->rchild, key);
    }
}

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

//前驅(qū)節(jié)點
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為空樹
    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)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

創(chuàng)新互聯(lián)公司專注于企業(yè)全網(wǎng)營銷推廣、網(wǎng)站重做改版、和田縣網(wǎng)站定制設(shè)計、自適應品牌網(wǎng)站建設(shè)、H5建站、成都做商城網(wǎng)站、集團公司官網(wǎng)建設(shè)、成都外貿(mào)網(wǎng)站建設(shè)公司、高端網(wǎng)站制作、響應式網(wǎng)頁設(shè)計等建站業(yè)務，價格優(yōu)惠性價比高，為和田縣等各大城市提供網(wǎng)站開發(fā)制作服務。

網(wǎng)站名稱：數(shù)據(jù)結(jié)構(gòu)（十三）、C++二叉排序樹（BSTc風格）-創(chuàng)新互聯(lián)
URL標題：http://muchs.cn/article44/dodcee.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站營銷、App開發(fā)、網(wǎng)站策劃、網(wǎng)站制作、網(wǎng)站導航、App設(shè)計

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

成都網(wǎng)站建設(shè)公司