이진트리 구현과 순회

#이진트리(Binary)란?

-각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 
자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다.

#노드(Node)
트리를 구성하는 자료
#간선(Edge)
노드를 연결하는 선
#차수?
자식 노드의 수
#높이?
루트에서 해당 노드에 이르는 경로에 있는 간선의 수
#루트 노드?
트리의 시작 노드
#형제 노드?
같은 부모 노드의 자식노드들
#단말 , 리프노드?
자식이 없는 노드

#이진트리의 특징
*n개의 노드를 가진 이진 트리는 항상 (n-1)개의 간선을 갖는다

#이진트리의 순회
*이진트레이 있는 모든 노드를 한번씩 방문하여 노드가 가지고있는 
데이터를 처리하는 것. 선형 자료구조는 순회하는 방법이 하나지만
트리는 계층적인 구조를 가지고 있음으로 여러가지 순회 방법이 있다.

*전위 순회(preorder traverse)-현재노드->Left->Right
*중위 순회(inorder traverse)-Left->현재노드->Righr
*후위 순회(postorder traverse)-Lefr->Right->현재노드

 

#TreeNode구현

class BinaryTree
    {
        public class Node
        {
            public int data; //data
            public Node left;
            public Node right;
            public Node(int data)
            {
                this.data = data;
            }
            public Node rootNode;

#자식노드 추가

public Node()
            {
                Node A = new Node(1); //Root node 
                this.rootNode = A;
                Node B=AddChildNode(A, 2); 
                Node C=AddChildNode(A, 3);
                Node D=AddChildNode(B, 4);
                Node E=AddChildNode(B, 5);
                Node F=AddChildNode(C, 6);
                Node G=AddChildNode(C, 7);
                Node H=AddChildNode(D, 8);
            }
            public Node AddChildNode(Node parent, int data)
            {
                Node childNode = new Node(data);
                if (parent.left == null) //left에 자식노드가 없다면
                {
                    childNode = new Node(data); //data를 가지고있는 childNode 추가
                    parent.left = childNode;
                }
                else if (parent == null) //부모node가 없다면
                {
                    childNode = null; //node를 추가하지 않음
                }
                else if (parent.right == null)//right에 자식노드가 없다면
                {
                    childNode = new Node(data); //data를 가지고있는 childNode 추가
                    parent.right = childNode;
                }
                else
                {
                    childNode = null; //이미 left,right 모두 있다면 추가하지 않는다
                    Console.WriteLine("left,right");
                }
                return childNode;
            }

#순회(전위,중위,후위순회)

//전위 순회 (preorder traverse)
            public void Preorder(Node parent) //parent->left->right
            {
                if(parent!=null) //parent 가 없을때 까지
                {
                    Console.WriteLine("{0}", parent.data);
                    Preorder(parent.left); //재귀함수를 통해 반복
                    Preorder(parent.right);                    
                }
            }

            //중위 순회 (inorder traverse)
            public void Inorder(Node parent) //left->parent->right
            {
                if (parent != null)
                {
                    Inorder(parent.left);
                    Console.WriteLine("{0}", parent.data);
                    Inorder(parent.right);
                }
            }

            //후위 순회 (postorder traverse)
            public void Postorder(Node parent) //left->right->parent
            {
                if (parent != null)
                {
                    Postorder(parent.left);
                    Postorder(parent.right);
                    Console.WriteLine("{0}",parent.data);
                }
            }

#전체코드

using System;
using System.Collections.Generic;
using System.Linq;
using System.Security.Policy;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp19
{
    class BinaryTree
    {
        public class Node
        {
            public int data; //data
            public Node left;
            public Node right;
            public Node(int data)
            {
                this.data = data;
            }
            public Node rootNode;
            //Binary Tree 구현
            //Node추가 메서드 Addchild(Node parent, string data)
            //--------------------------------------------------------------------
            //Node추가(AddChildNode 메서드)

            public Node()
            {
                Node A = new Node(1); //Root node 
                this.rootNode = A;
                Node B=AddChildNode(A, 2); 
                Node C=AddChildNode(A, 3);
                Node D=AddChildNode(B, 4);
                Node E=AddChildNode(B, 5);
                Node F=AddChildNode(C, 6);
                Node G=AddChildNode(C, 7);
                Node H=AddChildNode(D, 8);
            }
            public Node AddChildNode(Node parent, int data)
            {
                Node childNode = new Node(data);
                if (parent.left == null) //left에 자식노드가 없다면
                {
                    childNode = new Node(data); //data를 가지고있는 childNode 추가
                    parent.left = childNode;
                }
                else if (parent == null) //부모node가 없다면
                {
                    childNode = null; //node를 추가하지 않음
                }
                else if (parent.right == null)//right에 자식노드가 없다면
                {
                    childNode = new Node(data); //data를 가지고있는 childNode 추가
                    parent.right = childNode;
                }
                else
                {
                    childNode = null; //이미 left,right 모두 있다면 추가하지 않는다
                    Console.WriteLine("left,right");
                }
                return childNode;
            }

            //-------------------------------------------------------------------
            //BinaryTree 순회

            //전위 순회 (preorder traverse)
            public void Preorder(Node parent) //parent->left->right
            {
                if(parent!=null) //parent 가 없을때 까지
                {
                    Console.WriteLine("{0}", parent.data);
                    Preorder(parent.left); //재귀함수를 통해 반복
                    Preorder(parent.right);                    
                }
            }

            //중위 순회 (inorder traverse)
            public void Inorder(Node parent) //left->parent->right
            {
                if (parent != null)
                {
                    Inorder(parent.left);
                    Console.WriteLine("{0}", parent.data);
                    Inorder(parent.right);
                }
            }

            //후위 순회 (postorder traverse)
            public void Postorder(Node parent) //left->right->parent
            {
                if (parent != null)
                {
                    Postorder(parent.left);
                    Postorder(parent.right);
                    Console.WriteLine("{0}",parent.data);
                }
            }

        }


    }   
}