İkili Ağaçlar(Binary Tree)

Öncelikle bazı terimlerden bahsetmek istiyorum.

Kök- Yukarıdaki resimde görüldüğü gibi ağaç yapımızda tüm elemanlar aslında tek bir yere bağlı. Buna kök diyoruz.

Çocuk ve ebeveyn- Kök hariç her düğümün bir ebeveyni vardır.

Yaprak-Çocuğu olmaya düğümlere denir. 3-7-10 gibi

Kardeş-Ebeveyni aynı olan düğümlerdir.

İkili Ağaçların özellikleri

• Hiçbir düğümün ikiden fazla çocuğu olamaz.
• Ortalama bir ağacın derinliği(kökten düğüme olan yolun uzunluğu) N’den küçüktür. En kötü durumda N-1 olur.

Ağaç Gezme

Önce kök gezme(pre-order traversar)

• Kökteki veriyi yaz
• Sol altağaçtaki veriyi iteratif olarak yaz
• Sağ altağaçtaki veriyi iteratif olarak yaz

 Çıktı: ++a*bc*+*defg

Sonra kök gezme(post-order traversar)

• Sol altağaçtaki veriyi iteratif olarak yaz
• Sağ altağaçtaki veriyi iteratif olarak yaz
• Kökteki veriyi yaz

Çıktı: abc*+de*f+g*+

İç kök gezme(in-order traversar)

• Sol altağaçtaki veriyi iteratif olarak yaz
• Kökteki veriyi yaz
• Sağ altağaçtaki veriyi iteratif olarak yaz

Çıktı: a+b*c+d*e+f*g

Ayrıca iç kök gezme işlemi ile sayıları da sıralamış oluruz.

namespace binaryTree
{
    class TreeNode
    {
        private TreeNode solDugum;
        private TreeNode sagDugum;
        private int data;

        #region
        public TreeNode SolDugum
        {
            get
            {
                return solDugum;
            }

            set
            {
                solDugum = value;
            }
        }

        public TreeNode SagDugum
        {
            get
            {
                return sagDugum;
            }

            set
            {
                sagDugum = value;
            }
        }

        public int Data
        {
            get
            {
                return data;
            }

            set
            {
                data = value;
            }
        }
        #endregion



        //node constructor
        public TreeNode(int dugumDatasi)
        {
            data = dugumDatasi;
            SagDugum = null; //ilk oluşturduğumuzda sag ve sol dugumleri yok
            SolDugum = null;
        }

        public void Ekle(int eklenecekData)
        {
            //eğer eklenecek data kendi datadan küçük ise sola ekle
            if (eklenecekData < data)
            {
                if (solDugum == null)
                    solDugum = new TreeNode(eklenecekData);
                else
                    solDugum.Ekle(eklenecekData);
            }
            //eğer eklenecek data kendi datadan büyük ise sağa ekle
            else if (eklenecekData > data)
            {
                if (sagDugum == null)
                    sagDugum = new TreeNode(eklenecekData);
                else
                    sagDugum.Ekle(eklenecekData);
            }
            
        }


    }
}

using System;

namespace binaryTree
{
    public class Agac
    {
        private TreeNode kok;

        public Agac()
        {
            kok = null; //ağaç ilk oluşturulduğunda kökü boş olacak 
        }

        public void DugumEkle(int eklenecekDeger)
        {
            lock (this)
            {
                if (kok == null)
                    kok = new TreeNode(eklenecekDeger);
                else
                    kok.Ekle(eklenecekDeger);
            }
        }

        public void OnceKokGezme()
        {
            lock (this)
            {
                OnceKokGezmeHelper(kok);
            }
        }

        private void OnceKokGezmeHelper(TreeNode kok)
        {
            if (kok == null)
                return;

            Console.Write(kok.Data + " ");

            OnceKokGezmeHelper(kok.SolDugum);
            OnceKokGezmeHelper(kok.SagDugum);
        }

        public void IcKokGezme()
        {
            lock (this)
            {
                IcKokGezmeHelper(kok);
            }
        }


        private void IcKokGezmeHelper(TreeNode kok)
        {
            if (kok == null)
                return ;

            IcKokGezmeHelper(kok.SolDugum);
            Console.Write(kok.Data + " ");
            IcKokGezmeHelper(kok.SagDugum);
        }




        public void SonraKokGezme()
        {
            lock (this)
            {
                SonraKokGezmeHelper(kok);
            }
        }



        private void SonraKokGezmeHelper(TreeNode kok)
        {
            if (kok == null)
                return;
            SonraKokGezmeHelper(kok.SolDugum);
            SonraKokGezmeHelper(kok.SagDugum);
            Console.Write(kok.Data + " ");
        }
    }
}

using System;

namespace binaryTree
{
    class Program
    {
        static void Main()
        {
            Agac agac = new Agac();
            int eklenecekDeger;

            Random random = new Random();


            for (int i = 0; i <= 20; i++)
            {
                eklenecekDeger = random.Next(1000);
                Console.Write(eklenecekDeger + " ");
                agac.DugumEkle(eklenecekDeger);
            }


            Console.WriteLine("\nOnce kok Gezme");
            agac.OnceKokGezme();


            Console.WriteLine("\nSonra kok Gezme");
            agac.SonraKokGezme();


            Console.WriteLine("\nİç kok Gezme");
            agac.IcKokGezme();

          
        }
    }
}

Çıktı: