첨부 실행 코드는 나눔고딕코딩 폰트를 사용합니다.
본 블로그는 광고를 포함하고 있습니다.
광고 클릭에서 발생하는 수익금은 모두 블로그 콘텐츠 향상을 위해 쓰여집니다.

728x90
반응형
728x170

TestProject.zip
다운로드

▶ MainForm.cs

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Windows.Forms;

using Lassalle.Flow;
using Lassalle.Flow.Layout.Hierarchic;

namespace TestProject
{
    /// <summary>
    /// 메인 폼
    /// </summary>
    public partial class MainForm : Form
    {
        //////////////////////////////////////////////////////////////////////////////////////////////////// Constructor
        ////////////////////////////////////////////////////////////////////////////////////////// Public

        #region 생성자 - MainForm()

        /// <summary>
        /// 생성자
        /// </summary>
        public MainForm()
        {
            InitializeComponent();

            Load += Form_Load;
        }

        #endregion

        //////////////////////////////////////////////////////////////////////////////////////////////////// Constructor
        ////////////////////////////////////////////////////////////////////////////////////////// Public
        //////////////////////////////////////////////////////////////////////////////// Event

        #region 폼 로드시 처리하기 - Form_Load(sender, e)

        /// <summary>
        /// 폼 로드시 처리하기
        /// </summary>
        /// <param name="sender">이벤트 발생자</param>
        /// <param name="e">이벤트 인자</param>
        private void Form_Load(object sender, EventArgs e)
        {
            AVLTree<TestData> tree = new AVLTree<TestData>();

            for(int i = 0; i < 100; i++)
            {
                TestData testData = new TestData { TestID = i.ToString() };

                tree.Add(testData);
            }

            DrawNodes(tree);

            HFlow hFlow = new HFlow();
            
            hFlow.LayerDistance  = 50;
            hFlow.VertexDistance = 50;
            hFlow.Orientation    = Lassalle.Flow.Layout.Hierarchic.Orientation.North;
            hFlow.LayerWidth     = 0;

            hFlow.Layout(this.addFlow);
        }

        #endregion

        //////////////////////////////////////////////////////////////////////////////// Function

        #region 노드들 그리기 - DrawNodes(tree)

        /// <summary>
        /// 노드들 그리기
        /// </summary>
        /// <param name="tree">트리</param>
        private void DrawNodes(AVLTree<TestData> tree)
        {
            Dictionary<string, AVLTreeNode<TestData>> treeDictionary = new Dictionary<string, AVLTreeNode<TestData>>();

            foreach(TestData testData in tree)
            {
                AVLTreeNode<TestData> treeNode = tree.Find(testData);

                treeDictionary.Add(treeNode.Value.TestID, treeNode);
            }

            Dictionary<string, Node> nodeDictionary = new Dictionary<string, Node>();

            foreach(KeyValuePair<string, AVLTreeNode<TestData>> keyValuePair in treeDictionary)
            {
                AVLTreeNode<TestData> treeNode = keyValuePair.Value;

                Node node = new Node();
                
                node.Text        = treeNode.Value.TestID;
                node.Size        = new SizeF(50, 50);
                node.Tag         = treeNode;
                node.Shape.Style = ShapeStyle.Rectangle;

                this.addFlow.Nodes.Add(node);

                nodeDictionary.Add(treeNode.Value.TestID, node);
            }

            foreach(KeyValuePair<string, AVLTreeNode<TestData>> keyValuePair in treeDictionary)
            {
                AVLTreeNode<TestData> treeNode = keyValuePair.Value;

                Node node = nodeDictionary[treeNode.Value.TestID];

                if(treeNode.LeftChild != null)
                {
                    Node leftChildNode = nodeDictionary[treeNode.LeftChild.Value.TestID];

                    Link link = new Link();

                    link.DrawColor = Color.Blue;
                    link.BackMode  = BackMode.Opaque;

                    node.OutLinks.Add(link, leftChildNode);
                }

                if(treeNode.RightChild != null)
                {
                    Node rightChildNode = nodeDictionary[treeNode.RightChild.Value.TestID];

                    Link link = new Link();

                    link.DrawColor = Color.Blue;
                    link.BackMode  = BackMode.Opaque;

                    node.OutLinks.Add(link, rightChildNode);
                }
            }
        }

        #endregion
    }
}

 

▶ BinaryTreeNode.cs

using System;

namespace TestProject
{
    /// <summary>
    /// 이진 트리 노드
    /// </summary>
    public class BinaryTreeNode<T> where T : IComparable
    {
        //////////////////////////////////////////////////////////////////////////////////////////////////// Field
        ////////////////////////////////////////////////////////////////////////////////////////// Private

        #region Field

        /// <summary>
        /// 값
        /// </summary>
        private T value;

        /// <summary>
        /// 트리
        /// </summary>
        private BinaryTree<T> tree;

        /// <summary>
        /// 부모 노드
        /// </summary>
        private BinaryTreeNode<T> parentNode;

        /// <summary>
        /// 왼쪽 자식 노드
        /// </summary>
        private BinaryTreeNode<T> leftChildNode;

        /// <summary>
        /// 오른쪽 자식 노드
        /// </summary>
        private BinaryTreeNode<T> rightChildNode;

        #endregion

        //////////////////////////////////////////////////////////////////////////////////////////////////// Property
        ////////////////////////////////////////////////////////////////////////////////////////// Public

        #region 값 - Value

        /// <summary>
        /// 값
        /// </summary>
        public virtual T Value
        {
            get
            {
                return this.value;
            }
            set
            {
                this.value = value;
            }
        }

