contoh program tree

#include <iostream.h>
// exception classes for various error types

#ifndef Xcept_
#define Xcept_

#include <except.h>
#include <new.h>

// bad initializers
class BadInitializers {
public:
BadInitializers() {}
};

// insufficient memory
class NoMem {
public:
NoMem() {}
};

// change new to throw NoMem instead of xalloc
void my_new_handler()
{
throw NoMem();
};

new_handler Old_Handler_ = set_new_handler(my_new_handler);

// improper array, find, insert, or delete index
// or deletion from empty structure
class OutOfBounds {
public:
OutOfBounds() {}
};

// use when operands should have matching size
class SizeMismatch {
public:
SizeMismatch() {}
};

// use when zero was expected
class MustBeZero {
public:
MustBeZero() {}
};

// use when zero was expected
class BadInput {
public:
BadInput() {}
};

#endif

#ifndef Node_
#define Node_

template <class T> class LinkedStack;
template <class T> class LinkedQueue;

template <class T>
class Node {
friend LinkedStack<T>;
friend LinkedQueue<T>;
private:
T data;
Node<T> *link;
};

#endif
// header file lqueue.h
// linked queue

#ifndef LinkedQueue_
#define LinkedQueue_

template<class T>
class LinkedQueue {
// FIFO objects
public:
LinkedQueue() {front = rear = 0;} // constructor
~LinkedQueue(); // destructor
int IsEmpty() const
{return ((front) ? 0 : 1);} //false : true);}
int IsFull() const;
T First() const; // return first element
T Last() const; // return last element
LinkedQueue<T>& Add(const T& x);
LinkedQueue<T>& Delete(T& x);
private:
Node<T> *front;  // pointer to first node
Node<T> *rear;   // pointer to last node
};

template<class T>
LinkedQueue<T>::~LinkedQueue()
{// Queue destructor.  Delete all nodes.
Node<T> *next;
while (front) {
next = front->link;
delete front;
front = next;
}
}

template<class T>
int LinkedQueue<T>::IsFull() const
{// Is the queue full?
Node<T> *p;
try {p = new Node<T>;
delete p;
return 0;} //false;}
catch (NoMem) {return 1;} //true;}
}

template<class T>
T LinkedQueue<T>::First() const
{// Return first element of queue.  Throw
// OutOfBounds exception if the queue is empty.
if (IsEmpty()) throw OutOfBounds();
return front->data;
}

template<class T>
T LinkedQueue<T>::Last() const
{// Return last element of queue.  Throw
// OutOfBounds exception if the queue is empty.
if (IsEmpty()) throw OutOfBounds();
return rear->data;
}

template<class T>
LinkedQueue<T>& LinkedQueue<T>::Add(const T& x)
{// Add x to rear of queue.  Do not catch
// possible NoMem exception thrown by new.

// create node for new element
Node<T> *p = new Node<T>;
p->data = x;
p->link = 0;

// add new node to rear of queue
if (front) rear->link = p;  // queue not empty
else front = p;             // queue empty
rear = p;

return *this;
}

template<class T>
LinkedQueue<T>& LinkedQueue<T>::Delete(T& x)
{// Delete first element and put it in x.  Throw
// OutOfBounds exception if the queue is empty.

if (IsEmpty()) throw OutOfBounds();

// save element in first node
x = front->data;

// delete first node
Node<T> *p = front;
front = front->link;
delete p;

return *this;
}

template<class T> class BinaryTree;
template <class T>
class BinaryTreeNode{
friend void Visit(BinaryTreeNode<T>*);
friend void InOrder(BinaryTreeNode<T>*);
friend void PreOrder(BinaryTreeNode<T>*);
friend void PostOrder(BinaryTreeNode<T>*);
friend void LevelOrder(BinaryTreeNode<T>*);
friend void main(void);
public :
BinaryTreeNode(){LeftChild=RightChild=0;}
BinaryTreeNode(const T& e){
data=e;
LeftChild=RightChild=0;
}
BinaryTreeNode(const T& e, BinaryTreeNode *l, BinaryTreeNode *r){
data=e;
LeftChild=l;
RightChild=r;
}
private :
T data;
BinaryTreeNode<T> *LeftChild, *RightChild;
};

template<class T>
void Visit(BinaryTreeNode<T> *x){
cout<<x->data<<” “;
}

template<class T>
void PreOrder(BinaryTreeNode<T> *t){
if(t){
Visit(t);
PreOrder(t->LeftChild);
PreOrder(t->RightChild);
}
}

template<class T>
void InOrder(BinaryTreeNode<T> *t){
if(t){
InOrder(t->LeftChild);
Visit(t);
InOrder(t->RightChild);
}
}

template<class T>
void PostOrder(BinaryTreeNode<T> *t){
if(t){
PostOrder(t->LeftChild);
PostOrder(t->RightChild);
Visit(t);
}
}

template<class T>
void LevelOrder(BinaryTreeNode<T> *t){
LinkedQueue<BinaryTreeNode<T>*> Q;
while(t){
Visit(t);
if(t->LeftChild)Q.Add(t->LeftChild);
if(t->RightChild)Q.Add(t->RightChild);
try{Q.Delete(t);}
catch(OutOfBounds){return;}
}
}

void main(void){
BinaryTreeNode<int> x,y,z;
x.data=1;
y.data=2;
z.data=3;
x.LeftChild=&y;
x.RightChild=&z;
y.LeftChild=y.RightChild=z.LeftChild=z.RightChild=0;
cout<<“Kunjungan In order : “;
InOrder(&x);
cout<<endl;
cout<<“Kunjungan Pre order : “;
PreOrder(&x);
cout<<endl;
cout<<“Kunjungan Post order : “;
PostOrder(&x);
cout<<endl;
cout<<“Kunjungan Level order : “;
LevelOrder(&x);
cout<<endl;

}
#endif

 

diatas sebenarnya adalah program pemberian dosen saya, program diatas tentang kunjungan tree, yaitu inorder, postorder, levelorder, preorder,  seperti yang kalian semua ketahui, bahwa urutan kunjungan nya berbeda-beda dan menghasilkan output yang berbeda.

1.jika preorder maka dia akan mencetak node yang dikunjungi, lalu akan mengunjungi anak kiri sampai habis dan mengunjungi anak kanan sampai habis.

2. jika inorder dia ankan mengunjungi anak kiri sampai habis, cetak isi node , dan kunjungi anak kanan.

3.jika post order, kunjungi anak kiri sampai habis, kunjungi anak kanan sampai habis, cetak isi node.

 

didalam program diatas , cara mengunjunginya dengan menggunaka rekursif, yaitu perulangan hingga node NULL, tapi untuk kunjungan secara level order program diatas menggunakan antrian, atau Queue.

terdapat tiga konstruktor , dan didalam program utamanya, dipanggil menggunakan parameter.

untuk output program diatas adlah

kunjungan inorder  : 2 1 3

kunjungan preorder  : 1 2 3

kunjungan postorder : 2 3 1

kunjungan level order : 1 2 3

 

selamat mencoba!!!!!