• 数据结构——二叉排序树的删除操作（非递归）

    1、被删除的节点是叶子节点
    将双亲节点中相应的指针域的值改为空
    在这里插入图片描述
    2、被删除的节点只有左子树或右子树
    将要删除的节点的双亲节点相应指针域的值指向被删除节点的左子树或者右子树
    在这里插入图片描述
    3、被删除节点既有左子树又有右子树
    将左子树中的最大值或者右子树中的最小值代替该节点
    在这里插入图片描述

    TreeNode * DeleteTreeNode(TreeNode *root,int data){
	if(!root){
		return NULL;
	}
	TreeNode *node = NULL;//遍历指针
	TreeNode *parent = NULL;//记录指针的父节点
	node = root;
	while(1)//寻找要删除的位置
	{
        parent = node;//记录指针的父节点
		if(node ->data > data)//左边找
		{
            node = node ->left;
		}
		else if(node ->data < data)//右边找
		{
            node = node ->right;
		}
		if(node -> data == data)//找到了，退出循环
		{
			break;
		}
	}
	if(node == NULL){
		return NULL;
	}
	if(node -> left && node -> right)//左右孩子都有
	{
		TreeNode *temp = node;
        parent = node;
        node = node -> right;
		while(node -> left)//找右子树上最小的
		{
            parent = node;
            node = node -> left;
		}
        temp -> data = node -> data;//交换数据
		if(parent -> left == node)
		{
            parent ->left = node -> right;
			free(node);
		}
		else if(parent -> right == node)
		{
            parent -> right = node -> right;
			free(node);
		}
		return root;
	}
	if(!node -> left && !node -> right)//左右孩子都没有
	{
		if(node == root)//删除节点为根
		{
			free(root);
			return NULL;
		}
		if(parent -> left == node)
		{
            parent -> left = NULL;
			free(node);
		}
		else if(parent -> right == node)
		{
            parent -> right = NULL;
			free(node);
		}
		return root;
	}
	if(node -> left && !node -> right)//只有左孩子，没有右孩子
	{
		if(root == node)
		{
			root = node -> left;
            node -> left = NULL;
			free(node);
			return root;
		}
		if(parent -> left == node)
		{
            parent -> left = node -> left;
            node -> left = NULL;
			free(node);
		}
		else if(parent -> right == node)
		{
            parent -> right = node -> left;
            node -> left = NULL;
			free(node);
		}
		return root;
	}
	if(!node -> left && node -> right)//只有右孩子，没有左孩子
	{
		if(root == node)
		{
			root = node -> right;
            node -> right = NULL;
			free(node);
			return root;
		}
		if(parent -> left == node)
		{
            parent -> left = node -> right;
            node -> right = NULL;
			free(node);
		}
		else if(parent -> right == node)
		{
            parent -> right = node -> right;
            node -> right = NULL;
			free(node);
		}
		return root;
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115

    该方法存在的问题：
    ①当要删除的元素不存在时，while会陷入死循环
    ②二叉排序树只剩下最后一个元素时无法删除

    完整代码

    #include 
#include 
#define TRUE 1
#define FALSE 0
typedef struct TreeNode{
    int data;
    struct TreeNode *left,*right;
}TreeNode;
static TreeNode* preNode = NULL;
TreeNode* InsertNode(TreeNode* root,int data){//排序二叉树中插入元素
    if(!root){
        root = (TreeNode*)malloc(sizeof(TreeNode));
        root->data = data;
        root->right = NULL;
        root->left = NULL;
        return root;
    }else{
        if(root->data > data){
            root->left = InsertNode(root->left,data);
        }else if(root->data < data){
            root->right = InsertNode(root->right,data);
        }else if(root->data = data){
            return root;
        }
    }
    return root;
}
void InOrderTree(TreeNode* root){//中序遍历二叉树
    if(root == NULL){
        return;
    }
    InOrderTree(root->left);
    printf("%d->",root->data);
    InOrderTree(root->right);
}
//删除节点
TreeNode * DeleteTreeNode(TreeNode *root,int data){
	if(!root){
		return NULL;
	}
	TreeNode *node = NULL;//遍历指针
	TreeNode *parent = NULL;//记录指针的父节点
	node = root;
	while(1)//寻找要删除的位置
	{
        parent = node;//记录指针的父节点
		if(node ->data > data)//左边找
		{
            node = node ->left;
		}
		else if(node ->data < data)//右边找
		{
            node = node ->right;
		}
		if(node -> data == data)//找到了，退出循环
		{
			break;
		}
	}
	if(node -> left && node -> right)//左右孩子都有
	{
		TreeNode *temp = node;
        parent = node;
        node = node -> right;
		while(node -> left)//找右边最小的
		{
            parent = node;
            node = node -> left;
		}
        temp -> data = node -> data;//交换数据
		if(parent -> left == node)
		{
            parent ->left = node -> right;
			free(node);
		}
		else if(parent -> right == node)
		{
            parent -> right = node -> right;
			free(node);
		}
		return root;
	}
	if(!node -> left && !node -> right)//左右孩子都没有
	{
		if(node == root)//删除节点为根
		{
			free(root);
			return NULL;
		}
		if(parent -> left == node)
		{
            parent -> left = NULL;
			free(node);
		}
		else if(parent -> right == node)
		{
            parent -> right = NULL;
			free(node);
		}
		return root;
	}
	if(node -> left && !node -> right)//只有左孩子，没有右孩子
	{
		if(root == node)
		{
			root = node -> left;
            node -> left = NULL;
			free(node);
			return root;
		}
		if(parent -> left == node)
		{
            parent -> left = node -> left;
            node -> left = NULL;
			free(node);
		}
		else if(parent -> right == node)
		{
            parent -> right = node -> left;
            node -> left = NULL;
			free(node);
		}
		return root;
	}
	if(!node -> left && node -> right)//只有右孩子，没有左孩子
	{
		if(root == node)
		{
			root = node -> right;
            node -> right = NULL;
			free(node);
			return root;
		}
		if(parent -> left == node)
		{
            parent -> left = node -> right;
            node -> right = NULL;
			free(node);
		}
		else if(parent -> right == node)
		{
            parent -> right = node -> right;
            node -> right = NULL;
			free(node);
		}
		return root;
	}
}

int main() {
    int data[11] = {38,12,56,6,34,40,98,3,13,78,17};
    TreeNode* root = NULL;
    for(int i = 0; i < (sizeof(data)/sizeof (data[0]));i++){
        printf("第%d次插入的元素为：%d\n",i+1,data[i]);
        root =InsertNode(root,data[i]);
    }
    printf("\n");
    InOrderTree(root);
    printf("END\n");
    DeleteTreeNode(root,12);
    InOrderTree(root);
    printf("END\n");
    DeleteTreeNode(root,34);
    InOrderTree(root);
    printf("END\n");
    DeleteTreeNode(root,40);
    InOrderTree(root);
    printf("END\n");
    return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171

    程序运行结果

    第1次插入的元素为：38
第2次插入的元素为：12
第3次插入的元素为：56
第4次插入的元素为：6
第5次插入的元素为：34
第6次插入的元素为：40
第7次插入的元素为：98
第8次插入的元素为：3
第9次插入的元素为：13
第10次插入的元素为：78
第11次插入的元素为：17

3->6->12->13->17->34->38->40->56->78->98->END
3->6->13->17->34->38->40->56->78->98->END
3->6->13->17->38->40->56->78->98->END
3->6->13->17->38->56->78->98->END

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    对应的二叉树为：
    在这里插入图片描述

  • 相关阅读:
    软件测试 app自动化01 APP环境搭建 Appium自动化测试原理
    C++算法 —— 动态规划（4）子数组
    React 状态管理 - Context API 前世今生（下）
    Java SE 18 新增特性
    全面采集商品数据的电商API接口对接【支持5大主流电商平台】
    OctaneRender for CINEMA 4D 安装指南丨安装教程丨安装方法
    Spring Task单机定时任务(使用及阻塞问题解决)
    【数据结构】——堆 堆的实现、堆排序、TopK问题
    LeetCode 1726. 同积元组：哈希表（组合数学）
    double或Double取整或保留n位小数(后续如果有需要再整理其他小数类型)
  • 原文地址：https://blog.csdn.net/xinzhi1992/article/details/126583436