자료구조 트리(Tree) 정의, LCRS구현

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0

트리 구조 - 위키백과, 우리 모두의 백과사전

트리 구조(tree) : 나무구조, 계층적 자료구조

그래프의 일종이다

그래프 (Graph) : vertex (정점)과 edge (간선)으로 이루어진 자료구조

​

서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.

​

트리에서 최상위 노드를 루트 노드(root node)라고 한다

​

A가 B를 가리킬때 A를 B의 부모노드 (parent node), B를 A의 자식노드(child node) 라고한다

​

형제 노드(sibling node)는 부모가 같은 두 노드이다.

​

자식 노드가 없는 노드를 잎 노드 (leaf node)라고 부른다

​

잎노드가 아닌 노드를 내부 노드(internal node)라고 한다

​

​

노드의 차수(degree)는 자식의 수이다.

​

노드의 깊이(depth):

루트 노드에서 자신까지 가는 경로의 길이,

루트 노드의 깊이는 0,

위에서 아래로 계산,

​

경로의 길이(length)는 경로가 포함하는 방향 간선의 수이다.

​

노드의 레벨(level)는 루트 노드에서 자신까지 가는 경로의 길이 더하기 1이다.

루트 노드의 레벨은 1이다.

​

노드의 높이(height)는 그 노드와 단말 노드 사이의 경로의 최대 길이(간선 수)이다.

​

---

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%8A%B8%EB%A6%AC

이진 트리 - 위키백과, 우리 모두의 백과사전

이진 트리 (binary tree)

각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조

자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다.

---

트리 구현

1.알고리즘

 

 

 

2.순서도

 

 

3.코드화

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

namespace Helloworld1
{
    
    class BinaryTree
    {
        public class Node
        {
            
            public string Data
            {
                get;
                private set;

            }
            string data;
            public Node Left
            {
                get;
                set;
            }
            public Node Right
            {
                get;
                set;
            }
            

            public Node(string data)
            {
                this.Data = data;
            }
        }

        public Node Root
        {
            get;
            private set;
        }
        

        //생성자
        public BinaryTree()
        {

        }

        public Node AddChild(Node root, string data)
        {
            Node node = new Node(data);
            if(root == null)
            {
                root = node;
                return root;
            }
            else
            {
                if(root.Left == null)
                {
                    node.Left = node;
                    return node.Left;
                }
                else
                {
                    if(root.Left.Right == null)
                    {
                        node.Left.Right = node;
                        return node.Left.Right;
                    }
                    else
                    {
                        throw new InvalidOperationException();
                    }
                }
            }
        }
    }
}


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

namespace Helloworld1
{
    class App
    {
        public App()
        {
            BinaryTree bt = new BinaryTree();
            BinaryTree.Node root = bt.AddChild(bt.Root, "A");
            var nodeB = bt.AddChild(root, "B");
            var nodeC = bt.AddChild(root, "C");

            Console.WriteLine("Data: {0}, Left: {1}, Right: {2}", root.Data, root.Left, root.Right);
            Console.WriteLine("Data: {0}, Left: {1}, Right: {2}", nodeB.Data, nodeB.Left, nodeB.Right);
            Console.WriteLine("Data: {0}, Left: {1}, Right: {2}", nodeC.Data, nodeC.Left, nodeC.Right);

        }
    }
}