二叉排序树-查找/插入/删除

二叉排序树-查找#includestdio.h #includestdlib.h //二叉排序树--查找 typedef int ElemType; typedef struct TreeNode { ElemType data; struct TreeNode* lchild; struct TreeNode* rchild; }TreeNode; typedef TreeNode* BiTree; //用数组模拟先序遍历创建一棵二叉树 int treeArr[] { 70,55,49,30,-1,39,-1,-1,53,-1,-1,-1,80,75,-1,-1,98,95,-1,-1,-1 }; int idx 0; //递归先序方式构建二叉树 void createTree(BiTree* T) { ElemType num; num treeArr[idx]; if (num -1) { *T NULL; } else { *T (BiTree)malloc(sizeof(TreeNode)); (*T)-data num; createTree((*T)-lchild); createTree((*T)-rchild); } } //前序遍历输出该二叉树 void preOrder(BiTree T) { if (T NULL) { return; } printf(%d , T-data); preOrder(T-lchild); preOrder(T-rchild); } //T当前子树根节点 //value要查找的值 //parent当前节点的父节点 //pos指针变量用于返回找到的节点 int search_bst(BiTree T, int value, BiTree parent, BiTree* pos) { if (T NULL) { *pos parent;//如果传进来的是空节点就将它的父节点返回查找失败 return 0; } if (T-data value) { *pos T;//找到了目标值 return 1; } if (T-data value)//如果当前的节点大于要找的值就去该节点的左孩子里找 //否则就去右孩子里找 { return search_bst(T-lchild, value, T, pos); } else { return search_bst(T-rchild, value, T, pos); } } int main(int argc, char const* argv[]) { BiTree T; createTree(T); BiTree searchT; search_bst(T, 53, NULL, searchT); preOrder(T); printf(\n); printf(%d\n, searchT-data);//输出查找到的节点值 return 0; } //输出70 55 49 30 39 53 80 75 98 95 53二叉排序树-插入#includestdio.h #includestdlib.h //二叉树节点结构体定义 typedef int ElemType; typedef struct TreeNode { ElemType data; struct TreeNode* lchild; struct TreeNode* rchild; }TreeNode; typedef TreeNode* BiTree; //前序遍历输出该二叉树 void preOrder(BiTree T) { if (T NULL) { return; } printf(%d , T-data); preOrder(T-lchild); preOrder(T-rchild); } //二叉排序树-查找 int search_bst(BiTree T, int value, BiTree parent, BiTree* pos) { if (T NULL) { *pos parent;//如果传进来的是空节点就将它的父节点返回查找失败 return 0; } if (T-data value) { *pos T;//找到了目标值 return 1; } if (T-data value)//如果当前的节点大于要找的值就去该节点的左孩子里找 //否则就去右孩子里找 { return search_bst(T-lchild, value, T, pos); } else { return search_bst(T-rchild, value, T, pos); } } //二叉排序树-插入 int insert_bst(BiTree* T, int value) { BiTree parent, pos; //parent当前插入节点的父节点用于辅助search_bst() //pos表示插入位置或已存在的位置 BiTree curr; int status search_bst(*T, value, NULL, pos);//查找要插入的位置 if (status 0)//没找到要插入的值就返回了0status为0 { curr (BiTree)malloc(sizeof(TreeNode));//如果未找到创建新节点 curr-data value; curr-lchild NULL; curr-rchild NULL; if (pos NULL)//如果树本身为空新节点作为根节点。 //所以插入还可以用来作为创建一棵树 { *T curr; } else if (value pos-data) //此时pos和parent都是98 //要插入的99比98大所以赋值给98的右节点 { pos-lchild curr; } else { pos-rchild curr; } return 1; } else {//如果已存在要插入的这个节点就return 0不插入 return 0; } } int main(int argc, char const* argv[]) { int i 0; BiTree T NULL; //准备插入的初始序列 int treeArr[] { 70,55,49,30,39,53,80,75,98,95 }; //批量插入 for (int i 0; i 10; i) { insert_bst(T, treeArr[i]); } preOrder(T); printf(\n); insert_bst(T, 99);//插入一个新值99 preOrder(T); printf(\n); return 0; } //输出 //70 55 49 30 39 53 80 75 98 95 //70 55 49 30 39 53 80 75 98 95 99二叉排序树-删除#includestdio.h #includestdlib.h typedef int ElemType; typedef struct TreeNode { ElemType data; struct TreeNode* lchild; struct TreeNode* rchild; }TreeNode; typedef TreeNode* BiTree; //前序遍历输出该二叉树 void preOrder(BiTree T) { if (T NULL) { return; } printf(%d , T-data); preOrder(T-lchild); preOrder(T-rchild); } //二叉排序树-查找 int search_bst(BiTree T, int value, BiTree parent, BiTree* pos) { if (T NULL) { *pos parent;//如果传进来的是空节点就将它的父节点返回查找失败 return 0; } if (T-data value) { *pos T;//找到了目标值 return 1; } if (T-data value)//如果当前的节点大于要找的值就去该节点的左孩子里找 //否则就去右孩子里找 { return search_bst(T-lchild, value, T, pos); } else { return search_bst(T-rchild, value, T, pos); } } //二叉排序树-插入 int insert_bst(BiTree* T, int value) { BiTree parent, pos; //parent当前插入节点的父节点用于辅助search_bst() //pos表示插入位置或已存在的位置 BiTree curr; int status search_bst(*T, value, NULL, pos);//查找要插入的位置 if (status 0)//没找到要插入的值就返回了0status为0 { curr (BiTree)malloc(sizeof(TreeNode));//如果未找到创建新节点 curr-data value; curr-lchild NULL; curr-rchild NULL; if (pos NULL)//如果树本身为空新节点作为根节点。 //所以插入还可以用来作为创建一棵树 { *T curr; } else if (value pos-data) //此时pos和parent都是98 //要插入的99比98大所以赋值给98的右节点 { pos-lchild curr; } else { pos-rchild curr; } return 1; } else {//如果已存在要插入的这个节点就return 0不插入 return 0; } } //二叉排序树-删除 //叶子节点可以直接删除 //有一个节点的删除后子承父业 //删除的节点右两个孩自使用右子树最小的节点代替或者左子树中最大的节点 //真正执行删除的操作分三种情况 int deleteNode(BiTree* d) //函数名本来是delete但delete是C的关键字不能用 { BiTree temp, record; //情况一只有左孩子或无子节点 if ((*d)-rchild NULL) { temp *d; *d (*d)-lchild;//95是98的左孩子98没右孩子 free(temp);//把95给98再释放temp } //情况二只有右孩子 else if ((*d)-lchild NULL) { temp *d; *d (*d)-rchild; free(temp); //例如要删3030有39这个右孩子没左孩子就把39放到30再释放30 } //情况三左右子树都有找左子树中最大的节点替换 //例如要删除49d49record30 else { temp *d;//49 record (*d)-lchild;//30 while (record-rchild ! NULL) { temp record;//这里temp30 record record-rchild;//record39 } //替换当前值 (*d)-data record-data;//d39就是把39放到49的位置盖住49 //删除替代节点 if (temp ! *d) { temp-rchild record-lchild; //39的左孩子为空。如果有左孩子就是相当于把左孩子放到39的位置盖住39 } else { temp-lchild record-lchild; } free(record);//释放底下的39 } return 1; } //递归查找并删除目标节点 int delete_bst(BiTree* T, int value) { if (*T NULL) { printf(not found!\n); return 0; } else {//根节点和要删除的值比较 if ((*T)-data value) { return deleteNode(T);//找到这个节点了就调用delete() } else if ((*T)-data value) { return delete_bst((*T)-lchild, value); } else { return delete_bst((*T)-rchild, value); } } } int main(int argc, char const* argv[]) { int i 0; BiTree T NULL; int treeArr[] { 70,55,49,30,39,53,80,75,98,95 }; for (int i 0; i 10; i) { insert_bst(T, treeArr[i]); } preOrder(T); printf(\n); delete_bst(T, 49); preOrder(T); printf(\n); return 0; } //输出 //70 55 49 30 39 53 80 75 98 95 //70 55 39 30 53 80 75 98 95注代码来自B站逊哥带你学计算机