C \ # 데이터 구조 - 트 리 데이터 구조 트 리

트 리 (Tree) 는 n (n > = 0) 개의 같은 유형의 데이터 요소 의 유한 집합 입 니 다.트 리 의 데이터 요 소 를 노드 (Node) 라 고 합 니 다.n = 0 의 나 무 를 빈 나무 (Empty Tree) 라 고 합 니 다.n > 0 의 임의의 비 빈 나무 T 는 다음 과 같다. 1. 있 고 하나의 특수 한 결점 만 나무의 뿌리 (Root) 결점 이 라 고 부 르 며 뿌리 는 전구 결점 이 없다.2. n > 1 이면 뿌리 결점 을 제외 하고 나머지 결점 은 m (m > 0) 개의 서로 교차 하지 않 는 집합 T1, T2, T3,... Tm 로 나 뉘 는데 그 중에서 각 집합 Ti (1 < = i < = m) 자 체 는 또 하나의 나무 이다.나무 T1, T2,... Tm 는 이 나무의 자나무 (Subtree) 라 고 부른다.나무의 정 의 를 통 해 알 수 있 듯 이 나무의 정 의 는 재 귀 적 이 고 나무 로 나 무 를 정의 하기 때문에 나무의 많은 연산 은 재 귀 를 사용 했다.나무의 관련 용어 결점 (Node).트 리 의 데이터 요 소 를 나타 내 고 데이터 항목 과 데이터 요소 간 의 관계 로 구성 합 니 다.결점 의 도.결점 이 가지 고 있 는 하위 나무의 개수.나무의 도.나무의 각 결점 도의 최대 치.잎 이 맺히다.도 0 의 결점 을 단말기 결점 이 라 고도 부른다.다른 용 어 는 이 진 트 리 를 참고 합 니 다.다 중 링크 표시 법 으로 트 리 의 각 노드 포인터 필드 의 개 수 는 나무의 도수 와 같 습 니 다.


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');
        }
    }
}

좋은 웹페이지 즐겨찾기