（十三）、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)
{//如果樹空或等于根節點值，循環結束
    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);
    }
}

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

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

//前驅節點
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;
}

//構造
//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;
}

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

創新互聯公司專注于企業全網營銷推廣、網站重做改版、和田縣網站定制設計、自適應品牌網站建設、H5建站、成都做商城網站、集團公司官網建設、成都外貿網站建設公司、高端網站制作、響應式網頁設計等建站業務，價格優惠性價比高，為和田縣等各大城市提供網站開發制作服務。

網站名稱：數據結構（十三）、C++二叉排序樹（BSTc風格）-創新互聯
URL標題：http://m.newbst.com/article44/dodcee.html

成都網站建設公司_創新互聯，為您提供網站營銷、App開發、網站策劃、網站制作、網站導航、App設計

廣告

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