Mahfuz

Tree traversal adalah cara kunjungan node-node pada pohon biner. Ada tiga cara
kunjungan dalam tree:
• Pre-order
• In-order
• Post-order
1. Pre-order
a. Cetak data pada root
b. Secara rekursif mencetak seluruh data pada subpohon kiri
c. Secara rekursif mencetak seluruh data pada subpohon kanan
2. In-order
a. Secara rekursif mencetak seluruh data pada subpohon kiri
b. Cetak data pada root
c. Secara rekursif mencetak seluruh data pada subpohon kanan
3. Post-order
a. Secara rekursif mencetak seluruh data pada subpohon kiri
b. Secara rekursif mencetak seluruh data pada subpohon kanan
c. Cetak data pada root

Contoh program tree lenjutan:

#include <iostream>
#include <cstdlib>
using namespace std;

class BinaryTree
{
    private:
        struct tree_node
        {
           tree_node* left;
           tree_node* right;
           int data;
        };
        tree_node* root;
   
    public:
        BinaryTree()
        {
           root = NULL;
        }
      
        bool isEmpty() const { return root==NULL; }
        void print_inorder();
        void inorder(tree_node*);
        void print_preorder();
        void preorder(tree_node*);
        void print_postorder();
        void postorder(tree_node*);
        void insert(int);
        void remove(int);
};

// element yang lebih kecil ke kiri
// element yang lebih besar ke kanan
void BinaryTree::insert(int d)
{
    tree_node* t = new tree_node;
    tree_node* parent;
    t->data = d;
    t->left = NULL;
    t->right = NULL;
    parent = NULL;
   
    // merupakan pohon baru (new tree)
    if(isEmpty()) root = t;
    else
    {
        //Catatan: Semua yang dimasukkan adalah sebagai cabang pohon node
        tree_node* curr;
        curr = root;
        // Mencari induknya node
        while(curr)
        {
            parent = curr;
            if(t->data > curr->data) curr = curr->right;
            else curr = curr->left;
        }

        if(t->data < parent->data)
           parent->left = t;
        else
           parent->right = t;
    }
}

void BinaryTree::remove(int d)
{
    //Tempat element
    bool found = false;
    if(isEmpty())
    {
        cout<<" This Tree is empty! "<<endl;
        return;
    }
   
    tree_node* curr;
    tree_node* parent;
    curr = root;
   
    while(curr != NULL)
    {
         if(curr->data == d)
         {
            found = true;
            break;
         }
         else
         {
             parent = curr;
             if(d>curr->data) curr = curr->right;
             else curr = curr->left;
         }
    }
    if(!found)
         {
        cout<<" Data not found! "<<endl;
        return;
    }


         // 3 pilihan :
    // 1. Kita bisa menghapus cabang node (leaf node)
    // 2. Kita bisa menghapus sebuah node dengan satu anaknya
    // 3. Kita bisa menghilangkan sebuah node dengan dua anaknya

    // Node dengan satu anaknya (cabang dari induknya)
    if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL
&& curr->right == NULL))
    {
       if(curr->left == NULL && curr->right != NULL)
       {
           if(parent->left == curr)
           {
             parent->left = curr->right;
             delete curr;
           }
           else
           {
             parent->right = curr->right;
             delete curr;
           }
       }
       else // untuk cabang bagian kiri, bukan untuk cabang bagian kanan
       {
          if(parent->left == curr)
           {
             parent->left = curr->left;
             delete curr;
           }
           else
           {
             parent->right = curr->left;
             delete curr;
           }
       }
     return;
    }

         //Kita bisa melihat pada pohon node (leaf node)
         if( curr->left == NULL && curr->right == NULL)
    {
        if(parent->left == curr) parent->left = NULL;
        else parent->right = NULL;
                  delete curr;
                  return;
    }


    //Node dengan dua anaknya (cabang dari induknya)
    // mengganti atau menempatkan lagi dengan nilai terkecil pada anak pohon bagian kanan
    if (curr->left != NULL && curr->right != NULL)
    {
        tree_node* chkr;
        chkr = curr->right;
        if((chkr->left == NULL) && (chkr->right == NULL))
        {
            curr = chkr;
            delete chkr;
            curr->right = NULL;
        }
        else // anak bagian kanan merupakan anak-anak dari induknnya (children)
        {
            //jika anak kanan node merupakan anak bagian kiri
            //memindahkan semua bagian bawah cabang ke tempat element terkecil

            if((curr->right)->left != NULL)
            {
                tree_node* lcurr;
                tree_node* lcurrp;
                lcurrp = curr->right;
                lcurr = (curr->right)->left;
                while(lcurr->left != NULL)
                {
                   lcurrp = lcurr;
                   lcurr = lcurr->left;
                }
        curr->data = lcurr->data;
                delete lcurr;
                lcurrp->left = NULL;
           }
           else
           {
               tree_node* tmp;
               tmp = curr->right;
               curr->data = tmp->data;
           curr->right = tmp->right;
               delete tmp;
           }

        }
         return;
    }

}

void BinaryTree::print_inorder()
{
  inorder(root);
}

void BinaryTree::inorder(tree_node* p)
{
    if(p != NULL)
    {
        if(p->left) inorder(p->left);
        cout<<" "<<p->data<<" ";
        if(p->right) inorder(p->right);
    }
    else return;
}

void BinaryTree::print_preorder()
{
    preorder(root);
}

void BinaryTree::preorder(tree_node* p)
{
    if(p != NULL)
    {
        cout<<" "<<p->data<<" ";
        if(p->left) preorder(p->left);
        if(p->right) preorder(p->right);
    }
    else return;
}

void BinaryTree::print_postorder()
{
    postorder(root);
}

void BinaryTree::postorder(tree_node* p)
{
    if(p != NULL)
    {
        if(p->left) postorder(p->left);
        if(p->right) postorder(p->right);
        cout<<" "<<p->data<<" ";
    }
    else return;
}

int main()
{
    BinaryTree b;
    int ch,tmp,tmp1;
    while(1)
    {
      cout<<"\n\t\a\a1---Masukan Node Di Sepasang Pohon (Binary Tree)\a\a";
      cout<<"\n\t\a\a2---In-Order Traversal                          \a\a";
      cout<<"\n\t\a\a3---Pre-Order Traversal                         \a\a";
      cout<<"\n\t\a\a4---Post-Order Traversal                        \a\a";
      cout<<"\n\t\a\a5---Delete                                      \a\a";
      cout<<"\n\t\a\a6---Exit                                        \a\a";
      cout<<"\n";
      cout<<"\n";
      cout<<"        Masukkan pilihanmu : ";
      cin>>ch;
      switch(ch)
       {
           case 1 : cout<<" Masukkan Node Di Sepasang Pohon (Binary Tree) : ";
                    cin>>tmp;
                    b.insert(tmp);
                    break;
           case 2 : cout<<endl;
                    cout<<" In-Order Traversal "<<endl;
                    cout<<" -------------------"<<endl;
                    b.print_inorder();
                    break;
           case 3 : cout<<endl;
                    cout<<" Pre-Order Traversal "<<endl;
                    cout<<" -------------------"<<endl;
                    b.print_preorder();
                    break;
           case 4 : cout<<endl;
                    cout<<" Post-Order Traversal "<<endl;
                    cout<<" --------------------"<<endl;
                    b.print_postorder();
                    break;
           case 5 : cout<<" Masukkan data yang dihapus : ";
                    cin>>tmp1;
                    b.remove(tmp1);
                    break;
           case 6 :
                    return 0;
                   
       }
    }
}





Selamat mencoba!!