        #endregion

        #region 트리 - Tree

        /// <summary>
        /// 트리
        /// </summary>
        public virtual BinaryTree<T> Tree
        {
            get
            {
                return this.tree;
            }
            set
            {
                this.tree = value;
            }
        }

        #endregion
        #region 부모 노드 - ParentNode

        /// <summary>
        /// 부모 노드
        /// </summary>
        public virtual BinaryTreeNode<T> ParentNode
        {
            get
            {
                return this.parentNode;
            }
            set
            {
                this.parentNode = value;
            }
        }

        #endregion
        #region 왼쪽 자식 노드 - LeftChildNode

        /// <summary>
        /// 왼쪽 자식 노드
        /// </summary>
        public virtual BinaryTreeNode<T> LeftChildNode
        {
            get
            {
                return this.leftChildNode;
            }
            set
            {
                this.leftChildNode = value;
            }
        }

        #endregion
        #region 오른쪽 자식 노드 - RightChildNode

        /// <summary>
        /// 오른쪽 자식 노드
        /// </summary>
        public virtual BinaryTreeNode<T> RightChildNode
        {
            get
            {
                return this.rightChildNode;
            }
            set
            {
                this.rightChildNode = value;
            }
        }

        #endregion

        #region 자식 노드 카운트 - ChildNodeCount

        /// <summary>
        /// 자식 노드 카운트
        /// </summary>
        public virtual int ChildNodeCount
        {
            get
            {
                int childNodeCount = 0;

                if(this.LeftChildNode != null)
                {
                    childNodeCount++;
                }

                if(this.RightChildNode != null)
                {
                    childNodeCount++;
                }

                return childNodeCount;
            }
        }

        #endregion
        
        #region 종말 노드 여부 - IsLeafNode

        /// <summary>
        /// 종말 노드 여부
        /// </summary>
        public virtual bool IsLeafNode
        {
            get
            {
                return ChildNodeCount == 0;
            }
        }

        #endregion
        #region 내부 노드 여부 (자식 노드 존재 여부) - IsInternalNode

        /// <summary>
        /// 내부 노드 여부 (자식 노드 존재 여부)
        /// </summary>
        public virtual bool IsInternalNode
        {
            get
            {
                return ChildNodeCount > 0;
            }
        }

        #endregion
        #region 왼쪽 자식 노드 여부 - IsLeftChildNode

        /// <summary>
        /// 왼쪽 자식 노드 여부
        /// </summary>
        public virtual bool IsLeftChildNode
        {
            get
            {
                return ParentNode != null && ParentNode.LeftChildNode == this;
            }
        }

        #endregion
        #region 오른쪽 자식 노드 여부 - IsRightChildNode

        /// <summary>
        /// 오른쪽 자식 노드 여부
        /// </summary>
        public virtual bool IsRightChildNode
        {
            get
            {
                return ParentNode != null && ParentNode.RightChildNode == this;
            }
        }

        #endregion

        #region 왼쪽 자식 노드 소유 여부 - HasLeftChildNode

        /// <summary>
        /// 왼쪽 자식 노드 소유 여부
        /// </summary>
        public virtual bool HasLeftChildNode
        {
            get
            {
                return (this.LeftChildNode != null);
            }
        }

        #endregion
        #region 오른쪽 자식 노드 소유 여부 - HasRightChildNode

        /// <summary>
        /// 오른쪽 자식 노드 소유 여부
        /// </summary>
        public virtual bool HasRightChildNode
        {
            get
            {
                return (this.RightChildNode != null);
            }
        }

        #endregion

        //////////////////////////////////////////////////////////////////////////////////////////////////// Constructor
        ////////////////////////////////////////////////////////////////////////////////////////// Public

        #region 생성자 - BinaryTreeNode(value)

        /// <summary>
        /// 생성자
        /// </summary>
        public BinaryTreeNode(T value)
        {
            this.value = value;
        }

        #endregion
    }
}

 

▶ BinaryTree.cs

using System;
using System.Collections;
using System.Collections.Generic;

namespace TestProject
{
    /// <summary>
    /// 이진 트리
    /// </summary>
    public class BinaryTree<T> : ICollection<T> where T : IComparable
    {
        //////////////////////////////////////////////////////////////////////////////////////////////////// Class
        ////////////////////////////////////////////////////////////////////////////////////////// Private

        #region 이진 트리 전위 순회 열거자 - BinaryTreePreOrderEnumerator

        /// <summary>
        /// 이진 트리 전위 순회 열거자
        /// </summary>
        private class BinaryTreePreOrderEnumerator : IEnumerator<T>
        {
            //////////////////////////////////////////////////////////////////////////////////////////////////// Field
            ////////////////////////////////////////////////////////////////////////////////////////// Private

            #region Field

            /// <summary>
            /// 이진 트리
            /// </summary>
            private BinaryTree<T> binaryTree;

            /// <summary>
            /// 현재 이진 트리 노드
            /// </summary>
            private BinaryTreeNode<T> currentBinaryTreeNode;

            /// <summary>
            /// 순회 큐
            /// </summary>
            private Queue<BinaryTreeNode<T>> traverseQueue;

            #endregion

            //////////////////////////////////////////////////////////////////////////////////////////////////// Property
            ////////////////////////////////////////////////////////////////////////////////////////// Public

            #region 현재 값 - Current (IEnumerator<T>)

            /// <summary>
            /// 현재 값
            /// </summary>
            public T Current
            {
                get
                {
                    return this.currentBinaryTreeNode.Value;
                }
            }

