二叉查找树（binary search tree)
1）概念：对于树中的每个节点n，其左子节点中保存的所有数值都小于n保存的数值，右子节点保存的数值都大于n保存的数值。
2）二叉查找树可以实现更为优越的查找性能，主要实现方式有数组和链表结构，相比较而言，链表实现更为容易，因为数组实现删除和添加功能需要移动数组元素（如填补删除空位等）
今天下午在打印问题搞定后用C#实现了一下，比java版本比较有趣的使用C#的delegate来代替遍历二叉树时的visit方法，这样一来可以在遍历时对节点进行你所想要的任何操作。我们知道C#的delegate是类型化的函数指针，而C++的函数指针可以模仿动态语言的闭包或者匿名函数。这里也有这样的味道。
代码如下，只实现了整数型的，节点定义：
<!----> public class BSTIntNode
{
public int value;
public BSTIntNode left;
public BSTIntNode right;
public BSTIntNode(int value, BSTIntNode left, BSTIntNode right)
{
this.value = value;
this.left = left;
this.right = right;
}
public BSTIntNode(int value)
{
this.value = value;
this.left = null;
this.right = null;
}
}
然后定义一个Delegate，作为遍历时的访问方法：
<!----> public delegate void Visit(BSTIntNode node);
然后就是二叉树的实现，删除算法只实现了复制删除法：
<!---->public class BSTIntTree
{
protected BSTIntNode root;
public Visit visit;
public BSTIntTree()
{
this.root = null;
}
private BSTIntNode Search(BSTIntNode node, int el)
{
while (node != null)
{
if (el == node.value)
return node;
else if (el < node.value)
node = node.left;
else
node = node.right;
}
return null;
}
//查找
public BSTIntNode Search(int el)
{
return Search(root, el);
}
//广度优先遍历,利用队列实现,至上而下，至左而右
public void BreadthFirst()
{
BSTIntNode p = root;
Queue queue = new ListQueue();
if (p != null)
{
queue.Enqueue(p);
while (!queue.IsEmpty())
{
p = (BSTIntNode)queue.Dequeue();
visit(p);
if (p.left != null)
queue.Enqueue(p.left);
if (p.right != null)
queue.Enqueue(p.right);
}
}
}
//深度优先遍历，递归实现线序，中序和后序
//先序
protected void PreOrder(BSTIntNode p)
{
if (p != null)
{
visit(p);
PreOrder(p.left);
PreOrder(p.right);
}
}
public void PreOrder()
{
PreOrder(root);
}
//中序
protected void InOrder(BSTIntNode p)
{
if (p != null)
{
InOrder(p.left);
visit(p);
InOrder(p.right);
}
}
public void InOrder()
{
InOrder(root);
}
//后序
protected void PostOrder(BSTIntNode p)
{
if (p != null)
{
PostOrder(p.left);
PostOrder(p.right);
visit(p);
}
}
public void PostOrder()
{
PostOrder(root);
}
//插入节点操作
public void Insert(int el)
{
BSTIntNode p = root, prev = null;
//查找节点位置
while (p != null)
{
prev = p;
if (p.value < el)
p = p.right;
else
p = p.left;
}
if (root == null) //空树
root = new BSTIntNode(el);
else if (prev.value < el) //大于节点，插入右子树
prev.right = new BSTIntNode(el);
else
prev.left = new BSTIntNode(el);
}
//复制删除法的实现，归并删除法可能改变树的高度
public void Delete(int el)
{
BSTIntNode node, p = root, prev = null;
//查找节点位置
while (p != null&&p.value!=el)
{
prev = p;
if (p.value < el)
p = p.right;
else
p = p.left;
}
node = p;
if (p != null && p.value == el)
{
if (node.right == null)
node = node.left;
else if (node.left == null)
node = node.right;
else
{
BSTIntNode temp = node.left;
BSTIntNode previous = node;
while (temp.right != null) //查找左字节数的最右子节点
{
previous = temp;
temp = temp.right;
}
node.value = temp.value;
if (previous == node)
previous.left = temp.left;
else
previous.right = temp.left;
}
if (p == root)
root = node;
else if (prev.left == p)
prev.left = node;
else
prev.right = node;
}
else if (root != null)
{
Console.WriteLine("没有找到节点：{0}", el);
}
else
Console.WriteLine("树为空！");
}
}
注意，在树中我们维持了一个Visit的delegate，看看使用方法：
<!----> public static void Main(string[] args)
{
BSTIntTree tree=new BSTIntTree();
int []num={10,20,6,12,23,15,8};
for (int i = 0; i < num.Length; i++)
tree.Insert(num[i]);
//添加遍历处理函数，可以有多个
tree.visit += new Visit(printNode);
Console.WriteLine("广度优先遍历");
tree.BreadthFirst();
Console.WriteLine("先序");
tree.PreOrder();
Console.WriteLine("中序");
tree.InOrder();
Console.WriteLine("后序");
tree.PostOrder();
tree.Delete(8);
tree.Delete(15);
Console.WriteLine("删除后广度优先遍历");
tree.BreadthFirst();
}
public static void printNode(BSTIntNode node)
{
Console.WriteLine("访问节点:{0}", node.value);
}
可以看到，C#的delegate机制非常有趣，如果在java中恐怕需要用inner class来实现了。
分享到：
相关推荐
二叉排序树（Binary Sort Tree，BST），又称二叉查找树，是一种特殊的二叉树结构，其特性使得在树中的搜索、插入和删除操作具有较高的效率。主要特点如下： 1. **节点性质**： - 节点的左子树仅包含键值小于当前...
在C#中实现二叉查找树，我们需要定义一个表示节点的类，通常包含键、值、左子节点和右子节点等属性。下面是一个基本的二叉查找树节点类的实现： ```csharp public class TreeNode { public T Key; public T Value...
以下是一个简单的C#二叉查找树节点类的示例： ```csharp public class TreeNode, TValue> { public TKey Key { get; set; } public TValue Value { get; set; } public TreeNode, TValue> LeftChild { get; set;...
二叉查找树（Binary Search Tree，...通过这些文件，我们可以实现一个完整的C#二叉查找树数据结构，并对它进行各种操作。理解和掌握二叉查找树是理解数据结构和算法的关键，这对于任何IT专业人士来说都是至关重要的。
在C#中实现二叉排序树，首先需要定义一个二叉树节点类，包含键值、左子节点和右子节点属性。例如： ```csharp public class TreeNode { public int Key; public TreeNode Left; public TreeNode Right; } ``` ...
在"二叉查找树.sln"文件中，可能包含了使用某种编程语言（如C#或C++）实现的二叉查找树的项目解决方案。这个解决方案可能包括了源代码文件、编译配置和测试用例等，用于演示二叉查找树的基本操作，如插入、查找和...
C#，自平衡二叉查找树（AVL Tree）的算法与源代码 自平衡二叉查找树（AVL Tree）中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL...
二叉搜索树（BST，Binary Search Tree）又称二叉查找树或二叉排序树。 一棵二叉搜索树是以二叉树来组织的，可以使用一个链表数据结构来表示，其中每一个结点就是一个对象。 一般地，除了key和位置数据之外，每个结点...
在给定的C#源代码中，可能包含了二叉排序树的构造、查找和插入功能的实现，但没有提及删除操作，这可能是为了简化示例。 4. **C#源代码**： C#是微软公司推出的面向对象的编程语言，被广泛用于Windows平台的开发，...
在C#中实现二叉搜索树，我们通常会定义一个Node类来表示树的节点，以及一个BinarySearchTree类来封装树的操作。Node类可能包含以下属性： ```csharp public class Node { public int Key { get; set; } public ...
在C#中，我们可以创建一个二叉搜索树类`BinaryTreeNode`来表示树的节点，它通常包含键值、左子节点和右子节点属性。例如： ```csharp public class BinaryTreeNode { public int Key { get; set; } public ...
在C++和C#这两种编程语言中实现二叉搜索树，我们需要关注以下关键点： 1. **数据结构定义**：首先，要定义一个表示节点的类或结构体，它包含键、值、左子节点和右子节点的引用。在C++中，可以定义为`struct Node`，...
在这个问题中，我们用C#语言实现了动态规划算法来构建最优二叉搜索树。动态规划是一种解决最优化问题的有效方法，它将大问题分解为小问题，然后通过构建子问题的最优解来获得原问题的最优解。 首先，我们需要理解...
在C#中实现AVL树，首先需要理解二叉查找树的基本概念和操作。二叉查找树是一种特殊的二叉树，其中每个节点都包含一个键（key）、一个关联的值、一个指向左子树的指针和一个指向右子树的指针。在二叉查找树中，每个...
总结一下，C#二叉搜索树的插入算法涉及以下几个关键知识点： 1. **二叉搜索树定义**：每个节点的左子树只包含键小于节点键的节点，右子树只包含键大于节点键的节点。 2. **节点类定义**：创建一个`BinaryTreeNode`...
在本文中，我们将深入探讨如何使用C#编程语言实现二叉树，并将其应用于Windows窗体应用程序。二叉树是一种基础且重要的数据结构，它在计算机科学中有着广泛的应用，包括搜索、排序、图形处理和文件系统等。 首先，...
本文将详细解析C#中的基础查找算法，包括静态查找与动态查找、内查找与外查找，以及两种具体的查找算法：顺序查找（线性查找）和二叉查找（折半查找）。这些算法在数据处理、数据库操作和优化搜索效率等方面有着广泛...
**C# K-d树实现** K-d树（K-dimensional tree）是一种在高维空间中用于组织数据的数据结构，尤其适用于范围搜索和最近邻搜索。它是一种平衡的分层数据结构，类似于二叉搜索树，但扩展到了多维空间。C#作为一种广泛...
AVL树是一种自平衡二叉查找树，最早由G. M. Adelson-Velsky和E. M. Landis在1962年提出，因此得名AVL树。它的特点是任何节点的两个子树的高度最大差别不超过1，这使得AVL树在插入和删除操作后能够快速恢复平衡，从而...