数据结构与算法------二叉排序树

1. 结点结构

typedef struct BSTBitNode {
    int data;
    struct BSTBitNode *lchild,*rchild;
}BSTBitNode,*BSTBitTree;

2.  插入结点

static BSTBitNode * make_node(int key)
{
    BSTBitNode *p = (BSTBitNode *)malloc(sizeof(BSTBitNode));
    if(p == nullptr) {
        return nullptr;
    }
    p->data = key;
    p->lchild = p->rchild = nullptr;
    return p;
}

BSTBitNode *insertBST(BSTBitTree *proot,int key)
{
    BSTBitNode *pkey,*child,*parent;
    if(searchBST(*proot,key) != nullptr) {
        return nullptr;
    }

    pkey = make_node(key);

    if(*proot == nullptr) {
        *proot = pkey;
        return *proot;
    }
    parent = *proot;
    child = *proot;
    do{
        parent = child;
        if(key<parent->data) {
            child = parent->lchild;
        }
        else {
            child = parent->rchild;
        }
    }while(child != nullptr);
    if(key<parent->data) {
        parent->lchild = pkey;
    }
    else {
        parent->rchild = pkey;
    }
    return pkey;
}

  递归形式的插入结点：

BSTBitNode *insertBST_v2(BSTBitTree *proot,int key)
{
//    if(proot == nullptr) {
//        return nullptr;
//    }  //暂不考虑
    if(*proot == nullptr) {
        //说明当前还是空树
        *proot = make_node(key);
    }
    else if(key<(*proot)->data) {
        (*proot)->lchild = insertBST_v2(&((*proot)->lchild),key);
    }
    else if(key>(*proot)->data) {
        (*proot)->rchild = insertBST_v2(&((*proot)->rchild),key);
    }

    return (*proot);

}

3. 查找

（1）查找某结点：

BSTBitNode *searchBST(const BSTBitTree root,int key)
{
    if(root == nullptr) {
        return nullptr;
    }
    if(key<root->data) {
        return searchBST(root->lchild,key);
    }
    else if(key>root->data) {
        return searchBST(root->rchild,key);
    }
    else {
        return root;
    }
    // return nullptr; //这行没必要，对不在树中的元素进行查找，最后一次的递归调用会传nullptr进去，最后返回值也是nullptr
}

（2）

  查找最小、最大（参数是树的root时，最小结点就是中序遍历的第一个结点，最大结点就是中序遍历的最后一个结点）：

BSTBitNode *findBSTMin(BSTBitTree root)  //以当前结点为根子树的最左边的结点
{
    if(root == nullptr) {
        return nullptr;
    }
    else if(root->lchild == nullptr) {   //换成rchild就是找最大值
        return root;
    }
    else {
        return findBSTMin(root->lchild);   //这里也要换成rchild
    }
}

BSTBitNode *findBSTMax (BSTBitTree root)
{
    if(root != nullptr) {
        while(root->rchild != nullptr) {
            root = root->rchild;
        }
    }
    return root;
}

（3）查找中序遍历时某结点的前驱、后继

　　前驱：该结点左子树的最大结点(最大结点即最右边的结点，必然是叶子结点)---------该结点左子树的最右边结点

findBSTMax(node->lchild);

　　后继：该结点右子树的最小结点（最小结点即最左边的结点，必然是叶子结点）---------该结点右子树的最左边结点

findBSTMin(node->rchild); 

4. 删除结点

4.1

  删除的策略：要删除的结点是如下：

　　（1）结点为叶子结点：删除当前结点，并修改其父结点的指针

　　（2）只有单个子结点：①只有左子，则要删除结点的父结点指向该左子 ②只有右子，类似

　　（3）要删除有两个子结点的结点：用该结点的前驱或后继的内容代替该结点，再将那个前驱或后继从它们的位置上删掉

