說明

說明

• 1.根結點中的兩邊固定一邊大另一邊小。
• 2.下方節點當作新的根結點，繼續符合一邊大一邊小的規則。
• 3.無重複值。
• 4.二元搜尋樹是進行搜尋、插入、刪除最好的資料結構。
  

程式

前置準備

#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;
}