二叉搜索树

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

遍历

``````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();
}
``````

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

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

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

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; *