304

分享到

C++高级数据结构之二叉查找树

2024-04-02 19:04:59 304人浏览薄情痞子

摘要

目录高级数据结构（Ⅳ）二叉查找树基础概念基本实现数据表示查找插入有序性相关的方法最小键和最大键向上取整和向下取整选择操作排名范围查找与删除相关的方法删除最小键删除最大键删除操作性能分

高级数据结构（Ⅳ）二叉查找树

基础概念

此数据结构由结点组成，结点包含的链接可以为空（null）或者指向其他结点。在二叉树中，每个结点只能有一个父结点（只有一个例外，也就是根结点，它没有父结点），而且每个结点都只有左右两个链接，分别指向自己的左子结点和右子结点。每个结点的两个链接都指向了一棵独立的子二叉树或空链接。在二叉查找树中，每个结点还包含了一个键和一个值，键之间也有顺序之分以支持高校的查找。

定义：一棵二叉查找树（BST）是一棵二叉树，
其中每个结点都含有一个Comparable的键（以及相关联的值）
且每个结点的键都大于其左子树中的任意结点的键而小于右子树的任意结点的键。

以int类型为键，string类型为值的二叉查找树的API如下：

class BST<Key extends Comparable<Key>, Value>
-------------------------------------------------------------------------------------
node root; 根结点
int size(Node x); 返回以结点x为根节点的子树大小
Value get(Key key) 返回键key对应的值
void put(Key key, Value val) 插入键值对{key : val}
Key min() 返回最小键
Key max() 返回最大键
Key floor(Key key) 向下取整（返回小于等于key的最大值）
Key ceiling(Key key) 向上取整（返回大于等于key的最小值）
Key select(int k) 返回排名为k的键
int rank(Key key) 返回键key的排名
Iterable<Key> keys(Key lo, Key hi) 返回查找（返回指定范围内的所有键值）
void deleteMin() 删除最小键
void deleteMax() 删除最大键
void delete (Key key) 删除键key

基本实现

数据表示

我们嵌套定义一个私有类来表示二叉查找树上的一个结点。每个结点都含有一个键、一个值、一条左链接、一条右链接和一个结点计数器。左链接指向一棵由小于该结点的所有键组成的二叉查找树，右链接指向一棵由大于该结点的所有键组成的二叉查找树。变量N给出了以该结点为根的子树的结点总数。

实现：

class BST<Key extends Comparable<Key>, Value> {
private Node root; //二叉查找树的根节点
private class Node{
private Key key; //键
private Value val; //值
private Node left, right; //指向子树的链接
private int N; //以该结点为根的子树中的结点总数
public Node(Key key, Value val, int N) {
this.key = key;
this.val = val;
this.N = N;
}
}
public int size() {
return size(root);
}
private int size(Node x) {
if (x == null) {
return 0;
} else {
return x.N;
}
}
}

一棵二叉查找树代表了一组键（及其相应的值）的集合，而同一个集合可以用多棵不同的二叉查找树表示。如果我们将一棵二叉查找树的所有键投影到一条直线上，保证一个结点的左子树中的键出现在它的左边，右子树中的键出现在它的右边，那么我们一定可以得到一条有序的键列。

查找

一般来说，在符号表中查找一个键可能得到两种结果。如果含有该键的结点存在于表中，我们的查找就命中了，然后返回相应的值。否则查找未命中（并返回null）。根据数据表示的递归结构我们马上就能得到，在二叉查找树中查找一个键的递归算法：如果树是空的，则查找未命中；如果被查找的键和根结点的键相等，查找命中，否则我们就（递归地）在适当的子树中继续查找。如果被查找的键较小就选择左子树，较大则选择右子树。


public Value get(Key key) {
return get(root, key);
}
private Value get(Node x, Key key) {
//在以x为根节点的子树中查找并返回key所对应的值
//如果找不到则返回null
if (x == null) {
return null;
}
int cmp = key.compareTo(x.key);
if (cmp < 0) {
return get(x.left, key);
} else if (cmp > 0) {
return get(x.right, key);
} else {
return x.val;
}
}