            #endregion
            #region 현재 값 - IEnumerator.Current

            /// <summary>
            /// 현재 값
            /// </summary>
            object IEnumerator.Current
            {
                get
                {
                    return Current;
                }
            }

            #endregion

            //////////////////////////////////////////////////////////////////////////////////////////////////// Constructor
            ////////////////////////////////////////////////////////////////////////////////////////// Public

            #region 생성자 - BinaryTreePreOrderEnumerator(binaryTree)

            /// <summary>
            /// 생성자
            /// </summary>
            /// <param name="binaryTree">이진 트리</param>
            public BinaryTreePreOrderEnumerator(BinaryTree<T> binaryTree)
            {
                this.binaryTree = binaryTree;

                this.traverseQueue = new Queue<BinaryTreeNode<T>>();

                VisitNode(this.binaryTree.RootNode);
            }

            #endregion

            //////////////////////////////////////////////////////////////////////////////////////////////////// Method
            ////////////////////////////////////////////////////////////////////////////////////////// Public

            #region 리셋하기 - Reset() (IEnumerator<T>)

            /// <summary>
            /// 리셋하기
            /// </summary>
            public void Reset()
            {
                this.currentBinaryTreeNode = null;
            }

            #endregion
            #region 다음으로 이동하기 - MoveNext() (IEnumerator<T>)

            /// <summary>
            /// 다음으로 이동하기
            /// </summary>
            /// <returns>다음 이동 가능 여부</returns>
            public bool MoveNext()
            {
                if(this.traverseQueue.Count > 0)
                {
                    this.currentBinaryTreeNode = this.traverseQueue.Dequeue();
                }
                else
                {
                    this.currentBinaryTreeNode = null;
                }

                return (this.currentBinaryTreeNode != null);
            }

            #endregion
            #region 리소스 해제하기 - Dispose() (IEnumerator<T>)

            /// <summary>
            /// 리소스 해제하기
            /// </summary>
            public void Dispose()
            {
                this.currentBinaryTreeNode = null;

                this.binaryTree = null;
            }

            #endregion

            ////////////////////////////////////////////////////////////////////////////////////////// Private

            #region 노드 방문하기 - VisitNode(binaryTreeNode)

            /// <summary>
            /// 노드 방문하기
            /// </summary>
            /// <param name="binaryTreeNode">이진 트리 노드</param>
            private void VisitNode(BinaryTreeNode<T> binaryTreeNode)
            {
                if(binaryTreeNode == null)
                {
                    return;
                }
                else
                {
                    this.traverseQueue.Enqueue(binaryTreeNode);

                    VisitNode(binaryTreeNode.LeftChildNode);

                    VisitNode(binaryTreeNode.RightChildNode);
                }
            }

            #endregion
        }

        #endregion
        #region 이진 트리 중위 순회 열거자 - BinaryTreeInOrderEnumerator

        /// <summary>
        /// 이진 트리 중위 순회 열거자
        /// </summary>
        private class BinaryTreeInOrderEnumerator : IEnumerator<T>
        {
            //////////////////////////////////////////////////////////////////////////////////////////////////// Field
            ////////////////////////////////////////////////////////////////////////////////////////// Private

            #region Field

            /// <summary>
            /// 이진 트리
            /// </summary>
            private BinaryTree<T> binaryTree;

            /// <summary>
            /// 현재 이진 트리 노드
            /// </summary>
            private BinaryTreeNode<T> currentBinaryTreeNode;

            /// <summary>
            /// 순회 큐
            /// </summary>
            private Queue<BinaryTreeNode<T>> traverseQueue;

            #endregion

            //////////////////////////////////////////////////////////////////////////////////////////////////// Property
            ////////////////////////////////////////////////////////////////////////////////////////// Public

            #region 현재 값 - Current (IEnumerator<T>)

            /// <summary>
            /// 현재 값
            /// </summary>
            public T Current
            {
                get
                {
                    return this.currentBinaryTreeNode.Value;
                }
            }

            #endregion
            #region 현재 값 - IEnumerator.Current

            /// <summary>
            /// 현재 값
            /// </summary>
            object IEnumerator.Current
            {
                get
                {
                    return Current;
                }
            }

            #endregion

            //////////////////////////////////////////////////////////////////////////////////////////////////// Constructor
            ////////////////////////////////////////////////////////////////////////////////////////// Public

            #region 생성자 - BinaryTreeInOrderEnumerator(binaryTree)

            /// <summary>
            /// 생성자
            /// </summary>
            /// <param name="binaryTree">이진 트리</param>
            public BinaryTreeInOrderEnumerator(BinaryTree<T> binaryTree)
            {
                this.binaryTree = binaryTree;

                this.traverseQueue = new Queue<BinaryTreeNode<T>>();

                VisitNode(this.binaryTree.RootNode);
            }

            #endregion

            //////////////////////////////////////////////////////////////////////////////////////////////////// Method
            ////////////////////////////////////////////////////////////////////////////////////////// Public

            #region 리셋하기 - Reset() (IEnumerator<T>)

            /// <summary>
            /// 리셋하기
            /// </summary>
            public void Reset()
            {
                this.currentBinaryTreeNode = null;
            }

            #endregion
            #region 다음으로 이동하기 - MoveNext() (IEnumerator<T>)

            /// <summary>
            /// 다음으로 이동하기
            /// </summary>
            /// <returns>다음 이동 가능 여부</returns>
            public bool MoveNext()
            {
                if(this.traverseQueue.Count > 0)
                {
                    this.currentBinaryTreeNode = this.traverseQueue.Dequeue();
                }
                else
                {
                    this.currentBinaryTreeNode = null;
                }

                return (this.currentBinaryTreeNode != null);
            }

