C#实现二叉查找树的算法

C#实现二叉查找树的算法2013-11-13简介

树是一种非线性结构。树的本质是将一些节点由边连接起来，形成层级的结构。而二叉树是一种特殊的树，使得树每个子节点必须小于等于2.而二叉查找树又是一类特殊的二叉树。使得每一个节点的左节点或左子树的所有节点必须小于这个节点，右节点必须大于这个节点。从而方便高效搜索。

下面来看如何使用C#实现二叉查找树。

实现节点

二叉查找树是节点的集合。因此首先要构建节点，如代码1所示。

//二叉查找树的节点定义publicclass Node{//节点本身的数据publicint data;//左孩子public Node left;//右孩子public Node right;publicvoid DisplayData（）{Console.Write（data+""）;}}

代码1.节点的定义

构建二叉树

构建二叉树是通过向二叉树插入元素得以实现的，所有小于根节点的节点插入根节点的左子树，大于根节点的，插入右子树。依此类推进行递归。直到找到位置进行插入。二叉查找树的构建过程其实就是节点的插入过程。C#实现代码如代码2所示。

publicvoid Insert（int data）{Node Parent;//将所需插入的数据包装进节点Node newNode=new Node（）;newNode.data=data; //如果为空树，则插入根节点if（rootNode==null）{rootNode=newNode;}//否则找到合适叶子节点位置插入else{Node Current = rootNode;while（true）{Parent=Current;if（newNode.data<Current.data）{Current=Current.left;if（Current==null）{Parent.left=newNode;//插入叶子后跳出循环break;}}else{Current = Current.right;if （Current == null）{Parent.right = newNode;//插入叶子后跳出循环break;}}}}}

代码2.实现二叉树的插入