插入

二叉查找树插入的实现难度和查找差不多。如果树是空的，就返回一个含有该键值对的新结点；如果被查找的键小于根结点的键，继续在左子树中搜索插入该键，否则在右子树中插入该键。


public void put(Key key, Value val) {
//查找key，找到则更新它的值，否则为它创建一个新的结点
root = put(root, key, val);
}
private Node put(Node x, Key key, Value val) {
//如果key存在于以x为根结点的子树中则更新它的值；
//否则将以key和val为键值对的新结点插入到该子树中
if (x == null) {
return new Node(key, val, 1);
}
int cmp = key.compareTo(x.key);
if (cmp < 0) {
x.left = put(x.left, key, val);
} else if (cmp > 0) {
x.right = put(x.right, key, val);
} else {
x.val = val;
}
x.N = size(x.left) + size(x.right) + 1;
return x;
}

有序性相关的方法

二叉查找树得以广泛应用的一个重要原因就是它能够保持键的有序性，因此它可以作为实现有序符号表api中的众多方法的基础。这使得符号表的用例不仅能够通过键还能通过键的相对顺序来访问键值对。

最小键和最大键

如果根节点的左链接为空，那么一棵二叉查找树中最小的键就是根结点；如果左链接非空，那么树中的最小键就是左子树中的最小键，显示可以由递归操作实现。

找出最大键的方法也是类似的，只不过是变为查找右子树而已。

最小键


public Key min() {
if (root == null) {
return null;
}
return min(root).key;
}
private Node min(Node x) {
if (x.left == null) {
return x;
}
return min(x.left);
}

最大键


public Key max() {
if (root == null) {
return null;
}
return max(root).key;
}
private Node max(Node x) {
if (x.right == null) {
return x;
}
return max(x.right);
}

向上取整和向下取整

如果给定的键key小于二叉查找树的根结点的键，那么小于等于key的最大键floor(key)一定在根结点的左子树中；如果给定的键key大于二叉查找树的根结点，那么只有当根结点右子树中存在小于等于key的结点时，小于等于key的最大键才会出现在右子树中，否则根结点就是小于等于key的最大键。这段描述说明了floor()方法的递归实现，同时也递推地证明了它能够计算出预期的结果。将“左”变为“右”（同时将小于变为大于）就能够得到ceiling()的算法。

向下取整


public Key floor(Key key) {
Node x = floor(root, key);
if (x == null) {
return null;
}
return x.key;
}
private Node floor(Node x, Key key) {
if (x == null) {
return null;
}
int cmp = key.compareTo(x.key);
if (cmp == 0) {
return x;
}
if (cmp < 0) {
return floor(x.left, key);
}
Node t = floor(x.right, key);
if (t != null) {
return t;
} else {
return x;
}
}

向上取整


public Key ceiling(Key key) {
Node x = ceiling(root, key);
if (x == null) {
return null;
}
return x.key;
}
private Node ceiling(Node x, Key key) {
if (x == null) {
return null;
}
int cmp = key.compareTo(x.key);
if (cmp == 0) {
return x;
}
if (cmp > 0) {
return ceiling(x.right, key);
}
Node t = ceiling(x.left, key);
if (t != null) {
return t;
} else {
return x;
}
}

选择操作


public Key select(int k) {
if (root == null) {
return null;
}
return select(root, k).key;
}
private Node select(Node x, int k) {
//返回排名为k结点
if (x == null) {
return null;
}
//注：书中此处为int t = size(x.left);
//个人觉得此处应该加上当前结点,即+1（若有建议欢迎指正）
int t = size(x.left) + 1;
if (t > k) {
return select(x.left, k);
} else if (t < k) {
return select(x.right, k - t - 1);
} else {
return x;
}
}