            #endregion
            #region 리소스 해제하기 - Dispose() (IEnumerator<T>)

            /// <summary>
            /// 리소스 해제하기
            /// </summary>
            public void Dispose()
            {
                this.currentBinaryTreeNode = null;

                this.binaryTree = null;
            }

            #endregion

            ////////////////////////////////////////////////////////////////////////////////////////// Private

            #region 노드 방문하기 - VisitNode(binaryTreeNode)

            /// <summary>
            /// 노드 방문하기
            /// </summary>
            /// <param name="binaryTreeNode">이진 트리 노드</param>
            private void VisitNode(BinaryTreeNode<T> binaryTreeNode)
            {
                if(binaryTreeNode == null)
                {
                    return;
                }
                else
                {
                    VisitNode(binaryTreeNode.LeftChildNode);

                    this.traverseQueue.Enqueue(binaryTreeNode);

                    VisitNode(binaryTreeNode.RightChildNode);
                }
            }

            #endregion
        }

        #endregion
        #region 이진 트리 후위 순회 열거자 - BinaryTreePostOrderEnumerator

        /// <summary>
        /// 이진 트리 후위 순회 열거자
        /// </summary>
        private class BinaryTreePostOrderEnumerator : IEnumerator<T>
        {
            //////////////////////////////////////////////////////////////////////////////////////////////////// Field
            ////////////////////////////////////////////////////////////////////////////////////////// Private

            #region Field

            /// <summary>
            /// 이진 트리
            /// </summary>
            private BinaryTree<T> binaryTree;

            /// <summary>
            /// 현재 이진 트리 노드
            /// </summary>
            private BinaryTreeNode<T> currentBinaryTreeNode;

            /// <summary>
            /// 순회 큐
            /// </summary>
            private Queue<BinaryTreeNode<T>> traverseQueue;

            #endregion

            //////////////////////////////////////////////////////////////////////////////////////////////////// Property
            ////////////////////////////////////////////////////////////////////////////////////////// Public

            #region 현재 값 - Current (IEnumerator<T>)

            /// <summary>
            /// 현재 값
            /// </summary>
            public T Current
            {
                get
                {
                    return this.currentBinaryTreeNode.Value;
                }
            }

            #endregion
            #region 현재 값 - IEnumerator.Current

            /// <summary>
            /// 현재 값
            /// </summary>
            object IEnumerator.Current
            {
                get
                {
                    return Current;
                }
            }

            #endregion

            //////////////////////////////////////////////////////////////////////////////////////////////////// Constructor
            ////////////////////////////////////////////////////////////////////////////////////////// Public

            #region 생성자 - BinaryTreePostOrderEnumerator(binaryTree)

            /// <summary>
            /// 생성자
            /// </summary>
            /// <param name="binaryTree">이진 트리</param>
            public BinaryTreePostOrderEnumerator(BinaryTree<T> binaryTree)
            {
                this.binaryTree = binaryTree;

                this.traverseQueue = new Queue<BinaryTreeNode<T>>();

                VisitNode(this.binaryTree.RootNode);
            }

            #endregion

            //////////////////////////////////////////////////////////////////////////////////////////////////// Method
            ////////////////////////////////////////////////////////////////////////////////////////// Public

            #region 리셋하기 - Reset()

            /// <summary>
            /// 리셋하기
            /// </summary>
            public void Reset()
            {
                this.currentBinaryTreeNode = null;
            }

            #endregion
            #region 다음으로 이동하기 - MoveNext() (IEnumerator<T>)

            /// <summary>
            /// 다음으로 이동하기
            /// </summary>
            /// <returns>다음 이동 가능 여부</returns>
            public bool MoveNext()
            {
                if(this.traverseQueue.Count > 0)
                {
                    this.currentBinaryTreeNode = this.traverseQueue.Dequeue();
                }
                else
                {
                    this.currentBinaryTreeNode = null;
                }

                return (this.currentBinaryTreeNode != null);
            }

            #endregion
            #region 리소스 해제하기 - Dispose()

            /// <summary>
            /// 리소스 해제하기
            /// </summary>
            public void Dispose()
            {
                this.currentBinaryTreeNode = null;

                this.binaryTree = null;
            }

            #endregion

            ////////////////////////////////////////////////////////////////////////////////////////// Private

            #region 노드 방문하기 - VisitNode(binaryTreeNode)

            /// <summary>
            /// 노드 방문하기
            /// </summary>
            /// <param name="binaryTreeNode">이진 트리 노드</param>
            private void VisitNode(BinaryTreeNode<T> binaryTreeNode)
            {
                if(binaryTreeNode == null)
                {
                    return;
                }
                else
                {
                    VisitNode(binaryTreeNode.LeftChildNode);

                    VisitNode(binaryTreeNode.RightChildNode);

                    this.traverseQueue.Enqueue(binaryTreeNode);
                }
            }

            #endregion
        }

        #endregion

        //////////////////////////////////////////////////////////////////////////////////////////////////// Field
        ////////////////////////////////////////////////////////////////////////////////////////// Private

        #region Field

        /// <summary>
        /// 비교하기 대리자
        /// </summary>
        private Comparison<IComparable> comparison = CompareNodes;

        /// <summary>
        /// 루트 노드
        /// </summary>
        private BinaryTreeNode<T> rootNode;

        /// <summary>
        /// 카운트
        /// </summary>
        private int count;

