- /*
- * @文件:searchBinaryTree.c
- * @内容:查找二叉树,插入,查找,删除。
- * @作者:Luke
- * @时间:2014.11.12
- */
- #include <stdio.h>
- #include <stdlib.h>
- #define MAX 100
- /*
- * 结点,值域:关键字-值,key-data,但是这个程序里没有用到data域。
- */
- typedef struct Node {
- int key;
- char data;
- struct Node *left, *right;
- }Node, *Node_pointer;
- // 这些操作函数
- int sbt_insert(Node_pointer *Root, Node new_n);// 插入
- Node_pointer sbt_search(Node_pointer Root, int key);// 查找
- int sbt_delete(Node_pointer *Root, int key);// 删除
- void sbt_traver(Node_pointer Root);// 遍历
- /*
- * 功能:插入新的节点new_n。
- * 返回值:0成功,-1失败。
- */
- int sbt_insert(Node_pointer *Root, Node new_n) {
- if (sbt_search(*Root, new_n.key) != NULL) {
- printf("key %d already in the search binary tree!\\n", new_n.key);
- return -1;
- }
- // 定义两个指针,p指向当前节点,
- // y是指向p所指向节点的父节点的指针,注意是指针的指针。
- Node_pointer *y = Root;
- Node_pointer p = *Root;
- // 找到应该插入的位置。
- while (p) {
- if (p->key < new_n.key) {
- y = &(p->right);
- p = p->right;
- }
- else {
- y = &(p->left);
- p = p->left;
- }
- }
- // 此时*y指向的正是new_n应该插入位置的指针,
- // 动态分配新的节点。
- *y = (Node_pointer)malloc(sizeof(Node));
- if (!(*y)) {
- printf("Memory allocation failed!\\n");
- return -1;
- }
- (*y)->key = new_n.key;
- (*y)->data = new_n.data;
- (*y)->left = (*y)->right = NULL;
- return 0;
- }
- /*
- * 功能:查找是否存在关键字为key的节点的值data.
- * 返回值:找到则返回节点指针,否则返回NULL。
- */
- Node_pointer sbt_search(Node_pointer Root, int key) {
- while (Root) {
- if (Root->key == key)
- return Root;
- else if (Root->key < key)
- Root = Root->right;
- else
- Root = Root->left;
- }
- return NULL;
- }
- /*
- * 功能:遍历输出查找二叉树,先序遍历。
- */
- void sbt_traver(Node_pointer Root) {
- if (Root) {
- // 这里就只输出关键字好了key
- printf("<%d>", Root->key);
- sbt_traver(Root->left);
- sbt_traver(Root->right);
- }
- }
- /*
- * 功能:删除指定关键字key的节点。
- * 返回值:成功0,失败-1。
- * 思路,按被删除节点分三种情况:
- * 情况1:叶子节点,也就是左右子树都没。
- * 情况2:只有一个左子树/右子树。
- * 情况3:左右子树都有,这时抽取左子树的最大节点。
- */
- int sbt_delete(Node_pointer *Root, int key) {
- // 依然定义一个y和p
- Node_pointer *y1 = Root;
- Node_pointer p1 = *Root;
- // 然后我们先找到节点。
- while (p1 && p1->key != key) {
- if (p1->key < key) {
- y1 = &(p1->right);
- p1 = p1->right;
- }
- else {
- y1 = &(p1->left);
- p1 = p1->left;
- }
- }
- if (!p1) {
- // 先处理找不到关键字节点的情况,删除失败呗!!~~
- return -1;
- }
- else {
- // 此时y1指向节点的指针,p1指向关键字位置。
- if (!(p1->right) && !(p1->left)) {
- // 情况1:是叶子节点,直接删除。
- *y1 = NULL;
- free(p1);
- p1 = NULL;
- }
- else if (p1->right && !(p1->left)) {
- // 情况2:只有右孩子,*y1直接指向右孩子,并删除关键字节点p1。
- *y1 = p1->right;
- free(p1);
- p1 = NULL;
- }
- else if (!(p1->right) && p1->left) {
- // 情况2:只有左孩子,一样。
- *y1 = p1->left;
- free(p1);
- p1 = NULL;
- }
- else {
- // 情况3:左右孩子都有。
- // 这里还要借助新的指针操作关键字节点的左子树:
- Node_pointer *y2 = &(p1->left);
- Node_pointer p2 = p1->left;
- // 找到左子树的最大节点
- while (p2 && p2->right) {// 其实直接p2->right就可以了,是不是???
- y2 = &(p2->right);
- p2 = p2->right;
- }
- // 其实这里p2肯定不会指向NULL的,想想为什么?~~~
- if (p2) {
- // 别忘了让*y2接手p2节点的左子树。
- *y2 = p2->left;
- // 然后让p2代替p1的位置。
- *y1 = p2;
- p2->right = p1->right;
- p2->left = p1->left;
- // 释放p1
- free(p1);
- p1 = NULL;
- }
- }
- return 0;
- }
- }
- int main(void) {
- Node a[MAX] = {0};
- Node_pointer Root = NULL;
- int i, n = 0;
- int key = 0;
- // 输入测试数据到数组a
- printf("节点个数:n = ");
- scanf("%d", &n);
- printf("输入%d组数据key:\\n", n);
- for (i = 0; i < n; i ++)
- scanf("%d", &a[i].key);
- // 创建查找二叉树,可以想到,第一个数据就变成了树根节点。
- for (i = 0; i < n; i ++) {
- sbt_insert(&Root, a[i]);
- }
- // 遍历输出二叉树。
- sbt_traver(Root);
- printf("\\n");
- // 查找一个关键字。
- printf("查找关键字key = ");
- scanf("%d", &key);
- Node_pointer tmp = sbt_search(Root, key);
- if (tmp)
- printf("找到了:key = %d, data = %d\\n", tmp->key, tmp->data);
- else
- printf("没找到!key = %d\\n", key);
- printf("----------------------\\n");
- // 删除一个关键字。
- printf("删除关键字key = ");
- scanf("%d", &key);
- if (sbt_delete(&Root, key) != 0)
- printf("删除失败!\\n");
- else
- printf("删除成功!key = %d\\n", key);
- printf("----------------------\\n");
- // 再次遍历。
- sbt_traver(Root);
- printf("\\n");
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/1903201511920.html
来源: http://www.codesnippet.cn/detail/1903201511920.html