iT邦幫忙

0

【資料結構】二元樹的刪除

說明

說明

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

尚未有邦友留言

立即登入留言