        /// <summary>
        /// 탐색 모드
        /// </summary>
        private TraversalMode traversalMode = TraversalMode.InOrder;

        #endregion

        //////////////////////////////////////////////////////////////////////////////////////////////////// Property
        ////////////////////////////////////////////////////////////////////////////////////////// Public

        #region 루트 노드 - RootNode

        /// <summary>
        /// 루트 노드
        /// </summary>
        public virtual BinaryTreeNode<T> RootNode
        {
            get
            {
                return this.rootNode;
            }
            set
            {
                this.rootNode = value;
            }
        }

        #endregion
        #region 읽기 전용 여부 - IsReadOnly (ICollection<T>)

        /// <summary>
        /// 읽기 전용 여부
        /// </summary>
        public virtual bool IsReadOnly
        {
            get
            {
                return false;
            }
        }

        #endregion
        #region 카운트 - Count (ICollection<T>)

        /// <summary>
        /// 카운트
        /// </summary>
        public virtual int Count
        {
            get
            {
                return this.count;
            }
        }

        #endregion
        #region 탐색 모드 - TraversalOrder

        /// <summary>
        /// 탐색 모드
        /// </summary>
        public virtual TraversalMode TraversalMode
        {
            get
            {
                return this.traversalMode;
            }
            set
            {
                this.traversalMode = value;
            }
        }

        #endregion

        //////////////////////////////////////////////////////////////////////////////////////////////////// Constructor
        ////////////////////////////////////////////////////////////////////////////////////////// Public

        #region 생성자 - BinaryTree()

        /// <summary>
        /// 생성자
        /// </summary>
        public BinaryTree()
        {
            this.rootNode = null;
            this.count    = 0;
        }

        #endregion

        //////////////////////////////////////////////////////////////////////////////////////////////////// Method
        ////////////////////////////////////////////////////////////////////////////////////////// Public

        #region 추가하기 - Add(node)

        /// <summary>
        /// 추가하기
        /// </summary>
        /// <param name="node">노드</param>
        public virtual void Add(BinaryTreeNode<T> node)
        {
            if(this.rootNode == null)
            {
                this.rootNode = node;

                node.Tree = this;

                count++;
            }
            else
            {
                if(node.ParentNode == null)
                {
                    node.ParentNode = this.rootNode;
                }

                bool insertLeftSide = comparison((IComparable)node.Value, (IComparable)node.ParentNode.Value) <= 0;

                if(insertLeftSide)
                {
                    if(node.ParentNode.LeftChildNode == null)
                    {
                        node.ParentNode.LeftChildNode = node;

                        count++;

                        node.Tree = this;
                    }
                    else
                    {
                        node.ParentNode = node.ParentNode.LeftChildNode;

                        Add(node);
                    }
                }
                else
                {
                    if(node.ParentNode.RightChildNode == null)
                    {
                        node.ParentNode.RightChildNode = node;

                        count++;

                        node.Tree = this;
                    }
                    else
                    {
                        node.ParentNode = node.ParentNode.RightChildNode;

                        Add(node);
                    }
                }
            }
        }

        #endregion
        #region 추가하기 - Add(value) (ICollection<T>)

        /// <summary>
        /// 추가하기
        /// </summary>
        public virtual void Add(T value)
        {
            BinaryTreeNode<T> node = new BinaryTreeNode<T>(value);

            Add(node);
        }

        #endregion
        #region 찾기 - Find(value)

        /// <summary>
        /// 찾기
        /// </summary>
        /// <param name="value">값</param>
        /// <returns>노드</returns>
        public virtual BinaryTreeNode<T> Find(T value)
        {
            BinaryTreeNode<T> node = this.rootNode;

            while(node != null)
            {
                if(node.Value.Equals(value))
                {
                    return node;
                }
                else
                {
                    bool searchLeft = comparison((IComparable)value, (IComparable)node.Value) < 0;

                    if(searchLeft)
                    {
                        node = node.LeftChildNode;
                    }
                    else
                    {
                        node = node.RightChildNode;
                    }
                }
            }

            return null;
        }

        #endregion
        #region 포함 여부 구하기 - Contains(value) (ICollection<T>)

        /// <summary>
        /// 포함 여부 구하기
        /// </summary>
        public virtual bool Contains(T value)
        {
            return (Find(value) != null);
        }

        #endregion
        #region 제거하기 - Remove(removeNode)

