0402 이진 탐색 트리 재귀 함수로 중위순회

public class BSTNode
    {
        public int data;
        public BSTNode left;
        public BSTNode right;

        //생성자 
        public BSTNode(int data)
        {
            this.data = data;
        }
    }

public class BST
    {
        private BSTNode root;
        public List<BSTNode> ToSortedList()
        {
            //동적 배열 생성 
            List<BSTNode> list = new List<BSTNode>();
            this.Traversal(this.root, list);
            return list;
        }
        public void Add(int data)
        {
            if (this.root == null)
            {
                this.root = new BSTNode(data);
            }
            else
            {
                //변수에 루트 담기 
                var node = this.root;
                //변수의 값이 null아닐때까지 반복 
                while (node != null)
                {

                    //비교 
                    var result = data.CompareTo(node.data);

                    if (result == 0)
                    {
                        //같으면 값이 이미 있음 
                        throw new ApplicationException("duplicated!");
                    }
                    else if (result < 0)
                    {
                        //넣을려고 하는 값이 노드의 값보다 작으면 (왼쪽)

                        if (node.left == null)
                        {
                            //왼쪽에 값이 없으면 새노드 붙이기 
                            node.left = new BSTNode(data);
                            //종료 
                            break;
                        }
                        else
                        {
                            //왼쪽에 값이 있으면 변수에 왼쪽 노드 설정 
                            node = node.left;
                        }
                    }
                    else
                    {
                        //넣으려고 하는 값이 노드의 값보다 크면 (오른쪽)
                        if (node.right == null)
                        {
                            //오른쪽에 없으면 새노드 붙이기 
                            node.right = new BSTNode(data);
                            //종료 
                            break;
                        }
                        else
                        {
                            //오른쪽에 있으면 변수에 오른쪽 노드 설정 
                            node = node.right;
                        }
                    }
                }
            }
        }

        private void Traversal(BSTNode node, List<BSTNode> list)
        {

            if (node == null) return;

            this.Traversal(node.left, list);
            list.Add(node); //중위순회 
            this.Traversal(node.right, list);
        }

        public void Print(List<BSTNode> list)
        {
            foreach (var node in list)
            {
                Console.Write("{0} ", node.data);
            }
            Console.WriteLine();
        }
    }

public class App
    {
        public App()
        {
            Console.WriteLine("App");
            BST bst = new BST();
            bst.Add(30);
            bst.Add(25);
            bst.Add(35);
            bst.Add(21);
            bst.Add(27);
            bst.Add(32);

            var list = bst.ToSortedList();
            bst.Print(list);
        }
    }