二叉树查找（C#）
2024-10-11 15:40:35
参考文章：
http://www.cnblogs.com/huangxincheng/archive/2012/07/21/2602375.html
http://www.cnblogs.com/xiashengwang/archive/2013/03/04/2942555.html
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading;
using System.IO;
using System.Collections; namespace ConsoleApplication2
{
public class Program
{
public static void Main()
{
BinaryTree<int, Student> binaryTree = new BinaryTree<int, Student>();
binaryTree.Add(, new Student() { Age = , Name = "", Sex = false });//这个是用Age作为key
binaryTree.Add(, new Student() { Age = , Name = "", Sex = false });
binaryTree.Add(, new Student() { Age = , Name = "", Sex = true });
binaryTree.Add(, new Student() { Age = , Name = "", Sex = false });
binaryTree.Add(, new Student() { Age = , Name = "", Sex = true });
binaryTree.Add(, new Student() { Age = , Name = "", Sex = false });
binaryTree.Add(, new Student() { Age = , Name = "", Sex = true });
binaryTree.Add(, new Student() { Age = , Name = "", Sex = true });
binaryTree.Add(, new Student() { Age = , Name = "", Sex = false });
binaryTree.Add(, new Student() { Age = , Name = "", Sex = true });
binaryTree.Add(, new Student() { Age = , Name = "", Sex = true });
binaryTree.Add(, new Student() { Age = , Name = "", Sex = true });
binaryTree.Add(, new Student() { Age = , Name = "38@", Sex = true });//注意哦 这里故意又出现个38
binaryTree.Add(, new Student() { Age = , Name = "", Sex = false }); Console.WriteLine("层排序遍历：");
LevelOrder(binaryTree.RootNote);
Console.WriteLine(); Console.WriteLine("是否含有指定元素");
Console.WriteLine(binaryTree.Contain());
Console.WriteLine(); Console.WriteLine("最小元素");
Console.WriteLine(binaryTree.FindMin().TreeKey);
Console.WriteLine(); Console.WriteLine("最大元素");
Console.WriteLine(binaryTree.FindMax().TreeKey);
Console.WriteLine(); Console.WriteLine("范围查找");
foreach (var item in binaryTree.SearchRange(, ))
{
Console.WriteLine(item.Age);
}
Console.WriteLine(); Console.WriteLine("删除指定元素");
binaryTree.Remove(, new Student() { Age = , Name = "", Sex = false });
Console.WriteLine(); Console.WriteLine("层排序遍历：");
LevelOrder(binaryTree.RootNote);
Console.WriteLine(); Console.WriteLine("前序遍历：");
PreOrder(binaryTree.RootNote);
Console.WriteLine(); Console.WriteLine("中序遍历：");
InOrder(binaryTree.RootNote);
Console.WriteLine(); Console.WriteLine("后序遍历：");
PostOrder(binaryTree.RootNote);
Console.WriteLine(); Console.Read();
} private static void PreOrder(TreeNote<int, Student> treeNote)
{
foreach (var item in treeNote.TreeValues)
{
Console.Write(item.Name + " ");
} if (treeNote.LeftTreeNote != null)
{
PreOrder(treeNote.LeftTreeNote);
} if (treeNote.RightTreeNote != null)
{
PreOrder(treeNote.RightTreeNote);
}
} private static void InOrder(TreeNote<int, Student> treeNote)
{
if (treeNote.LeftTreeNote != null)
{
InOrder(treeNote.LeftTreeNote);
} foreach (var item in treeNote.TreeValues)
{
Console.Write(item.Name + " ");
} if (treeNote.RightTreeNote != null)
{
InOrder(treeNote.RightTreeNote);
}
} private static void PostOrder(TreeNote<int, Student> treeNote)
{
if (treeNote.LeftTreeNote != null)
{
PostOrder(treeNote.LeftTreeNote);
} if (treeNote.RightTreeNote != null)
{
PostOrder(treeNote.RightTreeNote);
} foreach (var item in treeNote.TreeValues)
{
Console.Write(item.Name + " ");
}
} private static void LevelOrder(TreeNote<int, Student> treeNote)
{
Queue queue = new Queue();
queue.Enqueue(treeNote);
while (queue.Count > )
{
var treeNoteTemp = (TreeNote<int, Student>)queue.Dequeue(); foreach (var item in treeNoteTemp.TreeValues)
{
Console.Write(item.Name + " ");
} if (treeNoteTemp.LeftTreeNote != null)
{
queue.Enqueue(treeNoteTemp.LeftTreeNote);
} if (treeNoteTemp.RightTreeNote != null)
{
queue.Enqueue(treeNoteTemp.RightTreeNote);
}
}
}
} public class Student : IEquatable<Student>//由于后面代码的treeNote.TreeValues.Remove(treeValue); 因为HashCode不同无法删除 这里需要重写GetHashCode()
{
public string Name { get; set; }
public bool Sex { get; set; }
public int Age { get; set; } public bool Equals(Student other)
{
return this.Name == other.Name &&
this.Sex == other.Sex &&
this.Age == other.Age;
}
public override bool Equals(object obj)
{
if (obj == null) return base.Equals(obj); if (obj is Student)
return Equals(obj as Student);
else
throw new InvalidCastException("the 'obj' Argument is not a Student object");
}
public override int GetHashCode()
{
return Name.GetHashCode()^Sex.GetHashCode()^Age.GetHashCode();//return object's hashcode
}
} public class TreeNote<TKey, TValue> where TKey : IComparable
{
public TreeNote(TKey treeKey, TValue treeValue)
{
TreeKey = treeKey;
TreeValues = new HashSet<TValue>();
TreeValues.Add(treeValue);
} public TKey TreeKey { get; set; }
public HashSet<TValue> TreeValues { get; set; }
public TreeNote<TKey, TValue> LeftTreeNote { get; set; }
public TreeNote<TKey, TValue> RightTreeNote { get; set; }
} public class BinaryTree<TKey, TValue> where TKey : IComparable
{
public TreeNote<TKey, TValue> RootNote = null;//根节点 public void Add(TKey treeKey, TValue treeValue)
{
RootNote = Add(treeKey, treeValue, RootNote);
} private TreeNote<TKey, TValue> Add(TKey treeKey, TValue treeValue, TreeNote<TKey, TValue> treeNote)
{
if (treeNote == null)
{
return new TreeNote<TKey, TValue>(treeKey, treeValue);
} if (treeNote.TreeKey.CompareTo(treeKey) > )
{
treeNote.LeftTreeNote = Add(treeKey, treeValue, treeNote.LeftTreeNote);
} if (treeNote.TreeKey.CompareTo(treeKey) < )
{
treeNote.RightTreeNote = Add(treeKey, treeValue, treeNote.RightTreeNote);
} if (treeNote.TreeKey.CompareTo(treeKey) == )
{
treeNote.TreeValues.Add(treeValue);
} return treeNote;
} public bool Contain(TKey treeKey)
{
return Contain(treeKey, RootNote);
} private bool Contain(TKey treeKey, TreeNote<TKey, TValue> treeNote)
{
if (treeNote == null)
{
return false;
} if (treeNote.TreeKey.CompareTo(treeKey) > )
{
return Contain(treeKey, treeNote.LeftTreeNote);
} if (treeNote.TreeKey.CompareTo(treeKey) < )
{
return Contain(treeKey, treeNote.RightTreeNote);
} return treeNote.TreeKey.CompareTo(treeKey) == ;
} public HashSet<TValue> SearchRange(TKey minTreeKey, TKey maxTreeKey)
{
return SearchRange(minTreeKey, maxTreeKey, RootNote, new HashSet<TValue>());
} private HashSet<TValue> SearchRange(TKey minTreeKey, TKey maxTreeKey, TreeNote<TKey, TValue> treeNote, HashSet<TValue> attach)
{
if (treeNote == null)
{
return attach;
} if (treeNote.TreeKey.CompareTo(minTreeKey) > )
{
SearchRange(minTreeKey, maxTreeKey, treeNote.LeftTreeNote, attach);
} if (treeNote.TreeKey.CompareTo(minTreeKey) >= && treeNote.TreeKey.CompareTo(maxTreeKey) <= )
{
foreach (var item in treeNote.TreeValues)
{
attach.Add(item);
}
} if (treeNote.TreeKey.CompareTo(maxTreeKey) < )
{
SearchRange(minTreeKey, maxTreeKey, treeNote.RightTreeNote, attach);
} return attach;
} public TreeNote<TKey, TValue> FindMin()
{
return FindMin(RootNote);
} private TreeNote<TKey, TValue> FindMin(TreeNote<TKey, TValue> treeNote)
{
if (treeNote == null)
{
return null;
} if (treeNote.LeftTreeNote == null)
{
return treeNote;
}
else
{
return FindMin(treeNote.LeftTreeNote);
}
} public TreeNote<TKey, TValue> FindMax()
{
return FindMax(RootNote);
} private TreeNote<TKey, TValue> FindMax(TreeNote<TKey, TValue> treeNote)
{
if (treeNote == null)
{
return null;
} if (treeNote.RightTreeNote == null)
{
return treeNote;
}
else
{
return FindMax(treeNote.RightTreeNote);
}
} public void Remove(TKey treeKey, TValue treeValue)
{
Remove(treeKey, treeValue, RootNote, true);
} private TreeNote<TKey, TValue> Remove(TKey treeKey, TValue treeValue, TreeNote<TKey, TValue> treeNote, bool isAccordingToTreeValues)
{
if (treeNote == null)
{
return null;
} if (treeNote.TreeKey.CompareTo(treeKey) > )
{
treeNote.LeftTreeNote = Remove(treeKey, treeValue, treeNote.LeftTreeNote, isAccordingToTreeValues);
} if (treeNote.TreeKey.CompareTo(treeKey) < )
{
treeNote.RightTreeNote = Remove(treeKey, treeValue, treeNote.RightTreeNote, isAccordingToTreeValues);
} if (treeNote.TreeKey.CompareTo(treeKey) == )
{
if (treeNote.TreeValues.Count > && isAccordingToTreeValues)
{
treeNote.TreeValues.Remove(treeValue);
}
else
{
if (treeNote.LeftTreeNote == null || treeNote.RightTreeNote == null)
{
treeNote = treeNote.LeftTreeNote == null ? treeNote.RightTreeNote : treeNote.LeftTreeNote;
}
else //有一对子元素
{
var treeNoteTemp = FindMin(treeNote.RightTreeNote);//右子节点下的最小子节点替换当前节点
treeNote.TreeKey = treeNoteTemp.TreeKey;
treeNote.TreeValues = treeNoteTemp.TreeValues; treeNote.RightTreeNote = Remove(treeNoteTemp.TreeKey, treeValue, treeNote.RightTreeNote, false);
}
}
}
return treeNote;
}
}
}
最新文章
- python之路:Day01 --- Python基础1
- react入门（1）
- Mysql查看版本，端口命令
- NET RichTextBox控件如何可以插入图像
- Fixing “WARNING: UNPROTECTED PRIVATE KEY FILE!” on Linux
- ARM时钟初始化
- Could not find action or result 导致 页面出现404错误
- PHPCMS 核心代码与 www 分离部署
- Linux Shell编程（2）——第一个shell程序
- C++设计模式之状态模式(四)
- 有return如果是try catch finally运行命令
- Android笔记：Fragment与ViewPager组合时，如何在FragmentActicity获取Fragment对象
- iOS开发之NSTimer
- IScroll5不能滑到最底端的解决办法
- Qt文档阅读笔记-QGraphicsItem::paint中QStyleOptionGraphicsItem *option的进一步认识
- 掌上电脑设备可以使用Ubuntu MATE 18.10 Linux映像了
- JsonWebToken
- easyui-datebox 只能获取当前日期以前的日期
- android_serialport_api hacking
- 排查linux下java应用cpu占用过高