        /// <summary>
        /// 제거하기
        /// </summary>
        /// <param name="removeNode">제거 노드</param>
        /// <returns>처리 결과</returns>
        public virtual bool Remove(BinaryTreeNode<T> removeNode)
        {
            if(removeNode == null || removeNode.Tree != this)
            {
                return false;
            }

            bool wasRootNode = (removeNode == this.rootNode);

            if(this.count == 1) // 노드가 1개만 있는 경우
            {
                this.rootNode = null;

                removeNode.Tree = null;

                this.count--;
            }
            else if(removeNode.IsLeafNode) // 종말 노드인 경우
            {
                if(removeNode.IsLeftChildNode)
                {
                    removeNode.ParentNode.LeftChildNode = null;
                }
                else
                {
                    removeNode.ParentNode.RightChildNode = null;
                }

                removeNode.Tree       = null;
                removeNode.ParentNode = null;

                this.count--;
            }
            else if(removeNode.ChildNodeCount == 1) // 자식 노드가 1개인 경우
            {
                if(removeNode.HasLeftChildNode)
                {
                    #region 제거 노드가 왼쪽 자식 노드를 갖고 있는 경우 처리합니다.

                    removeNode.LeftChildNode.ParentNode = removeNode.ParentNode;

                    if(wasRootNode)
                    {
                        this.RootNode = removeNode.LeftChildNode;
                    }

                    if(removeNode.IsLeftChildNode)
                    {
                        removeNode.ParentNode.LeftChildNode = removeNode.LeftChildNode;
                    }
                    else
                    {
                        removeNode.ParentNode.RightChildNode = removeNode.LeftChildNode;
                    }

                    #endregion
                }
                else
                {
                    #region 제거 노드가 오른쪽 자식 노드를 갖고 있는 경우 처리합니다.

                    removeNode.RightChildNode.ParentNode = removeNode.ParentNode;

                    if(wasRootNode)
                    {
                        this.RootNode = removeNode.RightChildNode;
                    }

                    if(removeNode.IsLeftChildNode)
                    {
                        removeNode.ParentNode.LeftChildNode = removeNode.RightChildNode;
                    }
                    else
                    {
                        removeNode.ParentNode.RightChildNode = removeNode.RightChildNode;
                    }

                    #endregion
                }

                removeNode.Tree           = null;
                removeNode.ParentNode     = null;
                removeNode.LeftChildNode  = null;
                removeNode.RightChildNode = null;

                this.count--;
            }
            else // 자식 노드가 2개인 경우
            {
                BinaryTreeNode<T> successorNode = removeNode.LeftChildNode;

                while(successorNode.RightChildNode != null)
                {
                    successorNode = successorNode.RightChildNode;
                }

                removeNode.Value = successorNode.Value;

                Remove(successorNode);
            }
            
            return true;
        }

        #endregion
        #region 제거하기 - Remove(value) (ICollection<T>)

        /// <summary>
        /// 제거하기
        /// </summary>
        /// <param name="value">값</param>
        /// <returns>처리 결과</returns>
        public virtual bool Remove(T value)
        {
            BinaryTreeNode<T> removeNode = Find(value);

            return Remove(removeNode);
        }

        #endregion
        #region 지우기 - Clear() (ICollection<T>)

        /// <summary>
        /// 지우기
        /// </summary>
        public virtual void Clear()
        {
            IEnumerator<T> enumerator = GetPostOrderEnumerator();

            while(enumerator.MoveNext())
            {
                Remove(enumerator.Current);
            }

            enumerator.Dispose();
        }

        #endregion
        #region 높이 구하기 - GetHeight(startNode)

        /// <summary>
        /// 높이 구하기
        /// </summary>
        /// <param name="startNode">시작 노드</param>
        /// <returns>높이</returns>
        public virtual int GetHeight(BinaryTreeNode<T> startNode)
        {
            if(startNode == null)
            {
                return 0;
            }
            else
            {
                return 1 + Math.Max(GetHeight(startNode.LeftChildNode), GetHeight(startNode.RightChildNode));
            }
        }

        #endregion
        #region 높이 구하기 - GetHeight()

        /// <summary>
        /// 높이 구하기
        /// </summary>
        public virtual int GetHeight()
        {
            return GetHeight(this.rootNode);
        }

        #endregion
        #region 높이 구하기 - GetHeight(value)

        /// <summary>
        /// 높이 구하기
        /// </summary>
        /// <param name="value">값</param>
        /// <returns>높이</returns>
        public virtual int GetHeight(T value)
        {
            BinaryTreeNode<T> node = this.Find(value);

            if(value != null)
            {
                return GetHeight(node);
            }
            else
            {
                return 0;
            }
        }

        #endregion
        #region 깊이 구하기 - GetDepth(startNode)

        /// <summary>
        /// 깊이 구하기
        /// </summary>
        /// <param name="startNode">시작 노드</param>
        /// <returns>깊이</returns>
        public virtual int GetDepth(BinaryTreeNode<T> startNode)
        {
            int depth = 0;

            if(startNode == null)
            {
                return depth;
            }

            BinaryTreeNode<T> parentNode = startNode.ParentNode;

            while(parentNode != null)
            {
                depth++;

                parentNode = parentNode.ParentNode;
            }

            return depth;
        }

        #endregion
        #region 깊이 구하기 - GetDepth(value)

        /// <summary>
        /// 깊이 구하기
        /// </summary>
        public virtual int GetDepth(T value)
        {
            BinaryTreeNode<T> node = this.Find(value);

            return GetDepth(node);
        }

        #endregion
        #region IN-ORDER 열거자 구하기 - GetInOrderEnumerator()

        /// <summary>
        /// IN-ORDER 열거자 구하기
        /// </summary>
        public virtual IEnumerator<T> GetInOrderEnumerator()
        {
            return new BinaryTreeInOrderEnumerator(this);
        }

        #endregion
        #region POST-ORDER 열거자 구하기 - GetPostOrderEnumerator()

        /// <summary>
        /// POST-ORDER 열거자 구하기
        /// </summary>
        public virtual IEnumerator<T> GetPostOrderEnumerator()
        {
            return new BinaryTreePostOrderEnumerator(this);
        }

        #endregion
        #region PRE-ORDER 열거자 구하기 - GetPreOrderEnumerator()

        /// <summary>
        /// PRE-ORDER 열거자 구하기
        /// </summary>
        /// <returns>PRE-ORDER 열거자</returns>
        public virtual IEnumerator<T> GetPreOrderEnumerator()
        {
            return new BinaryTreePreOrderEnumerator(this);
        }

        #endregion
        #region 열거자 구하기 - GetEnumerator() (IEnumerable<T>)