二叉查找树的选择操作和基于切分的数组选择操作类似。我们在二叉查找树中的每个结点中维护的子树结点计数器变量N就是用来支持此操作的。

排名


public int rank(Key key) {
if (root == null) {
return 0;
}
return rank(root, key);
}
private int rank(Node x, Key key) {
//返回以x为根结点的子树中小于x.key的键的数量
if (x == null) {
return 0;
}
int cmp = key.compareTo(x.key);
if (cmp < 0) {
return rank(x.left, key);
} else if (cmp > 0) {
return 1 + size(x.left) + rank(x.right, key);
} else {
//若返回给定键的排名，我认为这里要+1，不然可以在上面调用后的return语句后+1
//书中此处为return size(x.left)（若有建议欢迎指正）;
return size(x.left) + 1;
}
}

rank()方法是select()方法的逆方法，它会返回给定键的排名。它的实现和select()类似：如果给定的键和根结点的键相等，我们返回左子树中的结点总数t；如果给定的键小于根结点，我们会返回该键在左子树中的排名（递归计算）；如果给定的键大于根结点，我们会返回t+1（根结点）加上它在右子树中的排名（递归计算）。

范围查找


public Iterable<Key> keys() {
return keys(min(), max());
}

public Iterable<Key> keys(Key lo, Key hi) {
Queue<Key> queue = new LinkedList<Key>();
keys(root, queue, lo, hi);
return queue;
}
private void keys(Node x, Queue<Key> queue, Key lo, Key hi) {
if (x == null) {
return;
}
int cmplo = lo.compareTo(x.key);
int cmphi = hi.compareTo(x.key);
if (cmplo < 0) {
keys(x.left, queue, lo, hi);
}
if (cmplo <= 0 && cmphi >= 0) {
queue.offer(x.key);
}
if (cmphi > 0) {
keys(x.right, queue, lo, hi);
}
}

要实现能够返回给定范围键的keys()方法，我们首先需要一个遍历二叉查找树的基本方法，为中序遍历。要说明这个方法，我们先看看如何能够将二叉查找树中的所有键按照顺序打印出来。要做到这一点，我们应该先打印出根结点的左子树中的所有键（根据二叉查找树的定义它们应该都小于根结点的键），然后打印出根结点的键，最后打印出根结点的右子树中的所有键（根据二叉查找树的定义它们应该都大于根结点的键）。

与删除相关的方法

删除最小键

二叉查找树中最难实现的方法就是delete()方法，即从符号表中删除一个键值对。在此之前，我们先考虑deleteMin()方法（删除最小键所对应的键值对）。对于deleteMin()，我们要不断深入根节点的左子树直至遇见一个空链接，然后将指向该结点的右子树（只需要在递归调用中返回它的右链接即可）。此时它会被垃圾收集器清理掉。我们给出的标准递归代码在删除结点后会正确地设置它的父结点的链接并更新它到根结点的路径上的所有结点的计数器的值。


public void deleteMin() {
if (root == null) {
return;
}
deleteMin(root);
}
private Node deleteMin(Node x) {
if (x.left == null) {
return x.right;
}
x.left = deleteMin(x.left);
x.N = size(x.left) + size(x.right) + 1;
return x;
}

删除最大键

deletemax()方法的实现和deletemin()完全类似，相应地，只需删除右子树最右端结点，然后返回其最右端结点的左子树即可。


public void deleteMax() {
if (root == null) {
return;
}
deleteMax(root);
}
private Node deleteMax(Node x) {
if (x.right == null) {
return x.left;
}
x.right = deleteMax(x.right);
x.N = size(x.left) + size(x.right) + 1;
return x;
}

删除操作

将指向即将被删除的结点的链接保存为t;
将x指向它的后继结点min(t.right);
将x的右链接（原本指向一棵所有结点都大于x.key的二叉查找树）指向deleteMin(t.right)，也就是在删除后所有结点仍然都大于x.key的子二叉查找树；
将x的左链接（本为空）设为t.left（其下所有的键都小于被删除的结点和它的后继结点）。