BSTBitNode *deleteNode_v2(BSTBitTree root,int key)
{
    BSTBitNode *tmp = nullptr;
    if(root == nullptr) {
        cout<<"Element:"<<key<<" not found."<<endl;
    }
    else if(key<root->data) {
        root->lchild = deleteNode_v2(root->lchild,key);
    }
    else if(key>root->data) {
        root->rchild = deleteNode_v2(root->rchild,key);
    }
    else {
        if(root->lchild && root->rchild) {
            tmp = findBSTMin(root->rchild); //找到要删除结点的后继
            root->data = tmp->data;
            root->rchild = deleteNode_v2(root->rchild,root->data);

//            tmp = findBSTMax(root->lchild);//找到要删除结点的前驱
//            root->data = tmp->data;
//            root->lchild = deleteNode_v2(root->lchild,key);
            //以上用结点前驱或后继数据代替当前结点数据都可以
        }
        else {
            //要删除结点只有单个孩子结点或没有孩子结点的情况
            tmp = root;
            if(root->lchild == nullptr) {
                root = root->rchild;
            }
            else if(root->rchild == nullptr) {
                root = root->lchild;
            }
            free(tmp);
        }
    }
    return root;
}

//以下的是通用的代码

　　

5. 删除整个树

static void freeBSTTree(BSTBitTree root) {
    if(root != nullptr) {
        freeBSTTree(root->lchild);
        freeBSTTree(root->rchild);
        free(root);
    }
}

void clearBSTTree(BSTBitTree *proot)
{
    freeBSTTree(*proot);
    *proot = nullptr;
}

6. 统计树中结点个数

  (1)如果二叉树为空，结点个数为0
  (2)如果二叉树不为空， 当前树结点个数=左子树结点个数+右子树结点个数+1

int getBitTreeNum(BSTBitTree root)
{
    if(root == nullptr) {
        return 0;
    }
    return getBitTreeNum(root->lchild)+getBitTreeNum(root->rchild)+1;
}

7. 计算树深度

  (1)如果二叉树为空，二叉树深度为0
  (2)如果二叉树不为空， 当前树深度=max(左子树深度,右子树深度)+1

int getBitTreeDepth(BSTBitTree root)
{
    if(root == nullptr) {
        return 0;
    }
    int leftDepth = getBitTreeDepth(root->lchild);
    int rightDepth = getBitTreeDepth(root->rchild);
    return leftDepth>rightDepth?(leftDepth+1):(rightDepth+1);
}

8. 中序遍历BST

void inOrderTravelBST(BSTBitTree root)
{
    if(root != nullptr) {
        inOrderTravelBST(root->lchild);
        std::cout<<root->data<<" ";
        inOrderTravelBST(root->rchild);
    }
}

9. 深度优先遍历、广度优先遍历

void DepthFirstSearch(BSTBitTree root)
{
    stack<BSTBitNode *> bstNodeStack;
//    queue<BSTBitNode *> res;

    bstNodeStack.push(root);
    while(!bstNodeStack.empty()) {
        BSTBitNode *node = bstNodeStack.top();
        cout<<node->data<<" ";
//        res.push(node);
        bstNodeStack.pop();
        if(node->rchild) {
            bstNodeStack.push(node->rchild);
        }
        if(node->lchild) {
            bstNodeStack.push(node->lchild);
        }
    }
    cout<<endl;
//    while(!res.empty()) {
//        BSTBitNode *node = res.front();
//        cout<<node->data<<" ";
//        res.pop();
//    }
//    cout<<endl;
}

void BreadthFirstSearch(BSTBitTree root)
{
    queue<BSTBitNode *> bstNodeQueue;
//    queue<BSTBitNode *> res;  //如果需要返回的话
    bstNodeQueue.push(root);
    while(!bstNodeQueue.empty()) {
        BSTBitNode *node = bstNodeQueue.front(); //取队列中第一个数据
        cout<<node->data<<" ";
//        res.push(node);
        bstNodeQueue.pop();

        if(node->lchild) {
            bstNodeQueue.push(node->lchild);
        }
        if(node->rchild) {
            bstNodeQueue.push(node->rchild);
        }
    }
    cout<<endl;
//    while(!res.empty()) {
//        BSTBitNode *node = res.front();
//        cout<<node->data<<" ";
//        res.pop();
//    }
//    cout<<endl;
}