C语言算法二叉查找树基本操作

二叉查找树：左子 tree* node = (tree*)malloc(sizeof(tree)); if (node == NULL) { return node; } node->data = p_data; node->lchild = NULL;//左右子均置空 node->rchild = NULL; return node; } //中序遍历 //和普通二叉树中序遍历相同 void m_order(tree* root) { if (root != NULL) { if (root->lchild != NULL) { m_order(root->lchild); } printf("%d\t", root->data); if (root->rchild != NULL) { m_order(root->rchild); } } } //插入结点 //思路：定义一个新的结点，接收数据，接受到的数据>原root结点的数据就向右子树插入 //接受到的数据 return node; } if (node == NULL) { return root; } if (node->data > root->data) { root->rchild = insert(root->rchild, node); } else if (node->data data) { root->lchild = insert(root->lchild, node); } else { printf("%d已存在无需插入", node->data); } return root; } //删除 //思路：进入原二叉树中判断删除的值的大小与root的关系 //小于向左子树前进，大于向右子树前进 //当找到时创建一个临时的结点接收要删除的数据，让目标释放 //处理方式：如果结点是树叶直接可以删除，如果有有一个子结点就用其子结点代替要删除的结点 //如果有两个或以上的结点树，是根的左子树就用其右子树中的最小值代替 //是根的右子树就用其左子树中的最大值代替，最后释放 tree* del(tree* root, int p_data) { if (root == NULL) { return NULL; } if (p_data data) { root->lchild = del(root->lchild, p_data); } else if (p_data > root->data) { root->rchild = del(root->rchild, p_data); } else { tree* temp; if (root->lchild != NULL) { for (temp = root->lchild; temp->rchild != NULL; temp = temp->rchild);//寻找左子树最右结点 root->data = temp->data;//替换要删除的结点 del(root->lchild, temp->data);//删除替换结点 } if (root->rchild != NULL) { for (temp = root->rchild; temp->lchild != NULL; temp = temp->lchild);//寻找右子树最左结点 root->data = temp->data;//替换要删除的结点 del(root->rchild, temp->data);//删除替换结点 } else { free(root); return NULL; } } return root; } //寻找结点 void find(tree* root,int fnum) { if (root == NULL) { /*return NULL;*/ printf("error\n"); } if (fnum data) { /*return find(root->lchild, fnum);*/ find(root->lchild, fnum); printf("二叉树中有该结点\n"); } else if (fnum > root->data) { /*return find(root->rchild, fnum);*/ find(root->rchild, fnum); printf("二叉树中有该结点\n"); } /*return root;*/ } //find max结点 tree* findmax(tree* root) { if (root == NULL) { return NULL; } else if (root->rchild == NULL) { return root; } else { return findmax(root->rchild); } } //find min结点 tree* findmin(tree* root) { if (root == NULL) { return NULL; } else if (root->lchild == NULL) { return root; } else { return findmin(root->lchild); } } int main() { //测试：6214380 //tree* root = initnode(0);不能这样去写，因为0会被接收存在内存中！ tree* root = (tree*)malloc(sizeof(tree)); root = NULL; int value,choose; while (1) { printf("*****************************二叉查找树基本操作*****************************\n"); printf("*****************************1.创建二叉查找树*******************************\n"); printf("*****************************2.插入结点*************************************\n"); printf("*****************************3.删除结点*************************************\n"); printf("*****************************4.中序遍历*************************************\n"); printf("*****************************5.寻找二叉查找树中的结点***********************\n"); printf("*****************************6.寻找二叉查找树中的最大的结点*****************\n"); printf("*****************************7.寻找二叉查找树中的最小的结点*****************\n"); printf("*****************************8.退出exit*************************************\n"); printf("****************************************************************************\n"); printf("请输入你要选择的功能："); scanf_s("%d", &choose); if (choose == 8) { printf("程序退出》》》"); break; } switch (choose) { case 1: { while (1) { printf("请输入一个二叉搜索树的结点:\n"); scanf_s("%d", &value); if (value > 0) { tree* node = initnode(value); root = insert(root, node); } else { break; } } printf("当前的二叉查找树为：\n"); m_order(root); printf("\n"); } break; case 2: { while (1) { printf("请输入你要插入的二叉搜索树的结点:\n"); scanf_s("%d", &value); if (value > 0) { tree* node = initnode(value); root = insert(root, node); } else { break; } } printf("当前的二叉查找树为：\n"); m_order(root); printf("\n"); } break; case 3: { int delchoose,n; printf("选择你要的功能：1.单次删除\t 2.多次删除\n"); //在多次删除的时候注意不要输入已删除结点的子结点 scanf_s("%d", &delchoose); if (delchoose == 1) { printf("请输入你要删除的二叉搜索树的结点:\n"); scanf_s("%d", &value); root = del(root, value); printf("当前的二叉查找树为：\n"); m_order(root); printf("\n"); } else if (delchoose == 2) { printf("你要删除的个数:"); scanf_s("%d", &n); for (int i = 0; i printf("当前的二叉查找树为：\n"); m_order(root); printf("\n"); printf("error"); } } break; case 4: printf("当前的二叉查找树为：\n"); m_order(root); printf("\n"); break; case 5: { int findnum; printf("输入你要查找的结点:"); scanf_s("%d", &findnum); /*root = find(root, findnum);*/ find(root, findnum); //if (root != NULL) //{ // /*printf("二叉查找树中有该结点：%d\n", *root);*/ // printf("二叉树中有该结点："); // find(root, findnum); //} //else //{ // printf("error二叉查找树中无该结点\n"); break; } case 6: printf("二叉查找树中-- %d --是最大的结点\n", *findmax(root)); /*printf("二叉查找树中最大的结点：\n"); findmax(root);*/ break; case 7: printf("二叉查找树中-- %d --是最小的结点\n", *findmin(root)); break; default: printf("error!\n"); break; } } return 0; }

程序展示： 注意：在写寻找结点的函数时要用void型这样不会改变原始二叉查找树！