实现：


public void delete (Key key) {
root = delete(root, key);
}

private Node delete(Node x, Key key) {
if (x == null) {
return null;
}
int cmp = key.compareTo(x.key);
if (cmp < 0) {
x.left = delete(x.left, key);
} else if(cmp > 0) {
x.right = delete(x.right, key);
} else {
if (x.right == null) {
return x.left;
}
if (x.left == null) {
return x.right;
}
Node t = x;
x = min(t.right);
x.right = deleteMin(t.right);
x.left = t.left;
}
x.N = size(x.left) + size(x.right) + 1;
return x;
}

性能分析

我见过二叉查找树，但它的实现没有使用递归。这两种方式各有哪些优缺点？
答：一般来说，递归的实现更容易验证其正确性，而非递归的实现效率更高。

完整代码和测试

完整代码

class BST<Key extends Comparable<Key>, Value> {
private Node root; //二叉查找树的根节点
private class Node{
private Key key; //键
private Value val; //值
private Node left, right; //指向子树的链接
private int N; //以该结点为根的子树中的结点总数

public Node(Key key, Value val, int N) {
this.key = key;
this.val = val;
this.N = N;
}
}

public int size() {
return size(root);
}

private int size(Node x) {
if (x == null) {
return 0;
} else {
return x.N;
}
}


public Value get(Key key) {
return get(root, key);
}

private Value get(Node x, Key key) {
//在以x为根节点的子树中查找并返回key所对应的值
//如果找不到则返回null
if (x == null) {
return null;
}
int cmp = key.compareTo(x.key);
if (cmp < 0) {
return get(x.left, key);
} else if (cmp > 0) {
return get(x.right, key);
} else {
return x.val;
}
}


public void put(Key key, Value val) {
//查找key，找到则更新它的值，否则为它创建一个新的结点
root = put(root, key, val);
}

private Node put(Node x, Key key, Value val) {
//如果key存在于以x为根结点的子树中则更新它的值；
//否则将以key和val为键值对的新结点插入到该子树中
if (x == null) {
return new Node(key, val, 1);
}
int cmp = key.compareTo(x.key);
if (cmp < 0) {
x.left = put(x.left, key, val);
} else if (cmp > 0) {
x.right = put(x.right, key, val);
} else {
x.val = val;
}
x.N = size(x.left) + size(x.right) + 1;
return x;
}


public Key min() {
if (root == null) {
return null;
}
return min(root).key;
}

private Node min(Node x) {
if (x.left == null) {
return x;
}
return min(x.left);
}


public Key max() {
if (root == null) {
return null;
}
return max(root).key;
}

private Node max(Node x) {
if (x.right == null) {
return x;
}
return max(x.right);
}


public Key floor(Key key) {
Node x = floor(root, key);
if (x == null) {
return null;
}
return x.key;
}

private Node floor(Node x, Key key) {
if (x == null) {
return null;
}
int cmp = key.compareTo(x.key);
if (cmp == 0) {
return x;
}
if (cmp < 0) {
return floor(x.left, key);
}
Node t = floor(x.right, key);
if (t != null) {
return t;
} else {
return x;
}
}


public Key ceiling(Key key) {
Node x = ceiling(root, key);
if (x == null) {
return null;
}
return x.key;
}
private Node ceiling(Node x, Key key) {
if (x == null) {
return null;
}
int cmp = key.compareTo(x.key);
if (cmp == 0) {
return x;
}
if (cmp > 0) {
return ceiling(x.right, key);
}
Node t = ceiling(x.left, key);
if (t != null) {
return t;
} else {
return x;
}
}

public Key select(int k) {
if (root == null) {
return null;
}
return select(root, k).key;
}
private Node select(Node x, int k) {
//返回排名为k结点
if (x == null) {
return null;
}
int t = size(x.left) + 1;
if (t > k) {
return select(x.left, k);
} else if (t < k) {
return select(x.right, k - t - 1);
} else {
return x;
}
}

public int rank(Key key) {
if (root == null) {
return 0;
}
return rank(root, key);
}

private int rank(Node x, Key key) {
//返回以x为根结点的子树中小于x.key的键的数量
if (x == null) {
return 0;
}
int cmp = key.compareTo(x.key);
if (cmp < 0) {
return rank(x.left, key);
} else if (cmp > 0) {
return 1 + size(x.left) + rank(x.right, key);
} else {
return size(x.left) + 1;
}
}


public Iterable<Key> keys() {
return keys(min(), max());
}

public Iterable<Key> keys(Key lo, Key hi) {
Queue<Key> queue = new LinkedList<Key>();
keys(root, queue, lo, hi);
return queue;
}

private void keys(Node x, Queue<Key> queue, Key lo, Key hi) {
if (x == null) {
return;
}
int cmplo = lo.compareTo(x.key);
int cmphi = hi.compareTo(x.key);
if (cmplo < 0) {
keys(x.left, queue, lo, hi);
}
if (cmplo <= 0 && cmphi >= 0) {
queue.offer(x.key);
}
if (cmphi > 0) {
keys(x.right, queue, lo, hi);
}
}


public void deleteMin() {
if (root == null) {
return;
}
deleteMin(root);
}

private Node deleteMin(Node x) {
if (x.left == null) {
return x.right;
}
x.left = deleteMin(x.left);
x.N = size(x.left) + size(x.right) + 1;
return x;
}

public void deleteMax() {
if (root == null) {
return;
}
deleteMax(root);
}
private Node deleteMax(Node x) {
if (x.right == null) {
return x.left;
}
x.right = deleteMax(x.right);
x.N = size(x.left) + size(x.right) + 1;
return x;
}


public void delete (Key key) {
root = delete(root, key);
}

private Node delete(Node x, Key key) {
if (x == null) {
return null;
}
int cmp = key.compareTo(x.key);
if (cmp < 0) {
x.left = delete(x.left, key);
} else if(cmp > 0) {
x.right = delete(x.right, key);
} else {
if (x.right == null) {
return x.left;
}
if (x.left == null) {
return x.right;
}
Node t = x;
x = min(t.right);
x.right = deleteMin(t.right);
x.left = t.left;
}
x.N = size(x.left) + size(x.right) + 1;
return x;
}
}

