【资料结构】二元树的删除

说明

说明

程式

前置準备

#include <stdbool.h>#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct tree *tree_p;struct tree {  int data;  tree_p left;  tree_p right;  bool t_left;  bool t_right;  tree_p back;} tree;

副函式

tree_p max_p(tree_p root):找寻该根最大节点

带入树的某节点，利用搜寻树最大值放右侧的特性，可回传该根最大位址

tree_p max_p(tree_p root) {  tree_p temp = NULL;  while (root != NULL) {    temp = root;    root = root->right;  }  return temp;}

tree_p del(tree_p point, int num):删除节点

带入某树根与欲删除点，可经过三种不同情况的判断将结点删除

tree_p del(tree_p point, int num) {  tree_p temp = point;  if (point == NULL) {    printf("%d does not exist in the tree.\n",num);    //节点不存在  } else if (point->data > num) {    point->left = del(point->left, num);  } else if (point->data < num) {    point->right = del(point->right, num);  }//节点以搜寻树的方式，利用递迴找址   else {    //找到位址      if (point->left != NULL && point->right != NULL) {       //有左右节点，找寻该根最大值取代欲删除点，并将最大值位置删除      temp = max_p(point->left);      point->data = temp->data;      point->left = del(point->left, temp->data);    } else {        //只有一个左右节点或无左右节点      if (point->left == NULL) {        point = point->right;      } else if (point->right == NULL) {        point = point->left;      }    }  }  return point;}