C#实现二叉查找树

xiaoxiao2024-05-31 101

二叉查找树（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来实现了。

文章转自庄周梦蝶，原文发布时间5.17