测试

int[] keys = {6, 5, 1, 3, 2, 4, 9, 7, 8, 10};
String[] values = {"F", "E", "A", "C", "B", "D", "I", "G", "H", "J"};

public class BSTTest {
public static void main(String[] args) {
int[] keys = {6, 5, 1, 3, 2, 4, 9, 7, 8, 10};
String[] values = {"F", "E", "A", "C", "B", "D", "I", "G", "H", "J"};

BST<Integer, String> bst = new BST<Integer, String>();
//构建树
for (int i = 0; i < keys.length; i++) {
bst.put(keys[i], values[i]);
}

System.out.println("创建树的键为：");
LinkedList<Integer> queue = (LinkedList<Integer>) bst.keys();
while (!queue.isEmpty()) {
System.out.print(queue.poll() + " ");
}

System.out.println("\n创建树的大小为：" + bst.size());
System.out.println("键3所对应的值为：" + bst.get(3));
System.out.println("最小键为：" + bst.min());
System.out.println("最大键为: " + bst.max());
System.out.println("小于等于11的最大键是：" + bst.floor(11));
System.out.println("大于等于0的最小键是: " + bst.ceiling(0));
System.out.println("排名为5的键是：" + bst.select(5));
System.out.println("键7的排名是：" + bst.rank(7));

System.out.println("\n键值在3-8之间的键有：");
LinkedList<Integer> queue1 = (LinkedList<Integer>) bst.keys(3, 8);
while (!queue1.isEmpty()) {
System.out.print(queue1.poll() + " ");
}
System.out.println("\n删除最小键和最大键后的键值为：");
bst.deleteMin();
bst.deleteMax();
LinkedList<Integer> queue2 = (LinkedList<Integer>) bst.keys();
while (!queue2.isEmpty()) {
System.out.print(queue2.poll() + " ");
}
System.out.println("\n删除键4后的键值为： ");
bst.delete(4);
LinkedList<Integer> queue3 = (LinkedList<Integer>) bst.keys();
while (!queue3.isEmpty()) {
System.out.print(queue3.poll() + " ");
}
}
}

