二叉搜索树 Rust实现

二叉搜索树

  • 二叉搜索树是一颗二叉树
  • 每个节点应该包含三个属性 left, right, p, 根节点pNIL
  • 设x是二叉搜索树的一个节点, y是x左子树的一个节点, 那么y.key <= x.key, 若y是x右子树的一个节点, 那么y.key >= x.key

遍历

遍历分前中后, 以根节点的遍历顺序而划分

之前写过一篇二叉搜索树的, 用C语言实现, 可以参考一下C语言实现
感受一下区别

以下是代码, 来源于RustPrimer

type TreeNode<K, V> = Option<Box<Node<K, V>>>;
#[derive(Debug)]
struct Node<K, V: std::fmt::Display> {
    left: TreeNode<K, V>,
    right: TreeNode<K, V>,
    key: K,
    value: V,
}
trait BinaryTree<K, V> {
    fn pre_order(&self);
    fn in_order(&self);
    fn pos_order(&self);
}
trait BinarySearchTree<K: PartialOrd, V>: BinaryTree<K, V> {
    fn insert(&mut self, key: K, value: V);
}
impl<K, V: std::fmt::Display> Node<K, V> {
    fn new(key: K, value: V) -> Self {
        Node {
            left: None,
            right: None,
            value: value,
            key: key,
        }
    }
}
impl<K: PartialOrd, V: std::fmt::Display> BinarySearchTree<K, V> for Node<K, V> {
    fn insert(&mut self, key: K, value: V) {
        if self.key < key {
            if let Some(ref mut right) = self.right {
                right.insert(key, value);
            } else {
                self.right = Some(Box::new(Node::new(key, value)));
            }
        } else {
            if let Some(ref mut left) = self.left {
                left.insert(key, value);
            } else {
                self.left = Some(Box::new(Node::new(key, value)));
            }
        }
    }
}
impl<K, V: std::fmt::Display> BinaryTree<K, V> for Node<K, V> {
    fn pre_order(&self) {
        println!("{}", self.value);

        if let Some(ref left) = self.left {
            left.pre_order();
        }
        if let Some(ref right) = self.right {
            right.pre_order();
        }
    }

    fn in_order(&self) {
        if let Some(ref left) = self.left {
            left.in_order();
        }
        println!("{}", self.value);
        if let Some(ref right) = self.right {
            right.in_order();
        }
    }
    fn pos_order(&self) {
        if let Some(ref left) = self.left {
            left.pos_order();
        }
        if let Some(ref right) = self.right {
            right.pos_order();
        }
        println!("{}", self.value);
    }
}

type BST<K, V> = Node<K, V>;

fn test_insert() {
    let mut root = BST::<i32, i32>::new(3, 4);
    root.insert(2, 3);
    root.insert(4, 6);
    root.insert(5, 5);
    root.insert(6, 6);
    root.insert(1, 8);
    if let Some(ref left) = root.left {
        assert_eq!(left.value, 3);
    }

    if let Some(ref right) = root.right {
        assert_eq!(right.value, 6);
        if let Some(ref right) = right.right {
            assert_eq!(right.value, 5);
        }
    }
    println!("Pre Order traversal");
    root.pre_order();
    println!("In Order traversal");
    root.in_order();
    println!("Pos Order traversal");
    root.pos_order();
}

fn main() {
    test_insert();
}

原文地址:https://www.cnblogs.com/kwebi/p/9649462.html

时间: 09-14

二叉搜索树 Rust实现的相关文章

用JS实现二叉搜索树

