c\#이 진 트 리 의 실현
15241 단어 c#이 진 트 리 구현
NET/C\#의 각종 집합 류 는 이미 가장 좋 은 정렬 설 계 를 실 현 했 지만 기본 적 인 알고리즘 을 이해 하 는 것 은 소프트웨어 개발 의 각종 균형 과 선택 에 도움 이 된다.예 를 들 어 B+트 리 정렬 과 검색 을 실현 하고 트 리 노드 를 바 이 너 리 파일 블록 으로 정렬 하면 각종 데이터 베이스 색인 의 기본 설 계 를 이미 알 고 있 을 것 이다.
이 진 트 리 는 무엇 입 니까?http://en.wikipedia.org/wiki/Binary_tree
이 진 트 리 노드 류 정의
View Code
/// <summary>
///
/// </summary>
/// <typeparam name="T">The item type</typeparam>
public class BinaryTreeNode<T>
{
#region Constructors
/// <summary>
///
/// </summary>
public BinaryTreeNode()
{
}
/// <summary>
///
/// </summary>
/// <param name="value"> </param>
public BinaryTreeNode(T value)
{
this.Value = value;
}
/// <summary>
///
/// </summary>
/// <param name="value"> </param>
/// <param name="parent"> </param>
public BinaryTreeNode(T value, BinaryTreeNode<T> parent)
{
this.Value = value;
this.Parent = parent;
}
/// <summary>
///
/// </summary>
/// <param name="value"> </param>
/// <param name="parent"> </param>
/// <param name="left"> </param>
/// <param name="right"> </param>
public BinaryTreeNode(T value,
BinaryTreeNode<T> parent,
BinaryTreeNode<T> left,
BinaryTreeNode<T> right)
{
this.Value = value;
this.Right = right;
this.Left = left;
this.Parent = parent;
}
#endregion
#region Properties
/// <summary>
///
/// </summary>
public T Value { get; set; }
/// <summary>
///
/// </summary>
public BinaryTreeNode<T> Parent { get; set; }
/// <summary>
///
/// </summary>
public BinaryTreeNode<T> Left { get; set; }
/// <summary>
///
/// </summary>
public BinaryTreeNode<T> Right { get; set; }
/// <summary>
///
/// </summary>
public bool IsRoot { get { return Parent == null; } }
/// <summary>
///
/// </summary>
public bool IsLeaf { get { return Left == null && Right == null; } }
/// <summary>
///
/// </summary>
internal bool Visited { get; set; }
#endregion
#region Public Overridden Functions
/// <summary>
/// Returns a <see cref="System.String"/> that represents this instance.
/// </summary>
/// <returns>
/// A <see cref="System.String"/> that represents this instance.
/// </returns>
public override string ToString()
{
return Value.ToString();
}
#endregion
}
View Code
/// <summary>
///
/// </summary>
/// <typeparam name="T"> </typeparam>
[SuppressMessage("Microsoft.Naming", "CA1710:IdentifiersShouldHaveCorrectSuffix")]
public class BinaryTree<T> : ICollection<T>, IEnumerable<T> where T : IComparable<T>
{
#region Constructor
/// <summary>
///
/// </summary>
public BinaryTree()
{
NumberOfNodes = 0;
}
/// <summary>
///
/// </summary>
/// <param name="root"> </param>
public BinaryTree(BinaryTreeNode<T> root)
: this()
{
this.Root = root;
}
#endregion
#region Properties
/// <summary>
///
/// </summary>
public BinaryTreeNode<T> Root { get; set; }
/// <summary>
///
/// </summary>
protected int NumberOfNodes { get; set; }
/// <summary>
///
/// </summary>
public bool IsEmpty { get { return Root == null; } }
/// <summary>
///
/// </summary>
public T MinValue
{
get
{
if (IsEmpty)
return default(T);
BinaryTreeNode<T> minNode = Root;
while (minNode.Left != null)
minNode = minNode.Left;
return minNode.Value;
}
}
/// <summary>
///
/// </summary>
public T MaxValue
{
get
{
if (IsEmpty)
return default(T);
BinaryTreeNode<T> maxNode = Root;
while (maxNode.Right != null)
maxNode = maxNode.Right;
return maxNode.Value;
}
}
#endregion
#region IEnumerable<T> Members
/// <summary>
/// Returns an enumerator that iterates through the collection.
/// </summary>
/// <returns>
/// A <see cref="T:System.Collections.Generic.IEnumerator`1"></see>
/// that can be used to iterate through the collection.
/// </returns>
public IEnumerator<T> GetEnumerator()
{
foreach (BinaryTreeNode<T> node in Traverse(Root))
{
yield return node.Value;
}
}
#endregion
#region IEnumerable Members
/// <summary>
/// Returns an enumerator that iterates through a collection.
/// </summary>
/// <returns>
/// An <see cref="T:System.Collections.IEnumerator"/>
/// object that can be used to iterate through the collection.
/// </returns>
IEnumerator IEnumerable.GetEnumerator()
{
foreach (BinaryTreeNode<T> node in Traverse(Root))
{
yield return node.Value;
}
}
#endregion
#region ICollection<T> Members
/// <summary>
///
/// </summary>
/// <param name="item">The object to add to the
/// <see cref="T:System.Collections.Generic.ICollection`1"></see>.</param>
/// <exception cref="T:System.NotSupportedException">The
/// <see cref="T:System.Collections.Generic.ICollection`1"></see>
/// is read-only.</exception>
public void Add(T item)
{
if (Root == null)
{
Root = new BinaryTreeNode<T>(item);
++NumberOfNodes;
}
else
{
Insert(item);
}
}
/// <summary>
///
/// </summary>
public void Clear()
{
Root = null;
}
/// <summary>
///
/// </summary>
/// <param name="item">The object to locate in the
/// <see cref="T:System.Collections.Generic.ICollection`1"></see>.</param>
/// <returns>
/// true if item is found in the
/// <see cref="T:System.Collections.Generic.ICollection`1"></see>; otherwise, false.
/// </returns>
public bool Contains(T item)
{
if (IsEmpty)
return false;
BinaryTreeNode<T> currentNode = Root;
while (currentNode != null)
{
int comparedValue = currentNode.Value.CompareTo(item);
if (comparedValue == 0)
return true;
else if (comparedValue < 0)
currentNode = currentNode.Left;
else
currentNode = currentNode.Right;
}
return false;
}
/// <summary>
///
/// </summary>
/// <param name="array">The array.</param>
/// <param name="arrayIndex">Index of the array.</param>
public void CopyTo(T[] array, int arrayIndex)
{
T[] tempArray = new T[NumberOfNodes];
int counter = 0;
foreach (T value in this)
{
tempArray[counter] = value;
++counter;
}
Array.Copy(tempArray, 0, array, arrayIndex, Count);
}
/// <summary>
///
/// </summary>
public int Count
{
get { return NumberOfNodes; }
}
/// <summary>
///
/// </summary>
public bool IsReadOnly
{
get { return false; }
}
/// <summary>
///
/// </summary>
/// <param name="item"> </param>
/// <returns> </returns>
public bool Remove(T item)
{
BinaryTreeNode<T> node = Find(item);
if (node == null)
return false;
List<T> values = new List<T>();
foreach (BinaryTreeNode<T> l in Traverse(node.Left))
{
values.Add(l.Value);
}
foreach (BinaryTreeNode<T> r in Traverse(node.Right))
{
values.Add(r.Value);
}
if (node.Parent.Left == node)
{
node.Parent.Left = null;
}
else
{
node.Parent.Right = null;
}
node.Parent = null;
foreach (T v in values)
{
this.Add(v);
}
return true;
}
#endregion
#region Private Functions
/// <summary>
///
/// </summary>
/// <param name="value"> </param>
/// <returns>
///
/// </returns>
protected BinaryTreeNode<T> Find(T value)
{
foreach (BinaryTreeNode<T> node in Traverse(Root))
if (node.Value.Equals(value))
return node;
return null;
}
/// <summary>
///
/// </summary>
/// <param name="node"> </param>
/// <returns>
/// The individual items from the tree
/// </returns>
[SuppressMessage("Microsoft.Design", "CA1006:DoNotNestGenericTypesInMemberSignatures")]
protected IEnumerable<BinaryTreeNode<T>> Traverse(BinaryTreeNode<T> node)
{
//
if (node.Left != null)
{
foreach (BinaryTreeNode<T> left in Traverse(node.Left))
yield return left;
}
// , ， ，
yield return node;
//
if (node.Right != null)
{
foreach (BinaryTreeNode<T> right in Traverse(node.Right))
yield return right;
}
}
/// <summary>
///
/// </summary>
/// <param name="value"> </param>
protected void Insert(T value)
{
//
BinaryTreeNode<T> currentNode = Root;
while (true)
{
if (currentNode == null)
throw new InvalidProgramException("The current tree node cannot be null.");
//
int comparedValue = currentNode.Value.CompareTo(value);
if (comparedValue < 0)
{
//
if (currentNode.Left == null)
{
currentNode.Left = new BinaryTreeNode<T>(value, currentNode);
++NumberOfNodes;
return;
}
else
{
currentNode = currentNode.Left;
}
}
else if (comparedValue > 0)
{
//
if (currentNode.Right == null)
{
currentNode.Right = new BinaryTreeNode<T>(value, currentNode);
++NumberOfNodes;
return;
}
else
{
currentNode = currentNode.Right;
}
}
else
{
//
currentNode = currentNode.Right;
}
}
}
#endregion
}
class Program
{
static void Main(string[] args)
{
Console.ForegroundColor = ConsoleColor.Green;
BinaryTree<string> tree = new BinaryTree<string>();
tree.Add("Dennis");
tree.Add("Gao");
tree.Add("Is");
tree.Add("A");
tree.Add("C#");
tree.Add("Programmer");
Console.WriteLine("Root Node Is : " + tree.Root.ToString());
Console.WriteLine();
foreach (var node in tree)
{
Console.WriteLine(node);
}
Console.ReadKey();
}
}
중 서 는 이 진 트 리 를 옮 겨 다 닌 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
C#Task를 사용하여 비동기식 작업을 수행하는 방법라인이 완성된 후에 이 라인을 다시 시작할 수 없습니다.반대로 조인(Join)만 결합할 수 있습니다 (프로세스가 현재 라인을 막습니다). 임무는 조합할 수 있는 것이다. 연장을 사용하여 그것들을 한데 연결시키는 것이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
