二叉搜索树的插入，删除，和中序遍历

构建一个值的类型为int的二叉搜索树，输入N和M，然后进行N次插入操作，每次插入之后进行一次遍历验证代码正确性。然后进行M次删除操作，每次删除之后进行一次遍历验证代码正确性。

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
struct BST {
    int value;
    BST* lson;
    BST* rson;
}* root;
void remove(int value);
BST* init(int val) {
    BST* point = (BST*)malloc(sizeof(BST));
    point->value = val;
    point->lson = point->rson = NULL;
    return point;
}
void insert(int val) {
    BST* father = NULL;
    BST* now = root;
    while (now != NULL) {
        if (now->value == val) {
            return;
        }
        father = now;
        if (now->value < val) {
            now = now->rson;
        } else {
            now = now->lson;
        }
    }
    if (father == NULL) {
        root = init(val);
    } else if (father->value < val) {
        father->rson = init(val);
    } else {
        father->lson = init(val);
    }
}
/*这题的难点在于删除一个节点，思路是:
  当要删除的节点右子树不为空时，用右子树中的最小值代替要删除的节点的值，同时删除右子树中值最小的节点
  否则右子树为空，可以用左子树代替当前位置
  当要删除的节点是唯一节点时,将root置为空
*/
int findAndRemoveMin(BST* point) {
    while (point->lson != NULL) {
        point = point->lson;
    }
    int ans = point->value;
    remove(ans);
    return ans;
}
void remove(int value) {
    BST* father = NULL;
    BST* now = root;
    while (now != NULL) {
        if (now->value == value) {
            if (now->rson != NULL) {
                now->value = findAndRemoveMin(now->rson);
            } else {
                if (father == NULL) {
                    root = root->lson;
                } else if (now->value > father->value) {
                    father->rson = now->lson;
                } else {
                    father->lson = now->lson;
                }
                free(now);
            }
            return;
        }
        father = now;
        if (now->value < value) {
            now = now->rson;
        } else {
            now = now->lson;
        }
    }
}
//二叉搜索树中序遍历后会得到一个升序数列，这里用递归写起来很方便；
void ergodic(BST* point) {
    if (point == NULL) {
        return;
    }
    ergodic(point->lson);
    printf("%d ", point->value);
    ergodic(point->rson);
}
int main() {
    int N, M, value;
    scanf("%d%d", &N, &M);
    while (N--) {
        scanf("%d", &value);
        insert(value);
        ergodic(root);
        puts("");
    }
    while (M--) {
        scanf("%d", &value);
        remove(value);
        ergodic(root);
        puts("");
    }
    return 0;
}

二叉树的中序遍历还有一种非递归写法，以此代码代替上面的ergodic效果也是一样的

void ergodic(BST* point) {
    stack<BST*> sta;
    while (point != NULL || !sta.empty()) {
        while (point != NULL) {
            sta.push(point);
            point = point->lson;
        }
        point = sta.top();
        sta.pop();
        printf("%d ", point->value);
        point = point->rson;
    } 
}

原文链接: https://www.cnblogs.com/Jathon-cnblogs/p/10220498.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/288010

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

二叉搜索树的插入，删除，和中序遍历

相关推荐