        /// <summary>
        /// 열거자 구하기
        /// </summary>
        /// <returns>열거자 인터페이스</returns>
        public virtual IEnumerator<T> GetEnumerator()
        {
            switch(this.traversalMode)
            {
                case TraversalMode.InOrder   : return GetInOrderEnumerator();
                case TraversalMode.PostOrder : return GetPostOrderEnumerator();
                case TraversalMode.PreOrder  : return GetPreOrderEnumerator();
                default                      : return GetInOrderEnumerator();
            }
        }

        #endregion
        #region IEnumerable - IEnumerable.GetEnumerator() (IEnumerable)

        /// <summary>
        /// 열거자 구하기
        /// </summary>
        /// <returns>열거자 인터페이스</returns>
        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        #endregion
        #region 복사하기 - CopyTo(array) (ICollection<T>)

        /// <summary>
        /// 복사하기
        /// </summary>
        public virtual void CopyTo(T[] array)
        {
            CopyTo(array, 0);
        }

        #endregion
        #region 복사하기 - CopyTo(array, startIndex)

        /// <summary>
        /// 복사하기
        /// </summary>
        /// <param name="array">배열</param>
        /// <param name="startIndex">시작 인덱스</param>
        public virtual void CopyTo(T[] array, int startIndex)
        {
            IEnumerator<T> enumerator = this.GetEnumerator();

            for(int i = startIndex; i < array.Length; i++)
            {
                if(enumerator.MoveNext())
                {
                    array[i] = enumerator.Current;
                }
                else
                {
                    break;
                }
            }
        }

        #endregion
        #region 노드들 비교하기 - CompareNodes(xComparable, yComparable)

        /// <summary>
        /// 노드들 비교하기
        /// </summary>
        /// <param name="xComparable">X 비교 가능자</param>
        /// <param name="yComparable">Y 비교 가능자</param>
        /// <returns>노드들 비교 결과</returns>
        public static int CompareNodes(IComparable xComparable, IComparable yComparable)
        {
            return xComparable.CompareTo(yComparable);
        }

        #endregion
    }
}

 

▶ AVLTreeNode.cs

using System;

namespace TestProject
{
    /// <summary>
    /// AVL 트리 노드
    /// </summary>
    /// <typeparam name="T">타입</typeparam>
    public class AVLTreeNode<T> : BinaryTreeNode<T> where T : IComparable
    {
        //////////////////////////////////////////////////////////////////////////////////////////////////// Property
        ////////////////////////////////////////////////////////////////////////////////////////// Public

        #region 부모 노드 - Parent

        /// <summary>
        /// 부모 노드
        /// </summary>
        public AVLTreeNode<T> Parent
        {
            get
            {
                return (AVLTreeNode<T>)base.ParentNode;
            }
            set
            {
                base.ParentNode = value;
            }
        }

        #endregion
        #region 왼쪽 자식 노드 - LeftChild

        /// <summary>
        /// 왼쪽 자식 노드
        /// </summary>
        public AVLTreeNode<T> LeftChild
        {
            get
            {
                return (AVLTreeNode<T>)base.LeftChildNode;
            }
            set
            {
                base.LeftChildNode = value;
            }
        }

        #endregion
        #region 오른쪽 자식 노드 - RightChild

        /// <summary>
        /// 오른쪽 자식 노드
        /// </summary>
        public AVLTreeNode<T> RightChild
        {
            get
            {
                return (AVLTreeNode<T>)base.RightChildNode;
            }
            set
            {
                base.RightChildNode = value;
            }
        }

        #endregion

        //////////////////////////////////////////////////////////////////////////////////////////////////// Constructor
        ////////////////////////////////////////////////////////////////////////////////////////// Public

        #region 생성자 - AVLTreeNode(value)

        /// <summary>
        /// 생성자
        /// </summary>
        /// <param name="value">값</param>
        public AVLTreeNode(T value) : base(value)
        {
        }

        #endregion
    }
}

 

▶ AVLTree.cs

using System;

namespace TestProject
{
    /// <summary>
    /// AVL 트리
    /// </summary>
    public class AVLTree<T> : BinaryTree<T> where T : IComparable
    {
        //////////////////////////////////////////////////////////////////////////////////////////////////// Property
        ////////////////////////////////////////////////////////////////////////////////////////// Public

        #region 루트 노드 - Root

        /// <summary>
        /// 루트 노드
        /// </summary>
        public AVLTreeNode<T> Root
        {
            get
            {
                return (AVLTreeNode<T>)base.RootNode;
            }
            set
            {
                base.RootNode = value;
            }
        }

        #endregion

        //////////////////////////////////////////////////////////////////////////////////////////////////// Method
        ////////////////////////////////////////////////////////////////////////////////////////// Public

        #region 찾기 - Find(value)

        /// <summary>
        /// 찾기
        /// </summary>
        /// <param name="value">값</param>
        /// <returns>AVL 트리 노드</returns>
        public new AVLTreeNode<T> Find(T value)
        {
            return (AVLTreeNode<T>)base.Find(value);
        }

        #endregion
        #region 추가하기 - Add(value)

        /// <summary>
        /// 추가하기
        /// </summary>
        /// <param name="value">값</param>
        public override void Add(T value)
        {
            AVLTreeNode<T> node = new AVLTreeNode<T>(value);

            base.Add(node);

            AVLTreeNode<T> parentNode = node.Parent;

            while(parentNode != null)
            {
                int balance = GetBalance(parentNode);

                if(Math.Abs(balance) == 2)
                {
                    BalanceAt(parentNode, balance);
                }

                parentNode = parentNode.Parent;
            }
        }

        #endregion
        #region 제거하기 - Remove(node)