创建树的键为：
1 2 3 4 5 6 7 8 9 10
创建树的大小为：10
键3所对应的值为：C
最小键为：1
最大键为: 10
小于等于11的最大键是：10
大于等于0的最小键是: 1
排名为5的键是：5
键7的排名是：7
键值在3-8之间的键有：
3 4 5 6 7 8
删除最小键和最大键后的键值为：
2 3 4 5 6 7 8 9
删除键4后的键值为：
2 3 5 6 7 8 9
Process finished with exit code 0

到此这篇关于c++高级数据结构之二叉查找树的文章就介绍到这了,更多相关C++二叉查找树内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: C++高级数据结构之二叉查找树

本文链接: https://www.lsjlt.com/news/149531.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档

去做题

猜你喜欢

C++高级数据结构之二叉查找树

目录高级数据结构（Ⅳ）二叉查找树基础概念基本实现数据表示查找插入有序性相关的方法最小键和最大键向上取整和向下取整选择操作排名范围查找与删除相关的方法删除最小键删除最大键删除操作性能分...

99+

2024-04-02
C++高级数据结构之二叉查找树怎么实现

本文小编为大家详细介绍“C++高级数据结构之二叉查找树怎么实现”，内容详细，步骤清晰，细节处理妥当，希望这篇“C++高级数据结构之二叉查找树怎么实现”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。高级数据结构（Ⅳ）...

99+

2023-06-30
Java数据结构之二叉查找树的实现

目录定义节点结构查找算法插入算法删除算法完整代码定义二叉查找树（亦称二叉搜索树、二叉排序树）是一棵二叉树，且各结点关键词互异，其中根序列按其关键词递增排列。等价描述：二叉查找树中...

99+

2024-04-02
数据结构TypeScript之二叉查找树实现详解

目录树的结构特点面向对象方法封装二叉查找树（迭代版）二叉查找树的定义构造函数基本单元：二叉查找树节点主体：二叉查找树增加节点查找节点删除节点二叉树的遍历树的结构特点树是一种有层次...

99+

2023-01-30

TypeScript数据结构二叉查找树 TypeScript数据结构
C语言数据结构之二叉树详解

目录1. 树概念及结构1.1树概念1.2树的表示2. 二叉树概念及结构2.1概念2.2数据结构中的二叉树2.3特殊的二叉树2.4二叉树的存储结构2.5二叉树的性质3. 二叉树顺序结构...

99+

2024-04-02
C语言数据结构之二叉链表创建二叉树

目录一、思想（先序思想创建）二、创建二叉树(1)传一级参数方法(2)传二级参数方法一、思想（先序思想创建）第一步先创建根节点,然后创建根节点左子树,开始递归创建左子树，直到递归创建...

99+

2024-04-02
Go 数据结构之二叉树详情

目录Go 语言实现二叉树定义二叉树的结构二叉树遍历创建二叉树插入值测试前言：树可以有许多不同的形状，并且它们可以在每个节点允许的子节点数量或它们在节点内组织数据值的方式上有所不同。...

99+

2024-04-02
Java数据结构学习之二叉树

