二叉查找树二叉查找树

二叉查找树

二叉查找树是一种特殊的二叉树,该数据结构的核心性质是:

对于树中的每个节点X,它的左子树中所有关键字值小于X的关键字值,而它的右子树中所有关键字值大于X的关键字值

二叉查找树ADT

  • MakeEmpty:清空二叉查找树
  • Find:给出关键字值,返回该关键字值的节点指针
  • FindMin与FindMax:返回最小关键字值和最大关键字值的节点指针
  • Insert:插入一个给定关键字值的节点
  • Delete:删除一个指定关键字值的节点

代码实现

结构体

type tree_data struct {
    data int
}

type tree_node struct {
    num         int
    data        tree_data
    left_point  *tree_node
    right_point *tree_node
    parent      *tree_node
}

构造函数

func New_tree_node(num int, data tree_data, parent *tree_node) *tree_node {
    node := tree_node{}
    node.num = num
    node.data = data
    node.left_point = nil
    node.right_point = nil
    node.parent = parent
    return &node
}

清空方法

func (t *tree_node) MakeEmpty() {
    if t.left_point != nil {
        t.left_point.MakeEmpty()
    }
    if t.right_point != nil {
        t.right_point.MakeEmpty()
    }
    t.num = 0
    t.data = tree_data{}
}

查找方法

查找时:

  • 当待查标号大于本节点标号时,向右子树查询
  • 当待查标号小于本节点标号时,向左子树查询
  • 当待查标号等于本节点标号时,命中,返回本节点指针
func (t *tree_node) Find(num int) (*tree_node, error) {
    if num > t.num {
        if t.right_point == nil {
            return &tree_node{}, errors.New("num not exsist")
        } else {
            return t.right_point.Find(num)
        }
    } else if num < t.num {
        if t.left_point == nil {
            return &tree_node{}, errors.New("num not exsist")
        } else {
            return t.left_point.Find(num)
        }
    } else {
        return t, nil
    }
}

查找最小值/最大值方法

func (t *tree_node) FindMin() *tree_node {
    if t.left_point != nil {
        return t.left_point.FindMin()
    } else {
        return t
    }
}
func (t *tree_node) FindMax() *tree_node {
    if t.right_point != nil {
        return t.right_point.FindMax()
    } else {
        return t
    }
}

插入方法

插入时:

  • 当插入标号大于本节点标号,向右子树插入
  • 当插入标号小于本节点标号,向左子树插入
  • 当插入标号等于本节点标号,覆盖原值
func (t *tree_node) Insert(num int, data tree_data) {
    if num > t.num {
        if t.right_point != nil {
            t.right_point.Insert(num, data)
        } else {
            t.right_point = New_tree_node(num, data, t)
        }
    } else if num < t.num {
        if t.left_point != nil {
            t.left_point.Insert(num, data)
        } else {
            t.left_point = New_tree_node(num, data, t)
        }
    } else {
        t.data = data
    }
}

删除方法

删除时,若删除的是本节点,则:

  • 当本节点没有子树(是树叶)时,直接将母节点指向该节点指针置nil(删除该节点)
  • 当本节点仅有一个子树时,直接将本节点替换为子节点
  • 当本节点有两个子树时,找到右节点的最小节点a,将本节点数据与标号替换为a节点的数据和标号,再递归的删除节点a
func (t *tree_node) Delete(num int) {
    if num < t.num {
        t.left_point.Delete(num)
    } else if num > t.num {
        t.right_point.Delete(num)
    } else {
        if t.left_point == nil && t.right_point == nil {
            if t.parent.left_point.num > t.num {
                t.parent.left_point = nil
            } else {
                t.parent.right_point = nil
            }
        } else {
            if t.left_point == nil {
                t.parent = t.right_point
            } else if t.right_point == nil {
                t.parent = t.left_point
            } else {
                temp := t.right_point.FindMin()
                t.num = temp.num
                t.data = temp.data
                temp.Delete(temp.num)
            }
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏向治洪

数据结构之线性表

基本概念 线性表(List):由零个或多个数据元素组成的有限序列。 特征: 1.线性表是一个序列。 2.0个元素构成的线性表是空表。 3.线性表中的第一个元素无...

21590
来自专栏机器学习入门

LWC 52:687. Longest Univalue Path

LWC 52:687. Longest Univalue Path 传送门:687. Longest Univalue Path Problem: Given...

23970
来自专栏java学习

面试题18(以下关于集合类 ArrayList 、 LinkedList 、 HashMap 描述错误的是?)

以下关于集合类 ArrayList 、 LinkedList 、 HashMap 描述错误的是? A)HashMap实现Map接口,它允许任何类型的键和值对象,...

30750
来自专栏haifeiWu与他朋友们的专栏

聊聊HashSet源码

今天聊一下HashSet源码,HashSet内部基本使用HashMap来实现,本博客将通过一下几个方向讲解。

9730
来自专栏余林丰

Java迭代器Iterator

 之前我们实现了迭代器模式,很多编程语言实际上已经内置了迭代器类,比如Java就为我们实现了迭代器Iterator。我们首先来看Iterator中的源码。 通过...

264100
来自专栏数据结构与算法

2879 堆的判断

2879 堆的判断 时间限制: 1 s 空间限制: 32000 KB 题目等级 : 黄金 Gold 题目描述 Description 堆是一种常用...

32580
来自专栏老马说编程

(43) 剖析TreeMap / 计算机程序的思维逻辑

40节介绍了HashMap,我们提到,HashMap有一个重要局限,键值对之间没有特定的顺序,我们还提到,Map接口有另一个重要的实现类TreeMap,在Tre...

21880
来自专栏芋道源码1024

Jedis 对 Redis 的操作详解

本篇主要阐述Jedis对redis的五大类型的操作:字符串、列表、散列、集合、有序集合。

22130
来自专栏java系列博客

Java ConcurrentModificationException异常原因和解决方法

87120
来自专栏大闲人柴毛毛

剑指 offer代码解析——面试题26复杂链表的复制

本题详细解析均在代码注释中: /** * 题目:请复制一个复杂链表。每个结点除了有一个next指针指向下一个结点外,还有一个sibling指向链表中的任意一个...

29140

扫码关注云+社区

领取腾讯云代金券