        /// <summary>
        /// 제거하기
        /// </summary>
        /// <param name="node">노드</param>
        /// <returns>처리 결과</returns>
        public bool Remove(AVLTreeNode<T> node)
        {
            AVLTreeNode<T> parentNode = node.Parent;

            bool removed = base.Remove(node);

            if(!removed)
            {
                return false;
            }
            else
            {
                while(parentNode != null)
                {
                    int balance = GetBalance(parentNode);

                    if(Math.Abs(balance) == 1)
                    {
                        break;
                    }
                    else if(Math.Abs(balance) == 2)
                    {
                        BalanceAt(parentNode, balance);
                    }

                    parentNode = parentNode.Parent;
                }

                return true;
            }
        }

        #endregion
        #region 제거하기 - Remove(value)

        /// <summary>
        /// 제거하기
        /// </summary>
        public override bool Remove(T value)
        {
            AVLTreeNode<T> node = Find(value);

            return Remove(node);
        }

        #endregion

        ////////////////////////////////////////////////////////////////////////////////////////// Protected

        #region 제거하기 - Remove(node)

        /// <summary>
        /// 제거하기
        /// </summary>
        /// <param name="node">노드</param>
        /// <returns>처리 결과</returns>
        protected new bool Remove(BinaryTreeNode<T> node)
        {
            return Remove((AVLTreeNode<T>)node);
        }

        #endregion
        #region 밸런스 구하기 - GetBalance(rootNode)

        /// <summary>
        /// 밸런스 구하기
        /// </summary>
        /// <param name="rootNode">루트 노드</param>
        /// <returns>밸런스</returns>
        protected virtual int GetBalance(AVLTreeNode<T> rootNode)
        {
            return GetHeight(rootNode.RightChild) - GetHeight(rootNode.LeftChild);
        }

        #endregion
        #region 왼쪽으로 노드 회전하기 - RotateLeft(rootNode)

        /// <summary>
        /// 왼쪽으로 노드 회전하기
        /// </summary>
        protected virtual void RotateLeft(AVLTreeNode<T> rootNode)
        {
            if(rootNode == null)
            {
                return;
            }

            AVLTreeNode<T> pivotNode = rootNode.RightChild;

            if(pivotNode == null)
            {
                return;
            }
            else
            {
                AVLTreeNode<T> rootParentNode = rootNode.Parent;

                bool isLeftChild = (rootParentNode != null) && (rootParentNode.LeftChild == rootNode);

                bool makeTreeRoot = (rootNode.Tree.RootNode == rootNode);

                rootNode.RightChild = pivotNode.LeftChild;

                pivotNode.LeftChild = rootNode;

                rootNode.Parent = pivotNode;

                pivotNode.Parent = rootParentNode;

                if(rootNode.RightChild != null)
                {
                    rootNode.RightChild.Parent = rootNode;
                }

                if(makeTreeRoot)
                {
                    pivotNode.Tree.RootNode = pivotNode;
                }

                if(isLeftChild)
                {
                    rootParentNode.LeftChild = pivotNode;
                }
                else if(rootParentNode != null)
                {
                    rootParentNode.RightChild = pivotNode;
                }
            }
        }

        #endregion
        #region 오른쪽으로 노드 회전하기 - RotateRight(rootNode)

        /// <summary>
        /// 오른쪽으로 노드 회전하기
        /// </summary>
        /// <param name="rootNode">루트 노드</param>
        protected virtual void RotateRight(AVLTreeNode<T> rootNode)
        {
            if(rootNode == null)
            {
                return;
            }

            AVLTreeNode<T> pivotNode = rootNode.LeftChild;

            if(pivotNode == null)
            {
                return;
            }
            else
            {
                AVLTreeNode<T> rootParentNode = rootNode.Parent;

                bool isLeftChild = (rootParentNode != null) && (rootParentNode.LeftChild == rootNode);

                bool makeTreeRoot = (rootNode.Tree.RootNode == rootNode);

                rootNode.LeftChild = pivotNode.RightChild;

                pivotNode.RightChild = rootNode;

                rootNode.Parent = pivotNode;

                pivotNode.Parent = rootParentNode;

                if(rootNode.LeftChild != null)
                {
                    rootNode.LeftChild.Parent = rootNode;
                }

                if(makeTreeRoot)
                {
                    pivotNode.Tree.RootNode = pivotNode;
                }

                if(isLeftChild)
                {
                    rootParentNode.LeftChild = pivotNode;
                }
                else if(rootParentNode != null)
                {
                    rootParentNode.RightChild = pivotNode;
                }
            }
        }

        #endregion
        #region 균형잡기 - BalanceAt(node, balance)

        /// <summary>
        /// 균형잡기
        /// </summary>
        protected virtual void BalanceAt(AVLTreeNode<T> node, int balance)
        {
            if(balance == 2)
            {
                int rightBalance = GetBalance(node.RightChild);

                if(rightBalance == 1 || rightBalance == 0)
                {
                    RotateLeft(node);
                }
                else if(rightBalance == -1)
                {
                    RotateRight(node.RightChild);

                    RotateLeft(node);
                }
            }
            else if(balance == -2)
            {
                int leftBalance = GetBalance(node.LeftChild);

                if(leftBalance == 1)
                {
                    RotateLeft(node.LeftChild);

                    RotateRight(node);
                }
                else if(leftBalance == -1 || leftBalance == 0)
                {
                    RotateRight(node);
                }
            }
        }

        #endregion
    }
}
728x90
반응형
그리드형(광고전용)
Posted by 사용자 icodebroker

댓글을 달아 주세요