一、背景知识：树（Tree）在之前的笔记中，我们介绍的链表、栈、队列、数组和字符串都是以线性结构来组织数据的。本篇笔记要介绍的树采用的是树状结构，这是一种非线性的数据组织形式。树...

99+

2024-04-02
java数据结构之搜索二叉树

本文实例为大家分享了java数据结构之搜索二叉树的具体代码，供大家参考，具体内容如下搜索二叉树的定义是：在一个二叉树上，左节点一定比父节点小，右节点一定比父节点大，其他定义跟二叉树...

99+

2024-04-02
C++数据结构之搜索二叉树的实现

目录零.前言1.概念2.作用3.迭代实现(1)查找(2)插入(3)删除4.递归实现(1)查找(2)插入(3)删除5.key/value模型的应用(1)对应查找(2)判断出现次数6.总...

99+

2024-04-02
C++高级数据结构之线段树

目录前言：高级数据结构（Ⅲ）线段树（Segment Tree）线段树的原理树的创建单点修改区间查找完整代码及测试前言：高级数据结构（Ⅲ）线段树（Segment Tree）线段树的原...

99+

2024-04-02
【Java 数据结构】树和二叉树

篮球哥温馨提示：编程的同时不要忘记锻炼哦！一棵倒立过来的树. 目录 1、什么是树？ 1.1 简单认识树 1.2 树的概念 1.3 树的表示形式 2、二叉树 2.1 二叉树的概念 2.2 特殊的二叉树...

99+

2023-09-17

算法数据结构
数据结构之链式二叉树详解

目录🍏1.二叉树的遍历🍏1.1前序遍历1.2中序遍历1.3后序遍历1.4层次遍历 🍎2.链式二叉树的实现🍎2.1二叉树的创建2.2前序遍历2.3中序遍历2.4后序遍历2.5...

99+

2023-05-16

C语言链式二叉树数据结构链式二叉树 C语言数据结构
Python数据结构之二叉排序树的定义、查找、插入、构造、删除

前言本篇章主要介绍二叉树的应用之一------二叉排序树，包括二叉排序树的定义、查找、插入、构造、删除及查找效率分析。 1. 二叉排序树的定义 Q...

99+

2024-04-02
C#实现二叉查找树

目录1.实现API1.数据结构2.查找3.插入4.分析有序性相关的方法和删除操作1.最大键和最小键2.向上取整和向下取整3.选择操作4.排名5.删除最大键和删除最小键6.删除操作7....

99+

2024-04-02
C++数据结构之二叉搜索树的实现详解

目录前言介绍实现节点的实现二叉搜索树的查找二叉搜索树的插入二叉搜索树的删除总结前言今天我们来学一个新的数据结构：二叉搜索树。介绍二叉搜索树也称作二叉排序树，它具有以下性质：非...

99+

2024-04-02
详解Java数据结构之平衡二叉树

目录什么是二叉搜索树平衡二叉搜索树平衡二叉搜索树建树程序计算每个节点的高度计算每个节点的平衡因子合并二叉树旋转调整函数整体代码什么是二叉搜索树简单来说，就是方便搜索的二叉树，是一种...

99+

2024-04-02
Java数据结构之二叉搜索树详解

目录前言性质实现节点结构初始化插入节点查找节点删除节点最后前言今天leetcode的每日一题450是关于删除二叉搜索树节点的，题目要求删除指定值的节点，并且需要保证二叉搜索树性质不...

99+

2024-04-02
C语言数据结构系列篇二叉树的概念及满二叉树与完全二叉树

链接：C语言数据结构系列之树的概念结构和常见表示方法 0x00 概念定义：二叉树既然叫二叉树，顾名思义即度最大为2的树称为二叉树。它的度可以为 1 也可...

99+

2024-04-02
C++高级数据结构之并查集

目录1.动态连通性2.union-find算法API3.quick-find算法4.quick-union算法5.加权quick-union算法6.使用...

99+

2024-04-02