0331 _ BinaryTree 배열로 구현하기

이진트리 (Binary Tree)
트리중 자식 노드의 수가 2개 이하인것을 이진트리
이진트리는 구현이 단순하다는 점 비롯하여 여러장점이있다.
이진트리는 한쪽 방향으로 틀어진건 1.사향이진트리
모두 노드들이 자식을 가지고있는건 2.포화이진트리
3.완전이진트리 - 왼쪽부터 자식이 차 잇는거

 

 

--

 

힙 자료구조가 전형적인 완전이진트리에 해당한다. 

이진트리는 일반적으로 연결리스트를 이용하는 방법과
배열을 이용하는 방법이있다.

이진 트리의 노드는 데이타와 좌/우 노드를 갖는 간단한 구조이므로 

Preorder 는 부모노드를 먼저 순회하고, 다음은 왼쪽 서브트리를,
마지막으로 오른쪽 서브트리를 순회하는 방식이다.
ㅂ
배열을 이용한
배열에 이진 트리를 저장하는 방식은 기본적으로 티르 레벨순으로 
레벨 순으로 왼쪽에서 오른쪽으로 저장
배열 A [0] = 루트 1 = 왼쪽 자시 / 2 = 오른쪽 자식노드
3번쨰 인덱스 1번으 ㅣ자식, 

고정 배열의 경우 해당 노드가 없으면 비워둔다.

이진트리 배열에 저장, 공식이있다.

 

---

 

 

1. 배열 생성 // 고정배열

 

2. Root 추가 // 루트는 무조건 0 인덱스에 세팅

 

3. 왼쪽 추가 예외처리전

 

4. 왼쪽 예외 생성

 

 

5. 

 

 

 

 

 

using System;

namespace study18

{
    public class App
    {
        public App()
        {
            Console.WriteLine("App");
            BinaryTreeArray tree = new BinaryTreeArray(8);
            tree.Root = "A";
            tree.SetLeft(0, "B");
            tree.SetRight(0, "C");
            tree.SetLeft(1, "D");
            tree.SetLeft(2, "F");
            tree.Print();
            var parent = tree.GetParent(2);
            Console.WriteLine(parent);
            var left = tree.GetLeft(2);
            Console.WriteLine(left);
        }
    }
}

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

namespace study18
{
    public class BinaryTreeArray
    {
        private string[] arr;
        public string Root
        {
            get
            {
                return this.arr[0];
            }
            set
            {
                this.arr[0] = value;
            }
        }
        //생성자 
        public BinaryTreeArray(int capacity)
        {
            //배열 생성 
            this.arr = new string[capacity];
        }

        //왼쪽추가 
        public void SetLeft(int parentIndex, string data)
        {

            int leftIndex = (parentIndex * 2) + 1;

            //부모가 없거나 배열이 full인경우 
            if (this.arr[parentIndex] == null || leftIndex >= this.arr.Length)
            {
                throw new ApplicationException("Error!");
            }

            this.arr[leftIndex] = data;
        }

        //왼쪽 요소 가져오기 
        public string GetLeft(int parentIndex)
        {
            int leftIndex = (parentIndex * 2) + 1;

            return this.arr[leftIndex];
        }

        //오른쪽 추가 
        public void SetRight(int parentIndex, string data)
        {
            int rightIndex = (parentIndex * 2) + 2;

            //부모가 없거나 배열이 full인경우 
            if (this.arr[parentIndex] == null || rightIndex >= this.arr.Length)
            {
                throw new ApplicationException("Error!");
            }

            this.arr[rightIndex] = data;
        }

        //오른쪽 가져오기 
        public string GetRight(int parentIndex)
        {
            int rightIndex = (parentIndex * 2) + 2;
            return this.arr[rightIndex];
        }

        //부모 요소 가져오기 
        public string GetParent(int childIndex)
        {

            if (childIndex == 0) return null;

            int parentIndex = (childIndex - 1) / 2;
            return this.arr[parentIndex];
        }

        //출력 
        public void Print()
        {
            for (int i = 0; i < this.arr.Length; i++)
            {
                Console.Write("{0}", this.arr[i] ?? "-");
            }
            Console.WriteLine();
        }
    }
}