二叉树的节点最多只能有两个子节点,一个左侧子节点,一个右侧子节点. 二叉搜索树(BST),是二叉树的一种,但只允许在左侧节点存储比父节点小的值,在右侧节点存储比父节点大或等于父节点的值. 1.创建BST 1.1创建BST类 首先申明BST类的基本结构 function BinarySearchTree() { var Node = function(key){ this.key = key; this.left = null; this.right = null; }; var root = n

538. Convert BST to Greater Tree 二叉搜索树转换为更大树

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST. Example: Input: The root of a Binary Search Tree like thi

二叉搜索树

#include<stdio.h> #include<iostream> #include<math.h> #include<stdlib.h> using namespace std; struct TreeNode { TreeNode* p; TreeNode* l; TreeNode* r; int key; TreeNode() { p = 0; l = 0; r = 0; key = -1; } }; const int RANDMOD = 30

04-树4 是否同一棵二叉搜索树

给定一个插入序列就可以唯一确定一棵二叉搜索树.然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到.例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树,都得到一样的结果.于是对于输入的各种插入序列,你需要判断它们是否能生成一样的二叉搜索树. 输入格式: 输入包含若干组测试数据.每组数据的第1行给出两个正整数N (≤10)和L,分别是每个序列插入元素的个数和需要检查的序列个数.第2行给出N个以空格分隔的正整数,作为初始插入序列.最后L行,每行给出N个插入的元素,属于

二叉搜索树建立、插入、删除、前继节点、后继节点之c++实现

一.前言 一直以来,都对树有关的东西望而却步.以前每次说要看一看,都因为惰性,时间就那么荒废掉了.今天下个决心,决定好好的数据结构中的东西看一下.不知道看这篇文章的你,是不是和我有同样的感受,空有一颗努力的心,却迟迟没有付出行动.如果是的话,如果也想好好的把树的知识巩固一下的话,就让我们一起好好儿地把知识点过一遍吧.本文争取让看完的每一个没有基础的同学,都能有所收获.在正文开始前,先给自己加个油.加油(^ω^) 二.二叉搜索树的定义 二叉搜索树是指,对于某一个节点而言,它左边的节点都小于或等于它

剑指offer:二叉搜索树与双向链表

1.题目描述: 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表.要求不能创建任何新的结点,只能调整树中结点指针的指向. 2.解题思路: (1)将左子树构造成双向链表,并返回链表头节点: (2)定位左子树双链表的尾节点: (3)如果左子树链表不为空,将当前root连缀其链尾: (4)将右子树构造出双向链表,并返回链表头节点: (5)如果右子树链表不为空,将当前root连缀其表头: (6)根据左子树链表是否为空,确定返回的节点. 3.JavaScript实现: function Conv

数据结构——二叉搜索树、B树、B-树

数据结构——二叉搜索树.B树.B-树 1. 综述 二叉排序树(Binary Sort Tree),又叫二叉查找树(Binary Search Tree),也叫二叉排序树. 二叉搜索树满足以下性质: 1. 若根节点左子树不为空,则左子树上的所有节点均小于根节点: 2. 若根节点右子树不为空,则右子树上的所有节点均大于根节点: 3. 其左右子树也是二叉搜索树(递归定义): 4. 没有键值相等的点. B树就是B-树.B树/B-树英文叫B-Tree,可能被不小心翻译成了B-树.

PAT天梯赛练习题 L3-010. 是否完全二叉搜索树(完全二叉树的判断)

L3-010. 是否完全二叉搜索树 时间限制 400 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 作者 陈越 将一系列给定数字顺序插入一个初始为空的二叉搜索树(定义为左子树键值大,右子树键值小),你需要判断最后的树是否一棵完全二叉树,并且给出其层序遍历的结果. 输入格式: 输入第一行给出一个不超过20的正整数N:第二行给出N个互不相同的正整数,其间以空格分隔. 输出格式: 将输入的N个正整数顺序插入一个初始为空的二叉搜索树.在第一行中输出结果树的层序

Java数据结构之二叉搜索树

Java数据结构之二叉搜索树 1.二叉搜索树组成 二叉搜索树又称为二叉排序树,它或者是一颗空树,或者是一颗具有如下特性的非空二叉树,需要满足一下三个条件: (1)若它的左子树非空,则左子树上所有结点的关键字均小于根结点的关键字: (2)若它的右子树非空,则右子树上所有结点的关键字均大于(可以等于)根结点的关键字. (3)左子树右子树本身又各是一颗二叉搜索树 在算法描述中,均以结点值的比较来代表其关键字的比较,因为若结点的值为类类型时,该类必须实现系统提供的java.lang.comparable

二叉搜索树与双向链表

void convertNode(BSTreeNode *root, BSTreeNode ** pLastNodeInList) { if(!root) return ; if(root->left) { convertNode(root->left, pLastNodeInList); } root->left = *pLastNodeInList; if(*pLastNodeInList != NULL) (*pLastNodeInList)->right = root; *