爱学记
判断二叉树是否是二叉排序树 二叉排序树的C#实现
二叉排序树的C#实现
二叉排序树说起来其实并不是很难 二叉查找树是一种把值比较小的节点存储在左子节点内而值比较大的节点存储在右子节点里的树 其基本操作有以下几种
插入
我们对这个二叉树插入节点 如果二叉树本身没有任何节点 那么插入的这个节点就成为根节点 否则 根据定义 你应该遍历树 找出某一个节点 如果带插入节点的值大于这个节点 则成为带插入节点的右节点 否则就是左节点 从这里看来 根节点本身就是一个树的节点 因此 我首先实现了一个TreeNode类型 如下
: public class TreeNode<T>:IComparable IComparable<TreeNode<T>> {
:
: #region ctor 串联构造函数
:
: public TreeNode():this(default(T) null null ){
: }
:
: public TreeNode(T value):this(value null null ) {
: }
:
: public TreeNode(T value TreeNode<T> leftNode TreeNode<T> rightNode):this(value leftNode rightNode ) {
: }
:
: public TreeNode(T value TreeNode<T> leftNode TreeNode<T> rightNode int deepness) {
: Value = value;
: LeftNode = leftNode;
: RightNode = rightNode;
: Deepness = deepness;
: IsLeaf = true;
: }
:
: public override string ToString() {
: return Value ToString();
: }
:
: #endregion
:
: #region Interface Members
:
: int IComparable CompareTo(Object item) {
: TreeNode<T> node = item as TreeNode<T>;
: if (node == null)
: throw new ArgumentException( Argument for paring is not a object of TreeNode Type !! );
: else {
: if (this == item)
: return ;
: else {
: Comparer parer = new Comparer(CultureInfo CurrentCulture);
: return parer Compare(this Value node Value);
: }
: }
: }
:
: int IComparable<TreeNode<T>> CompareTo(TreeNode<T> item) {
: if (item == null) {
: throw new ArgumentException( Argument for paring is not a object of TreeNode Type !! );
: } else {
: if (this == item)
: return ;
: else {
: Comparer parer = new Comparer(CultureInfo CurrentCulture);
: return parer Compare(this Value item Value);
: }
: }
: }
: #endregion
:
: #region Properties
:
: public TreeNode<T> LeftNode {
: get;
: set;
: }
:
: public TreeNode<T> RightNode {
: get;
: set;
: }
:
: public TreeNode<T> FatherNode {
: get;
: set;
: }
:
: //这个属性是指数的层数 也就是深度 根的深度为
: public int Deepness {
: get;
: set;
: }
:
: //这个属性指示这个节点是不是叶子节点
: public bool IsLeaf {
: get;
: set;
: }
:
: //这个属性返回或者设置该节点的值
: public T Value {
: get;
: set;
: }
:
: #endregion
: }
接下来我们就能实现插入的功能了 通常我觉得好的代码是自描述的 也就是一段好的代码应该能自己描述自己的用途的
: public void Add(T itemValue) {
: if (Root == null) {
: TreeNode<T> root = new TreeNode<T>(itemValue);
: this Root = root;
: this Count++;
: } else {
: TreeNode<T> _iterator = this Root;
: bool okFlag = true;;
: int deepness = ;
: int result = _parer Compare(itemValue _iterator Value); ;
:
: while (okFlag) {
: Debug WriteLine( Comaper Result is : + result ToString());
: Debug WriteLine( );
: if (result > ) {
: if (_iterator RightNode != null) {
: _iterator = _iterator RightNode;
: result = _parer Compare(itemValue _iterator Value);
: deepness++;
: } else {
: //在添加节点的时候就设置该节点的深度 而在计算整棵树的深度的时候 其实只要对所有叶节点的深度的值进行排序就可以得到了
: _iterator RightNode = new TreeNode<T>(itemValue null null deepness);
: _iterator IsLeaf = false;
: _iterator RightNode FatherNode = _iterator;
: Count++;
: okFlag = false;
: }
: } else if (result < ) {
: if (_iterator LeftNode != null) {
: _iterator = _iterator LeftNode;
: result = _parer Compare(itemValue _iterator Value);
: deepness++;
: } else {
: _iterator LeftNode = new TreeNode<T>(itemValue null null deepness);
: _iterator IsLeaf = false;
: _iterator LeftNode FatherNode = _iterator;
: Count++;
: okFlag = false;
: }
: } else
: okFlag = false;
: }
: }
: }
这里在比较的时候 我是在全局设置了一个与本地文化相关的Comparer类型的私有成员_parer 这个类型用于对象判等 关键是你要判断的对象必须实现IComparable 接口 我编写的TreeNode类型就实现了这个接口了
查找
根据二叉搜索树的特点 如果你要搜索的节点的值比当前节点值小 那么就再搜索该节点的左子树 否则 搜索右子树 这个过程是递归过程
如果找到匹配的节点 返回ture;否则 当前节点为Null 然后又不等于你要搜索的节点的值 那么就直接返回false 我的实现如下
: public bool IsExit(T key out TreeNode<T> node) {
: node = null;
: TreeNode<T> _iterator = Root;
: int result = _parer Compare(key _iterator Value);
: bool okFlag = true;
: while (okFlag) {
: if (result == ) {
: okFlag = false;
: node = _iterator;//如果找到这个叶子结点 那么得到叶子节点的指针
: return true;
: } else if (result > ) {
: _iterator = _iterator RightNode;
: if (_iterator != null)
: result = _parer Compare(key _iterator Value);
: else {
: okFlag = false;
: return false;
: }
: } else {
: _iterator = _iterator LeftNode;
: if (_iterator != null)
: result = _parer Compare(key _iterator Value);
: else {
: okFlag = false;
: return false;
: }
: }
: }
: return false;
: }
遍历
这个分三种情况的遍历 分别是前根遍历 中根遍历 后根遍历 其实很简单 就是按照访问节点的顺序来划分的 如果先访问左子节点 然后访问父节点 最后在访问右节点 这个情况就是前序遍历 其他的情况以此类推 这里我实现的时候 是用递归的方式
: /// <summary>
: /// 中根遍历树
: /// </summary>
: /// <param name= root ></param>
: public void InOrder(TreeNode<T> root) {
: if (root != null) {
: InOrder(root LeftNode);
: Console WriteLine(string Format( This node s value is { } and it s deepness is { } leaf:{ } root ToString() root Deepness ToString() root IsLeaf ToString()));
: InOrder(root RightNode);
: }
: }
:
: /// <summary>
: /// 先根遍历树
: /// </summary>
: /// <param name= root ></param>
: public void PreOrder(TreeNode<T> root) {
: if (root != null) {
: Console WriteLine(string Format( This node s value is { } and it s deepness is { } leaf:{ } root ToString() root Deepness ToString() root IsLeaf ToString()));
: PreOrder(root LeftNode);
: PreOrder(root RightNode);
: }
: }
:
: /// <summary>
: /// 后根遍历树
: /// </summary>
: /// <param name= root ></param>
: public void PostOrder(TreeNode<T> root) {
: if (root != null) {
: PostOrder(root LeftNode);
: PostOrder(root RightNode);
: string Format( This node s value is { } and it s deepness is { } leaf:{ } root ToString() root Deepness ToString() root IsLeaf ToString());
: }
: }
删除节点
作为这个树的实现里面最有难度的地方 要考虑三种情况
要删除的节点时叶子结点 这个情况很好解决 直接删掉就好了
要删除的节点只有一个子节点 这个情况也很好解决 子节点替换一下父节点 问题解决
要删除的节点有两个节点 这个就比较复杂了一些 但我们仔细分析 就会发现 要删除这个节点 只要利用中根遍历得到直接前驱或者直接后继结点代替该节点就可以了 同时 你还要删除前驱或者后继这个节点 而这两个节点 一定符合前面的两种情况之一
: public void Remove(T key) {
: TreeNode<T> node;
: bool isExit = IsExit(key out node);
: if (!isExit) {
: return;
: } else {
: if (IsLeafNode(node)) {
: if (node FatherNode LeftNode == node)
: node FatherNode LeftNode = null;
: else
: node FatherNode RightNode = null;
: if (node != null) node = null;
: } else {
: if (!HasTwoLeafNodes(node)) {
: TreeNode<T> child = GetUniqueChild(node);
: if (node FatherNode LeftNode == node) {
: node FatherNode LeftNode = child;
: } else {
: if (node LeftNode != null)
: node FatherNode RightNode = child;
: }
: if (node != null) node = null;
: } else {
: //首先找到后继结点
: TreeNode<T> successor = GetSuccessor(node);
: //调整节点值 这个时候有一个值得注意的地方 比如你的树是这样的情况
: /* 或者
: * /
: *
: * / /
: * /
: * / /
: * / /
: *
: *
: *
: */
: //树A中节点 相应的后继结点应该是 那么 的左子节点应调整成 就要调整成
: node Value = successor Value;
: Remove(successor);
: }
: }
: this Count ;
: }
: }
以下是完整的代码 尽管是泛型 但其实我仅仅使用int类型编写 过测试 如果其他的类型 我想只要是实现了IComparable接口 应该就能正常工作
: using System;
: using System Collections;
: using System Collections Generic;
: using System Globalization;
: using System Diagnostics;
: using System Text;
:
: namespace Ultis {
: public class BinaryTree<T> {
: #region ctor
:
: static BinaryTree() {
: _parer = new Comparer(CultureInfo CurrentCulture);
: }
:
: public BinaryTree() {
: this Root = null;
: this Count = ;
: this _deepness = ;
: }
:
: public BinaryTree(TreeNode<T> root) {
: if (root == null) {
: throw new ArgumentException( Root can not be null !! );
: }
: this Root = root;
: this Count++;
: this _deepness = ;
: }
: #endregion
:
: #region Public Members
:
: /// <summary>
: ///
: /// </summary>
: /// <param name= itemValue ></param>
: public void Add(T itemValue) {
: if (Root == null) {
: TreeNode<T> root = new TreeNode<T>(itemValue);
: this Root = root;
: this Count++;
: } else {
: TreeNode<T> _iterator = this Root;
: bool okFlag = true;;
: int deepness = ;
: int result = _parer Compare(itemValue _iterator Value); ;
:
: while (okFlag) {
: Debug WriteLine( Comaper Result is : + result ToString());
: Debug WriteLine( );
: if (result > ) {
: if (_iterator RightNode != null) {
: _iterator = _iterator RightNode;
: result = _parer Compare(itemValue _iterator Value);
: deepness++;
: } else {
: //在添加节点的时候就设置该节点的深度 而在计算整棵树的深度的时候 其实只要对所有叶节点的深度的值进行排序就可以得到了
: _iterator RightNode = new TreeNode<T>(itemValue null null deepness);
: _iterator IsLeaf = false;
: _iterator RightNode FatherNode = _iterator;
: Count++;
: okFlag = false;
: }
: } else if (result < ) {
: if (_iterator LeftNode != null) {
: _iterator = _iterator LeftNode;
: result = _parer Compare(itemValue _iterator Value);
: deepness++;
: } else {
: _iterator LeftNode = new TreeNode<T>(itemValue null null deepness);
: _iterator IsLeaf = false;
: _iterator LeftNode FatherNode = _iterator;
: Count++;
: okFlag = false;
: }
: } else
: okFlag = false;
: }
: }
: }
:
: /// <summary>
: /// 从树中移出一个节点 要考虑很多情况 比如要删除的节点没有子节点 有一个子节点 有两个子节点
: /// PS:这个方法应进行测试
: /// </summary>
: /**
: * 删除指定的节点实现
: *
: * 算法思想
: *
: * 若待删除的节点p是叶子节点 则直接删除该节点
: *
: * 若待删除的节点p只有一个子节点 则将p的子节点与p的父节点直接连接 然后删除节点p
: * 为什么只有一个子节点时可以直接接到删除节点的父节点下面呢?因为只有一个子节点 直接接上
: * 去不会影响排序子节点本身的排序 当然更不会影响另外一个子树（因为另一子树跟本不存在!）
: *
: * 若待删除节点p有两个子节点时 应该使用中序遍历方式得到的直接前置节点S或直接后继节点s
: * 的值来代替点s的值 然后删除节点s （注 节点s肯定属于上述 情况之一）而不是直接删除
: * p 这样可以将该删除问题转换成上面 问题
: */
: public void Remove(T key) {
: TreeNode<T> node;
: bool isExit = IsExit(key out node);
: if (!isExit) {
: return;
: } else {
: if (IsLeafNode(node)) {
: if (node FatherNode LeftNode == node)
: node FatherNode LeftNode = null;
: else
: node FatherNode RightNode = null;
: if (node != null) node = null;
: } else {
: if (!HasTwoLeafNodes(node)) {
: TreeNode<T> child = GetUniqueChild(node);
: if (node FatherNode LeftNode == node) {
: node FatherNode LeftNode = child;
: } else {
: if (node LeftNode != null)
: node FatherNode RightNode = child;
: }
: if (node != null) node = null;
: } else {
: //首先找到后继结点
: TreeNode<T> successor = GetSuccessor(node);
: //调整节点值 这个时候有一个值得注意的地方 比如你的树是这样的情况
: /* 或者
: * /
: *
: * / /
: * /
: * / /
: * / /
: *
: *
: *
: */
: //树A中节点 相应的后继结点应该是 那么 的左子节点应调整成 就要调整成
: node Value = successor Value;
: Remove(successor);
: }
: }
: this Count ;
: }
: }
:
:
: /**
: * 删除指定的节点实现
: *
: * 算法思想
: *
: * 若待删除的节点p是叶子节点 则直接删除该节点
: *
: * 若待删除的节点p只有一个子节点 则将p的子节点与p的父节点直接连接 然后删除节点p
: * 为什么只有一个子节点时可以直接接到删除节点的父节点下面呢?因为只有一个子节点 直接接上
: * 去不会影响排序子节点本身的排序 当然更不会影响另外一个子树（因为另一子树跟本不存在!）
: *
: * 若待删除节点p有两个子节点时 应该使用中序遍历方式得到的直接前置节点S或直接后继节点s
: * 的值来代替点s的值 然后删除节点s （注 节点s肯定属于上述 情况之一）而不是直接删除
: * p 这样可以将该删除问题转换成上面 问题
: */
: public void Remove(TreeNode<T> node) {
: if (IsLeafNode(node)) {
: if (node FatherNode LeftNode == node)
: node FatherNode LeftNode = null;
: else
: node FatherNode RightNode = null;
: if (node != null) node = null;
: } else {
: if (!HasTwoLeafNodes(node)) {
: TreeNode<T> child = GetUniqueChild(node);
: if (node FatherNode LeftNode == node) {
: node FatherNode LeftNode = child;
: } else {
: node FatherNode RightNode = child;
: }
: if(node != null) node = null;
: } else {
: //要删除的节点有两个子节点
: TreeNode<T> successor = GetSuccessor(node);
: node Value = successor Value;
: Remove(successor); //删除相应的后继结点
: if (successor != null) successor = null;
: }
: }
: this Count ;
: }
:
: /// <summary>
: /// 返回某一节点唯一的一个节点
: /// </summary>
: /// <param name= node ></param>
: /// <returns></returns>
: private TreeNode<T> GetUniqueChild(TreeNode<T> node) {
: TreeNode<T> child;
: if (node LeftNode != null)
: child = node LeftNode;
: else
: child = node RightNode;
: return child;
: }
:
: /// <summary>
: /// 根据中根遍历来得到相应的后继结点 仍然还有BUG存在！
: /// </summary>
: /// <param name= value ></param>
: /// <returns></returns>
: public TreeNode<T> GetSuccessor(T value) {
: throw new NotImplementedException( This function is not plete yet ! );
: IComparable iparable = Root as IComparable;
: TreeNode<T> wanted = new TreeNode<T>(value);
: if (iparable CompareTo(wanted) == ) {
: return Root;
: } else {
: TreeNode<T> node;
: if (IsExit(value out node)) {
: if (IsLeafNode(node)) { //如果是叶子节点 那么应该做么做才能返回正确的后继节点？
: return null;
: }else
: return GetSuccessor(node); //如果是非叶子节点 则调用相应的方法返回非叶子节点的后继结点
: } else
: return null;
: }
: }
:
: /// <summary>
: /// 中根遍历树
: /// </summary>
: /// <param name= root ></param>
: public void InOrder(TreeNode<T> root) {
: if (root != null) {
: InOrder(root LeftNode);
: Console WriteLine(string Format( This node s value is { } and it s deepness is { } leaf:{ } root ToString() root Deepness ToString() root IsLeaf ToString()));
: InOrder(root RightNode);
: }
: }
:
: /// <summary>
: /// 先根遍历树
: /// </summary>
: /// <param name= root ></param>
: public void PreOrder(TreeNode<T> root) {
: if (root != null) {
: Console WriteLine(string Format( This node s value is { } and it s deepness is { } leaf:{ } root ToString() root Deepness ToString() root IsLeaf ToString()));
: PreOrder(root LeftNode);
: PreOrder(root RightNode);
: }
: }
:
: /// <summary>
: /// 后根遍历树
: /// </summary>
: /// <param name= root ></param>
: public void PostOrder(TreeNode<T> root) {
: if (root != null) {
: PostOrder(root LeftNode);
: PostOrder(root RightNode);
: string Format( This node s value is { } and it s deepness is { } leaf:{ } root ToString() root Deepness ToString() root IsLeaf ToString());
: }
: }
:
: /// <summary>
: /// 返回具有最大节点值的树节点
: /// </summary>
: /// <returns></returns>
: public TreeNode<T> GetMaxNode() {
: TreeNode<T> _iterator = Root;
: while (_iterator RightNode != null) {
: _iterator = _iterator RightNode;
: }
: return _iterator;
: }
:
: /// <summary>
: /// 返回最大的值
: /// </summary>
: /// <returns></returns>
: public T GetMaxValue() {
: return GetMaxNode() Value;
: }
:
: /// <summary>
: /// 返回具有最小节点值得节点
: /// </summary>
: /// <returns></returns>
: public TreeNode<T> GetMinNode() {
: TreeNode<T> _iterator = Root;
: while (_iterator LeftNode != null) {
: _iterator = _iterator LeftNode;
: }
: return _iterator;
: }
:
: /// <summary>
: /// 返回最小值
: /// </summary>
: /// <returns></returns>
: public T GetMinValue() {
: return GetMinNode() Value;
: }
:
: public bool IsExit(T key out TreeNode<T> node) {
: node = null;
: TreeNode<T> _iterator = Root;
: int result = _parer Compare(key _iterator Value);
: bool okFlag = true;
: while (okFlag) {
: if (result == ) {
: okFlag = false;
: node = _iterator;//如果找到这个叶子结点 那么得到叶子节点的指针
: return true;
: } else if (result > ) {
: _iterator = _iterator RightNode;
: if (_iterator != null)
: result = _parer Compare(key _iterator Value);
: else {
: okFlag = false;
: return false;
: }
: } else {
: _iterator = _iterator LeftNode;
: if (_iterator != null)
: result = _parer Compare(key _iterator Value);
: else {
: okFlag = false;
: return false;
: }
: }
: }
: return false;
: }
:
: public override string ToString() {
: string rtnString = string Format( This is a kind of binary tree that impleted by Master and it has { } nodes Count ToString());
: return rtnString;
: }
:
: public TreeNode<T> Root {
: get;
: set;
: }
:
: public int Count {
: get;
: private set;
: }
:
: //返回树的深度
: public int Deepness {
: get {
: if (Count == )
: return ;
: else {
: int[] _deepnessSortArray = new int[Count];
: int pointer = Count ;
: for (int i = ; i < Count; i++) _deepnessSortArray[i] = ;
: InOrder(Root ref pointer ref _deepnessSortArray);
: Array Sort<int>(_deepnessSortArray); //对_deepnessSortArray进行排序 得出其中最大的数值就是该树的深度
: return _deepnessSortArray[Count ];
: }
: }
: }
:
: #endregion
:
: #region Private Members
:
: private static Comparer _parer;
:
: private int _deepness;
:
: /// <summary>
: /// 遍历树节点 然后给深度数组_deepnessSortArray[i]赋值 之后对这个数组进行排序 得到的最大值就是该树的深度
: /// </summary>
: /// <param name= root ></param>
: /// <param name= pointer ></param>
: /// <param name= deepnessSortArray ></param>
: private void InOrder(TreeNode<T> root ref int pointer ref int[] deepnessSortArray) {
: if (root != null) {
: InOrder(root LeftNode ref pointer ref deepnessSortArray);
: deepnessSortArray[pointer] = root Deepness;
: pointer ;
: InOrder(root RightNode ref pointer ref deepnessSortArray);
: }
: }
:
: /// <summary>
: /// 基于中根遍历的算法来得到某一个非叶子节点的后继结点
: /// </summary>
: /// <param name= wannaDelNode ></param>
: private TreeNode<T> GetSuccessor(TreeNode<T> wannaDelNode) {
: TreeNode<T> _iterator = wannaDelNode RightNode;
: TreeNode<T> successorFather = null;
: TreeNode<T> successor = null;
:
: //Debug WriteLine(string Format( _iterator s value is { } _iterator Value ToString()));
: //Debug WriteLine(string Format( successor s value is { } successor Value ToString()));
: //首先应该要判断是不是叶子节点 如果是叶子节点 情况就完全不一样了
: while (_iterator != null) {
: successorFather = _iterator FatherNode;
: successor = _iterator;
: _iterator = _iterator LeftNode;
: }
: return successor;
: }
:
: private bool IsLeafNode(TreeNode<T> node) {
: return (node LeftNode == null && node RightNode == null) ? true : false;
: }
:
: private bool HasTwoLeafNodes(TreeNode<T> node) {
: return (node LeftNode != null && node RightNode != null) ? true : false;
: }
:
: #endregion
: }
lishixinzhi/Article/program/net/201311/12641
微信收款码
支付宝收款码