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

说明

说明

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

<<:  CDB(集中式) 是什麽? DDB(分散式)是什麽?

>>:  iOS App开发 OC 第二天, 属性 @property 的特性(attribute)

Day 24 - 了解文字艺术

Rita.js Rita 使用范例 拆解字串:RiString() 取得词性 pos()(Part ...

Golang-gRPC & Protocol Buffers

之前都是使用RESTful API开发 换工作面试几轮之後发现有蛮多家公司都在使用gRPC 就多学一...

DAY25-问答页面设计

前言: 几个基本的页面都设计得差不多啦~这次的挑战也快接近尾声了!今天就让阿森来介绍一个有点小特效...

NIST SP 800-53A R4-测试深度&测试范围

“覆盖范围属性解决了评估的范围或广度。” (NIST SP 800-53A)测试的范围与测试范围有关...

【从零开始的Swift开发心路历程-Day16】安装RealmSwift资料库Part2(完)

昨天我们安装完CocoaPods後,今天就来安装RealmSwift吧! 要安装RealmSwift...