03/31 BinaryTree 배열로 구현하기

 

배열로 이진트리
레벨 순으로 왼쪽에서 오른쪽으로 저장
A[0]는 루트노드

왼쪽추가(부모인덱스, 데이터)
왼쪽노드 계산 : (부모인덱스 * 2) + 1
계산한 인덱스에 데이터 추가

오른쪽추가(부모인덱스, 데이터)
오른쪽노드 계산 : (부모인덱스 * 2) + 1
계산한 인덱스에 데이터 추가

 

Program.cs

using System;

namespace Study09
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Main");
            new App();
        }
    }
}

 

App.cs

using System;

namespace Study09
{

    public class App
    {

        //생성자 
        public App()
        {
            Console.WriteLine("App");
            BinaryTreeArray tree = new BinaryTreeArray(7);
            tree.Root = "A";
            tree.SetLeft(0, "B");
            tree.SetRight(0, "C");
            tree.SetLeft(1, "D");
            tree.SetLeft(2, "F");
            tree.Print();
            var prent = tree.GetParent(5);
            Console.WriteLine("5번째 인덱스의 부모요소 : " + prent);
        }

    }
}

 

BinaryTreeArray.cs

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

namespace Study09
{
    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();
        }
    }
}