数据结构（十三）、C++二叉排序树（BSTc风格）-创新互联

#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元起，快前往官网查看详情吧