C \ # 데이터 구조 - 트 리 데이터 구조 트 리
13683 단어 데이터 구조C#나무.DataStructure
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DataStructure
{
public interface ITree<T>
{
T Root(); //
T Parent(T t); // t
T Child(T t, int i); // t i
T RightSibling(T t); // t
bool Insert(T s, T t, int i); // s t i
T Delete(T t, int i); // t i
void Traverse(int TraverseType); //
void Clear(); //
bool IsEmpty(); //
int GetDepth(T t); //
}
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
class CSeqQueue<T>
{
private int maxsize; //
private T[] data; // ,
private int front; //
private int rear; //
public T this[int index]
{
get { return data[index]; }
set { data[index] = value; }
}
//
public int Maxsize
{
get { return maxsize; }
set { maxsize = value; }
}
//
public int Front
{
get { return front; }
set { front = value; }
}
//
public int Rear
{
get { return rear; }
set { rear = value; }
}
public CSeqQueue()
{
}
public CSeqQueue(int size)
{
data = new T[size];
maxsize = size;
front = rear = -1;
}
//
public bool IsFull()
{
if ((front == -1 && rear == maxsize - 1) || (rear + 1) % maxsize == front)
return true;
else
return false;
}
//
public void Clear()
{
front = rear = -1;
}
//
public bool IsEmpty()
{
if (front == rear)
return true;
else
return false;
}
//
public void EnQueue(T elem)
{
if (IsFull())
{
Console.WriteLine("Queue is Full !");
return;
}
rear = (rear + 1) % maxsize;
data[rear] = elem;
}
//
public T DeQueue()
{
if (IsEmpty())
{
Console.WriteLine("Queue is Empty !");
return default(T);
}
front = (front + 1) % maxsize;
return data[front];
}
//
public T GetFront()
{
if (IsEmpty())
{
Console.WriteLine("Queue is Empty !");
return default(T);
}
return data[(front + 1) % maxsize];//front -1
}
//
public int GetLength()
{
return (rear - front + maxsize) % maxsize;
}
}
/// <summary>
///
/// </summary>
/// <typeparam name="T"></typeparam>
class MLNode<T>
{
private T data; //
private MLNode<T>[] childs; //
public MLNode(int max)
{
childs = new MLNode<T>[max];
for (int i = 0; i < childs.Length; i++)
{
childs[i] = null;
}
}
public T Data
{
get { return data; }
set { data = value; }
}
public MLNode<T>[] Childs
{
get { return childs; }
set { childs = value; }
}
}
class MLTree<T> : ITree<MLNode<T>>
{
private MLNode<T> head;
public MLNode<T> Head
{
get { return head; }
set { head = value; }
}
public MLTree()
{
head = null;
}
public MLTree(MLNode<T> node)
{
head = node;
}
//
public MLNode<T> Root()
{
return head;
}
public void Clear()
{
head = null;
}
// !!!
public int GetDepth(MLNode <T> root)
{
int len;
if (root == null)
{
return 0;
}
for (int i = 0; i < root.Childs.Length; i++)
{
if (root.Childs[i] != null)
{
len = GetDepth(root.Childs[i]);
return len + 1;
}
}
return 0;
}
public bool IsEmpty()
{
return head == null;
}
// t , t , ,
//
public MLNode<T> Parent(MLNode<T> t)
{
MLNode<T> temp = head;
if (IsEmpty() || t == null) return null;
if (temp.Data.Equals(t.Data)) return null;
CSeqQueue<MLNode<T>> queue = new CSeqQueue<MLNode<T>>(50);
queue.EnQueue(temp);
while (!queue.IsEmpty())
{
temp = (MLNode<T>)queue.DeQueue();
for (int i = 0; i < temp.Childs.Length; i++)
{
if (temp.Childs[i] != null)
{
if (temp.Childs[i].Data.Equals(t.Data))
{
return temp;
}
else
{
queue.EnQueue(temp.Childs[i]);
}
}
}
}
return null;
}
// t i 。 , i ,
//i=0 ,
public MLNode<T> Child(MLNode<T> t, int i)
{
if (t != null && i < t.Childs.Length)
{
return t.Childs[i];
}
else
{
return null;
}
}
// t , , ,
public MLNode<T> RightSibling(MLNode<T> t)
{
MLNode<T> pt = Parent(t);
if (pt != null)
{
int i = FindRank(t);
return Child(pt, i + 1);
}
else
{
return null;
}
}
// t , , -1
private int FindRank(MLNode<T> t)
{
MLNode<T> pt = Parent(t);
for (int i = 0; i < pt.Childs.Length; i++)
{
MLNode<T> temp = pt.Childs[i];
if (temp != null && temp.Data.Equals(t.Data))
{
return i;
}
}
return -1;
}
// t, t , null
private MLNode<T> FindNode(MLNode<T> t)
{
if (head.Data.Equals(t.Data)) return head;
MLNode<T> pt = Parent(t);
foreach (MLNode<T> temp in pt.Childs)
{
if (temp != null && temp.Data.Equals(t.Data))
{
return temp;
}
}
return null;
}
// s t i 。 true
public bool Insert(MLNode<T> s, MLNode<T> t, int i)
{
if (IsEmpty()) head = t;
t = FindNode(t);
if (t != null && t.Childs.Length > i)
{
t.Childs[i] = s;
return true;
}
else
{
return false;
}
}
// t i 。 i 。
public MLNode<T> Delete(MLNode<T> t, int i)
{
t = FindNode(t);
MLNode<T> node = null;
if (t != null && t.Childs.Length > i)
{
node = t.Childs[i];
t.Childs[i] = null;
}
return node;
}
//
// -> ->
public void preorder(MLNode<T> root)
{
if (root == null)
return;
Console.WriteLine(root.Data + " ");
for (int i = 0; i < root.Childs.Length; i++)
{
preorder(root.Childs[i]);
}
}
//
// -> ->
public void postorder(MLNode<T> root)
{
if (root == null)
{ return; }
for (int i = 0; i < root.Childs.Length; i++)
{
postorder(root.Childs[i]);
}
Console.WriteLine(root.Data + " ");
}
//
//
public void LevelOrder(MLNode<T> root)
{
Console.WriteLine(" :");
if (root == null)
{
Console.WriteLine(" !");
return;
}
MLNode<T> temp = root;
CSeqQueue<MLNode<T>> queue = new CSeqQueue<MLNode<T>>(50);
queue.EnQueue(temp);
while (!queue.IsEmpty())
{
temp = (MLNode<T>)queue.DeQueue();
Console.WriteLine(temp.Data + " ");
for (int i = 0; i < temp.Childs.Length; i++)
{
if (temp.Childs[i] != null)
{
queue.EnQueue(temp.Childs[i]);
}
}
}
Console.WriteLine(" !");
}
//
//0
//1
//2
public void Traverse(int TraverseType)
{
if (TraverseType == 0) preorder(head);
else if (TraverseType == 1) postorder(head);
else LevelOrder(head);
}
}
class Tree
{
static void Main(string[] args)
{
MLTree<string> tree = new MLTree<string>();
char ch;
do
{
Console.WriteLine("1. ");
Console.WriteLine("2. ");
Console.WriteLine("3. ");
Console.WriteLine("4. ");
Console.WriteLine("5. ");
Console.WriteLine();
ch = Convert.ToChar(Console.ReadLine());
switch (ch)
{
case '1':
Console.WriteLine(" :");
string str = Convert.ToString(Console.ReadLine());
MLNode<string> pt = new MLNode<string>(4);
pt.Data = str;
Console.WriteLine(" :");
str = Convert.ToString(Console.ReadLine());
MLNode<string> ct = new MLNode<string>(4);
ct.Data = str;
Console.WriteLine(" :");
int i = Convert.ToInt32(Console.ReadLine());
bool ok = tree.Insert(ct, pt, i);
if (ok)
{
Console.WriteLine(" {0} ", ct.Data);
Console.WriteLine(tree.GetDepth(pt));
}
break;
case '2':
Console.WriteLine(" :");
str = Convert.ToString(Console.ReadLine());
pt = new MLNode<string>(4);
pt.Data = str;
tree.Delete(pt, 0);
break;
case '3':
tree.Traverse(2);
break;
}
} while (ch != '5');
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.