二叉查找树和递归
递归 编程语言中把自己调用自己的函数，称为递归函数。 递归函数必须满足两个条件： 1.在每一次调用自己时，必须是更接近解（将原问题转化为更小的子问题）。 2.必须有一个递归的终止条件（最小的子问题的解，一般能一眼看出）。
递归函数就是调用自己不断深入，直到满足条件再返回一步步执行。 
//计算n的阶乘
public static int Func(int n)
{
if (n == 1) return 1; //递归终止条件（直到最小的子问题，得到解）
else return n * Func(n - 1); //递推公式（将原问题转化为更小的子问题进行求解）
}
//设计递归函数思路
//1.明确函数的功能语义：
//Func（n）对应的功能为：求解n的阶乘。之后求n-1的阶乘就可以调用此函数了。
//2.寻找原问题与子问题的关系：
//我们以Func（n）表示n的阶乘，显然当 n > 1 时都满足 Func（n）=n*Func（n-1）
//3.寻找递归终止条件：
//当n==1时 不满足递推公式，递归终止，得到最小子问题的解 即 Func（1）= 1
//例如，求解Func（3）
//Func（3）= 3 *Func（2）
//Func（2）= 2 *Func（1）
//Func（1）= 1
//递归：由上往下为递、由下往上是归
//递：将原问题拆成最小的子问题进行求解
//我想要求解到（原问题）3的阶乘，那么我就必须先求解到（更小子问题）2的阶乘
//我想要求解到（更小子问题）2的阶乘，那么我就必须先求解到（最小子问题）1的阶乘。
//归：通过最小子问题的解往回得到原问题的解
//当求解到了（最小子问题）1的阶乘的结果，再返回上一层函数的调用
//进而求解到（更小子问题）2的阶乘的结果，再返回上一层函数的调用
//从而得到（原问题）3的阶乘的结果
二叉查找树 （Binary Search Tree(BST)） 
二叉树代码
class BST1 where E:IComparable
{
private class Node
{
public E e;
public Node left;
public Node right;
public Node(E e)
{
this.e = e;
left = null;
right = null;
}
}
private Node root;
private int N;
public BST1()
{
root = null;
N = 0;
}
public int Count { get { return N; } }
public bool IsEmpty { get { return N == 0; } }
//往二叉查找树中添加元素，非递归实现
public void add(E e)
{
if (root == null)
{
root = new Node(e);
N++;
return;
}
Node pre = null;
Node cur = root;
while (cur != null)
{
if (e.CompareTo(cur.e) == 0)
return;
pre = cur;
if (e.CompareTo(cur.e) 0
cur = cur.right;
}
cur = new Node(e);
if (e.CompareTo(pre.e) 0
pre.right = cur;
N++;
}
//往二叉查找树中添加元素，递归实现
public void Add(E e)
{
root=Add(root, e);
}
//以node为根的树中添加元素e，添加后返回根节点node
private Node Add(Node node,E e)
{
if (node == null)
{
N++;
return new Node(e);
}
if (e.CompareTo(node.e) 0)
node.right=Add(node.right, e);
return node;
}
//查询二叉查找树是否包含元素e
public bool Contains(E e)
{
return Contains(root, e);
}
//以node为根的树是否包含元素e
private bool Contains(Node node,E e)
{
if (node == null)
return false;
if (e.CompareTo(node.e) == 0)
return true;
else if (e.CompareTo(node.e) 0
return Contains(node.right, e);
}
// 二叉查找树的前序遍历
public void PreOrder()
{
PreOrder(root);
}
// 前序遍历以node为根的二叉查找树
private void PreOrder(Node node)
{
if (node == null)
return;
Console.WriteLine(node.e);
PreOrder(node.left);
PreOrder(node.right);
}
// 二叉查找树的中序遍历
public void InOrder()
{
InOrder(root);
}
//中序遍历以node为根的二叉查找树
private void InOrder(Node node)
{
if (node == null)
return;
InOrder(node.left);
Console.WriteLine(node.e);
InOrder(node.right);
}
// 二叉查找树的后序遍历
public void PostOrder()
{
PostOrder(root);
}
// 后序遍历以node为根的二叉查找树
private void PostOrder(Node node)
{
if (node == null)
return;
PostOrder(node.left);
PostOrder(node.right);
Console.WriteLine(node.e);
}
// 二叉查找树的层序遍历
public void LevelOrder()
{
Queue q = new Queue();
q.Enqueue(root);
while (q.Count != 0)
{
Node cur = q.Dequeue();
Console.WriteLine(cur.e);
if (cur.left != null)
q.Enqueue(cur.left);
if (cur.right != null)
q.Enqueue(cur.right);
}
}
// 寻找二叉查找树的最小元素
public E Min()
{
if (IsEmpty)
throw new ArgumentException("空树！");
return Min(root).e;
}
// 返回以node为根的二叉查找树的最小值所在的节点
private Node Min(Node node)
{
if (node.left == null)
return node;
return Min(node.left);
}
// 寻找二叉查找树的最大元素
public E Max()
{
if (IsEmpty)
throw new ArgumentException("空树！");
return Max(root).e;
}
// 返回以node为根的二叉查找树的最大值所在的节点
private Node Max(Node node)
{
if (node.right == null)
return node;
return Max(node.right);
}
// 从二叉查找树中删除最小值所在节点
public E RemoveMin()
{
E ret = Min();
root=RemoveMin(root);
return ret;
}
// 删除掉以node为根的二叉查找树中的最小节点
// 返回删除节点后新的二叉查找树的根
private Node RemoveMin(Node node)
{
if (node.left == null)
{
N--;
return node.right;
}
node.left=RemoveMin(node.left);
return node;
}
// 从二叉查找树中删除最大值所在节点
public E RemoveMax()
{
E ret = Max();
root = RemoveMax(root);
return ret;
}
// 删除掉以node为根的二叉查找树中的最大节点
// 返回删除节点后新的二叉查找树的根
private Node RemoveMax(Node node)
{
if (node.right == null)
{
N--;
return node.left;
}
node.right = RemoveMax(node.right);
return node;
}
// 从二叉查找树中删除元素为e的节点
public void Remove(E e)
{
root=Remove(root, e);
}
// 删除掉以node为根的二叉查找树中值为e的节点
// 返回删除节点后新的二叉查找树的根
private Node Remove(Node node, E e)
{
if (node == null) return null;
if (e.CompareTo(node.e) 0)
{
node.right=Remove(node.right, e);
return node;
}
else //e.CompareTo(node.e) == 0
{
// 要删除的节点只有左孩子
if (node.right == null)
{
N--;
return node.left;
}
// 要删除的节点只有右孩子
if (node.left == null)
{
N--;
return node.right;
}
// 要删除的节点左右都有孩子
// 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
// 用这个节点顶替待删除节点的位置
Node s=Min(node.right);
s.right=RemoveMin(node.right);
s.left = node.left;
return s;
}
}
//二叉树的最大高度
public int MaxHeight()
{
return MaxHeight(root);
}
//计算以node为根的二叉树的最大高度
private int MaxHeight(Node node)
{
if (node == null) return 0;
//int l = MaxHeight(node.left);
//int r = MaxHeight(node.right);
//return Math.Max(l, r) + 1;
//选择左右子树中最高的那一颗子树在加上node本身的高度。得到以node为根二叉树的最大高度
return Math.Max(MaxHeight(node.left), MaxHeight(node.right)) + 1;
}
}
性能分析 
基于二叉查找树实现集合
class BST1Set:ISet where E:IComparable
{
private BST1 bst;
public BST1Set()
{
bst = new BST1();
}
public int Count { get { return bst.Count; } }
public bool IsEmpty { get { return bst.IsEmpty; } }
public void Add(E e)
{
bst.Add(e);
}
public bool Contains(E e)
{
return bst.Contains(e);
}
public void Remove(E e)
{
bst.Remove(e);
}
public int MaxHeight()
{
return bst.MaxHeight();
}
}
基于二叉查找树实现映射
class BST2 where Key : IComparable
{
private class Node
{
public Key key;
public Value value;
public Node left;
public Node right;
public Node(Key key,Value value)
{
this.key = key;
this.value = value;
left = null;
right = null;
}
}
private Node root;
private int N;
public BST2()
{
root = null;
N = 0;
}
public int Count { get { return N; } }
public bool IsEmpty { get { return N == 0; } }
public void Add(Key key,Value value)
{
root = Add(root, key,value);
}
private Node Add(Node node, Key key,Value value)
{
if (node == null)
{
N++;
return new Node(key,value);
}
if (key.CompareTo(node.key) 0)
node.right = Add(node.right, key, value);
else
node.value = value;
return node;
}
private Node Min(Node node)
{
if (node.left == null)
return node;
return Min(node.left);
}
private Node RemoveMin(Node node)
{
if (node.left == null)
{
N--;
return node.right;
}
node.left = RemoveMin(node.left);
return node;
}
public void Remove(Key key)
{
root = Remove(root, key);
}
private Node Remove(Node node, Key key)
{
if (node == null) return null;
if (key.CompareTo(node.key) 0)
{
node.right = Remove(node.right, key);
return node;
}
else //e.CompareTo(node.e) == 0
{
// 要删除的节点只有左孩子
if (node.right == null)
{
N--;
return node.left;
}
// 要删除的节点只有右孩子
if (node.left == null)
{
N--;
return node.right;
}
// 要删除的节点左右都有孩子
Node s = Min(node.right);
s.right = RemoveMin(node.right);
s.left = node.left;
return s;
}
}
//返回以node为根节点的二叉查找树中，key所在的节点
private Node GetNode(Node node,Key key)
{
if (node == null) return null;
if (key.Equals(node.key))
return node;
else if (key.CompareTo(node.key) 0
return GetNode(node.right, key);
}
public bool Contains(Key key)
{
return GetNode(root, key) != null;
}
public Value Get(Key key)
{
Node node = GetNode(root, key);
if (node == null)
throw new ArgumentException("键" + key + "不存在，无法获取对应值");
else
return node.value;
}
public void Set(Key key,Value newValue)
{
Node node = GetNode(root, key);
if (node == null)
throw new ArgumentException("键" + key + "不存在，无法更改对应值");
else
node.value = newValue;
}
}
class BST2Dictionary:IDictionary where Key:IComparable
{
private BST2 bst;
public BST2Dictionary()
{
bst = new BST2();
}
public int Count { get { return bst.Count; } }
public bool IsEmpty { get { return bst.IsEmpty; } }
public void Add(Key key, Value value)
{
bst.Add(key, value);
}
public bool ContainsKey(Key key)
{
return bst.Contains(key);
}
public Value Get(Key key)
{
return bst.Get(key);
}
public void Remove(Key key)
{
bst.Remove(key);
}
public void Set(Key key, Value newValue)
{
bst.Set(key, newValue);
}
}
2-3查找树 
红黑树
红黑树代码
class RBT1 where E : IComparable
{
private const bool Red = true;
private const bool Black = false;
private class Node
{
public E e;
public Node left;
public Node right;
public bool color;
public Node(E e)
{
this.e = e;
left = null;
right = null;
color = Red;
}
}
private Node root;
private int N;
public RBT1()
{
root = null;
N = 0;
}
public int Count { get { return N; } }
public bool IsEmpty { get { return N == 0; } }
//判断节点是否为红色
private bool IsRed(Node node)
{
if (node == null)
return Black;
return node.color;
}
// node x
// / \ 左旋转 / \
// T1 x ---------> node T3
// / \ / \
// T2 T3 T1 T2
//返回左旋转后新的二叉查找树的根，对新的二叉查找树进行后续的修复操作
//左旋转过程中保证二叉树的性质，左子树都比根节点小，右子树都比根节点大
private Node LeftRotate(Node node)
{
Node x = node.right;
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = Red;
return x;
}
//颜色翻转
private void FlipColors(Node node)
{
node.color = Red;
node.left.color = Black;
node.right.color = Black;
}
// node x
// / \ 右旋转 / \
// x T2 -------> T3 node
// / \ / \
// T3 T1 T1 T2
//返回右旋转后新的二叉查找树的根，对新的二叉查找树进行后续的修复操作
//右旋转过程中保证二叉树的性质，左子树都比根节点小，右子树都比根节点大
private Node RightRoatate(Node node)
{
Node x = node.left;
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = Red;
return x;
}
//往红黑树中添加元素，递归实现
public void Add(E e)
{
root = Add(root, e);
root.color = Black;
}
//以node为根的树中添加元素e，添加后返回根节点node
private Node Add(Node node, E e)
{
if (node == null)
{
N++;
return new Node(e); //默认为红结点
}
if (e.CompareTo(node.e) 0)
node.right = Add(node.right, e);
//如果出现右子结点是红色，而左子结点是黑色，进行左旋转
if (IsRed(node.right) && !IsRed(node.left))
node=LeftRotate(node);
//如果出现连续的左子结点都为红色，进行右旋转
if (IsRed(node.left) && IsRed(node.left.left))
node=RightRoatate(node);
//如果出现左右子结点均为红色，进行颜色翻转
if (IsRed(node.left) && IsRed(node.right))
FlipColors(node);
return node;
}
//查询红黑树是否包含元素e
public bool Contains(E e)
{
return Contains(root, e);
}
//以node为根的树是否包含元素e
private bool Contains(Node node, E e)
{
if (node == null)
return false;
if (e.CompareTo(node.e) == 0)
return true;
else if (e.CompareTo(node.e) 0
return Contains(node.right, e);
}
//红黑树的最大高度
public int MaxHeight()
{
return MaxHeight(root);
}
//计算以node为根的红黑树的最大高度
private int MaxHeight(Node node)
{
if (node == null) return 0;
//int l = MaxHeight(node.left);
//int r = MaxHeight(node.right);
//return Math.Max(l, r) + 1;
//选择左右子树中最高的那一颗子树在加上node本身的高度。得到以node为根二叉树的最大高度
return Math.Max(MaxHeight(node.left), MaxHeight(node.right)) + 1;
}
}
基于红黑树实现集合
class RBT1Set:ISet where E:IComparable
{
private RBT1 rbt;
public RBT1Set()
{
rbt = new RBT1();
}
public int Count { get { return rbt.Count; } }
public bool IsEmpty { get { return rbt.IsEmpty; } }
public void Add(E e)
{
rbt.Add(e);
}
public bool Contains(E e)
{
return rbt.Contains(e);
}
public void Remove(E e)
{
Console.WriteLine("待实现");
}
public int MaxHeight()
{
return rbt.MaxHeight();
}
}
基于红黑树实现映射
class RBT2 where Key : IComparable
{
private const bool Red = true;
private const bool Black = false;
private class Node
{
public Key key;
public Value value;
public Node left;
public Node right;
public bool color;
public Node(Key key,Value value)
{
this.key = key;
this.value = value;
left = null;
right = null;
color = Red;
}
}
private Node root;
private int N;
public RBT2()
{
root = null;
N = 0;
}
public int Count { get { return N; } }
public bool IsEmpty { get { return N == 0; } }
//判断节点是否为红色
private bool IsRed(Node node)
{
if (node == null)
return Black;
return node.color;
}
// node x
// / \ 左旋转 / \
// T1 x ---------> node T3
// / \ / \
// T2 T3 T1 T2
//返回左旋转后新的二叉查找树的根，对新的二叉查找树进行后续的修复操作
//左旋转过程中保证二叉树的性质，左子树都比根节点小，右子树都比根节点大
private Node LeftRotate(Node node)
{
Node x = node.right;
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = Red;
return x;
}
//颜色翻转
private void FlipColors(Node node)
{
node.color = Red;
node.left.color = Black;
node.right.color = Black;
}
// node x
// / \ 右旋转 / \
// x T2 -------> T3 node
// / \ / \
// T3 T1 T1 T2
//返回右旋转后新的二叉查找树的根，对新的二叉查找树进行后续的修复操作
//右旋转过程中保证二叉树的性质，左子树都比根节点小，右子树都比根节点大
private Node RightRoatate(Node node)
{
Node x = node.left;
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = Red;
return x;
}
//往红黑树中添加元素，递归实现
public void Add(Key key,Value value)
{
root = Add(root, key,value);
root.color = Black;
}
//以node为根的树中添加元素e，添加后返回根节点node
private Node Add(Node node, Key key,Value value)
{
if (node == null)
{
N++;
return new Node(key,value); //默认为红结点
}
if (key.CompareTo(node.key) 0)
node.right = Add(node.right, key, value);
else //key.CompareTo(node.key) == 0
node.value = value;
//如果出现右子结点是红色，而左子结点是黑色，进行左旋转
if (IsRed(node.right) && !IsRed(node.left))
node = LeftRotate(node);
//如果出现连续的左子结点都为红色，进行右旋转
if (IsRed(node.left) && IsRed(node.left.left))
node = RightRoatate(node);
//如果出现左右子结点均为红色，进行颜色翻转
if (IsRed(node.left) && IsRed(node.right))
FlipColors(node);
return node;
}
private Node GetNode(Node node, Key key)
{
if (node == null) return null;
if (key.Equals(node.key))
return node;
else if (key.CompareTo(node.key) 0
return GetNode(node.right, key);
}
public bool Contains(Key key)
{
return GetNode(root, key) != null;
}
public Value Get(Key key)
{
Node node = GetNode(root, key);
if (node == null)
throw new ArgumentException("键" + key + "不存在，无法获取对应值");
else
return node.value;
}
public void Set(Key key, Value newValue)
{
Node node = GetNode(root, key);
if (node == null)
throw new ArgumentException("键" + key + "不存在，无法更改对应值");
else
node.value = newValue;
}
}
class RBT2Dictionary:IDictionary where Key:IComparable
{
private RBT2 rbt;
public RBT2Dictionary()
{
rbt = new RBT2();
}
public int Count { get { return rbt.Count; } }
public bool IsEmpty { get { return rbt.IsEmpty; } }
public void Add(Key key, Value value)
{
rbt.Add(key, value);
}
public bool ContainsKey(Key key)
{
return rbt.Contains(key);
}
public Value Get(Key key)
{
return rbt.Get(key);
}
public void Remove(Key key)
{
Console.WriteLine("待实现");
}
public void Set(Key key, Value newValue)
{
rbt.Set(key, newValue);
}
}
关于红黑树的插入和删除后续会补上。
哈希表哈希表是什么 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。 
代码
class HashST1
{
private LinkedList1[] hashtable;
private int N;
private int M;
public HashST1(int M)
{
this.M = M;
N = 0;
hashtable = new LinkedList1[M];
for (int i = 0; i
关注
打赏
![]()
1648518768
查看更多评论
最近更新
- 深拷贝和浅拷贝的区别（重点）
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state，props，refs（你学废了吗）
- 【脚手架VueCLI】从零开始，创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解（含代码）
- 【React】DOM的Diffing算法是什么？以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面？
