Contoh Program Pohon

 Silahkan dicoba

#include <iostream>
#include <deque>
#include <climits>
using namespace std;

struct Tree
{
 char data;
 Tree *left;
 Tree *right;  
 Tree *parent;  
};

Tree* lookUp(struct Tree *node, char key)
{
 if(node == NULL) return node;

 if(node->data == key) return node;
 else {
  if(node->data < key)
   return lookUp(node->right, key) ;
  else
   return lookUp(node->left, key);
 }
}

Tree* leftMost(struct Tree *node)
{
 if(node == NULL) return NULL;
 while(node->left != NULL)
  node = node->left;
 return node;
}

struct Tree *newTreeNode(int data) 
{
 Tree *node = new Tree;
 node->data = data;
 node->left = NULL;
 node->right = NULL;
 node->parent = NULL;

 return node;
}

struct Tree* insertTreeNode(struct Tree *node, int data)
{
 static Tree *p;
 Tree *retNode;

 if(node != NULL) p = node;

 if(node == NULL)  {
  retNode = newTreeNode(data);
      retNode->parent = p;
  return retNode;
 }
 if(data <= node->data ) { 
  p = node;
  node->left = insertTreeNode(node->left,data);
 } 
 else {
  p = node;
  node->right = insertTreeNode(node->right,data);
 } 
 return node;
}

void isBST(struct Tree *node)
{
 static int lastData = INT_MIN;
 if(node == NULL) return;

 isBST(node->left);

 /* check if the given tree is BST */
 if(lastData < node->data) 
  lastData = node->data;
 else {
  cout << "Not a BST" << endl;
  return;
 }

 isBST(node->right);
 return;
}

int treeSize(struct Tree *node)
{
 if(node == NULL) return 0;
 else
  return treeSize(node->left) + 1 + treeSize(node->right);
}

int maxDepth(struct Tree *node)
{
 if(node == NULL) return 0;

 int leftDepth = maxDepth(node->left);
 int rightDepth = maxDepth(node->right);

 return leftDepth > rightDepth ? 
    leftDepth + 1 : rightDepth + 1;
}

int minDepth(struct Tree *node)
{
 if(node == NULL) return 0;

 int leftDepth = minDepth(node->left);
 int rightDepth = minDepth(node->right);

 return leftDepth < rightDepth ? 
    leftDepth + 1 : rightDepth + 1;
}

bool isBalanced(struct Tree *node)
{
 if(maxDepth(node)-minDepth(node) <= 1) 
  return true;
 else
  return false;
}

/* Tree Minimum */
Tree* minTree(struct Tree *node)
{
 if(node == NULL) return NULL;
 while(node->left) 
  node = node -> left;
 return node;
}

/* Tree Maximum */
Tree* maxTree(struct Tree *node)
{
 while(node->right) 
  node = node -> right;
 return node;
}

/* In Order Successor - a node which has the next higher key */ 
Tree *succesorInOrder(struct Tree *node)
{
 /* if the node has right child, seccessor is Tree-Minimum */
 if(node->right != NULL) return minTree(node->right);

 Tree *y = node->parent;
 while(y != NULL && node == y->right) {
  node = y;
  y = y->parent;
 }
 return y;
}

/* In Order Predecessor - a node which has the next lower key */
Tree *predecessorInOrder(struct Tree *node)
{
 /* if the node has left child, predecessor is Tree-Maximum */
 if(node->left != NULL) return maxTree(node->left);

 Tree *y = node->parent;
 /* if it does not have a left child, 
 predecessor is its first left ancestor */
 while(y != NULL && node == y->left) {
  node = y;
  y = y->parent;
 }
 return y;
}
 
Tree *lowestCommonAncestor(Tree *root, Tree *p, Tree *q) 
{
 Tree *left, *right;
 if(root == NULL) return NULL;
 if(root->left == p || root->left == q
  || root->right == p || root->right == q) return root;
 else {
  left = lowestCommonAncestor(root->left,p,q);
  right = lowestCommonAncestor(root->right, p,q);
  if(left && right) 
   return root;
  else 
   return (left) ? left : right;
 } 
}

void clear(struct Tree *node)
{
 if(node != NULL) {
  clear(node->left);
  clear(node->right);
  delete node;
 }
}
/* print tree in order */
/* 1. Traverse the left subtree. 
   2. Visit the root. 
   3. Traverse the right subtree. 
*/

void printTreeInOrder(struct Tree *node)
{
 static int lastData = INT_MIN;
 if(node == NULL) return;

 printTreeInOrder(node->left);
 cout << node->data << " ";
 printTreeInOrder(node->right);
}

/* print tree in postorder*/
/* 1. Traverse the left subtree. 
   2. Traverse the right subtree. 
   3. Visit the root. 
*/
void printTreePostOrder(struct Tree *node)
{
 if(node == NULL) return;

 printTreePostOrder(node->left);
 printTreePostOrder(node->right);
 cout << node->data << " ";
}

/* print in preorder */
/* 1. Visit the root. 
   2. Traverse the left subtree. 
   3. Traverse the right subtree. 
*/
void printTreePreOrder(struct Tree *node)
{
 if(node == NULL) return;

 cout << node->data << " ";
 printTreePreOrder(node->left);
 printTreePreOrder(node->right);
}

/* printing array */
void printThisPath(int path[], int n)
{
 for(int i = 0; i < n; i++)
  cout << (char)path[i] << " ";
 cout << endl;
}

/* recursion routine to find path */
void pathFinder(struct Tree *node, int path[], int pathLength)
{
 if(node == NULL) return;
 path[pathLength++] = node->data;

 /* Leaf node is the end of a path. 
    So, let's print the path */
 if(node->left == NULL && node->right == NULL)
  printThisPath(path, pathLength);
 else {
  pathFinder(node->left, path, pathLength);
  pathFinder(node->right, path, pathLength);
 }
}

/*printing all paths :
Given a binary tree, print out all of its root-to-leaf 
paths, one per line. Uses a recursive helper to do the work. */

void printAllPaths(struct Tree *root)
{
 int path[100];
 pathFinder(root,path,0);
}

bool matchTree(Tree *r1, Tree *r2)
{
 /* Nothing left in the subtree */
 if(r1 == NULL && r2 == NULL)
  return true;
 /* Big tree empty and subtree not found */
 if(r1 == NULL || r2 == NULL)
  return false;
 /* Not matching */
 if(r1->data != r2->data)
  return false;
 return (matchTree(r1->left, r2->left) && 
   matchTree(r1->right, r2->right));
}

bool subTree(Tree *r1, Tree *r2)
{
 /*Big tree empty and subtree not found */
 if(r1 == NULL)
  return false;
 if(r1->data == r2->data)
  if(matchTree(r1, r2)) return true;
 return (subTree(r1->left, r2) || subTree(r1->right, r2));
}

bool isSubTree(Tree *r1, Tree *r2)
{
 /* Empty tree is subtree */
 if(r2 == NULL) 
  return true;
 else
  return subTree(r1, r2);
}

/* change a tree so that the roles of the left 
and right hand pointers are swapped at every node */
void mirror(Tree *r)
{
 if(r == NULL) return;
 
 Tree *tmp;
 mirror(r->left);
 mirror(r->right);

 /* swap pointers */
 tmp = r->right;
 r->right = r->left;
 r->left = tmp;
}

/* create a new tree from a sorted array */
Tree *addToBST(char arr[], int start, int end)
{
 if(end < start) return NULL;
 int mid = (start + end)/2;

 Tree *r = new Tree;
 r->data = arr[mid];
 r->left = addToBST(arr, start, mid-1);
 r->right = addToBST(arr, mid+1, end);
 return r;
}

Tree *createMinimalBST(char arr[], int size)
{
 return addToBST(arr,0,size-1);
}

/* Breadth first traversal using queue */
void BreadthFirstTraversal(Tree *root)
{
 if (root == NULL) return;
 deque <Tree *> queue;
 queue.push_back(root);

 while (!queue.empty()) {
  Tree *p = queue.front();
  cout << p->data << " ";
  queue.pop_front();

  if (p->left != NULL)
   queue.push_back(p->left);
  if (p->right != NULL)
   queue.push_back(p->right);
 }
 cout << endl;
} 

/* find n-th max node from a tree */
void NthMax(struct Tree* t)
{        
 static int n_th_max = 5;
 static int num = 0;
 if(t == NULL) return;        
 NthMax(t->right);        
 num++;        
 if(num == n_th_max)                
  cout << n_th_max << "-th maximum data is " << t->data << endl;        
 NthMax(t->left);
}

/* Converting a BST into an Array */ 
void TreeToArray(struct Tree *node, int a[]){ 
 static int pos = 0; 
  
 if(node){ 
  TreeToArray(node->left,a); 
  a[pos++] = node->data; 
  TreeToArray(node->right,a); 
      } 
} 

int main(int argc, char **argv)
{
 char ch, ch1, ch2;
 Tree *found;
 Tree *succ;
 Tree *pred;
 Tree *ancestor;
 char charArr[9] 
  = {'A','B','C','D','E','F','G','H','I'};

 Tree *root = newTreeNode('F');
 insertTreeNode(root,'B');
 insertTreeNode(root,'A');
 insertTreeNode(root,'D');
 insertTreeNode(root,'C');  
 insertTreeNode(root,'E');
 insertTreeNode(root,'G');
 insertTreeNode(root,'I');
 insertTreeNode(root,'H');

 /* is the tree BST? */
 isBST(root);

 /* size of tree */
 cout << "size = " << treeSize(root) << endl;

 /* max depth */
 cout << "max depth = " << maxDepth(root) << endl;

 /* min depth */
 cout << "min depth = " << minDepth(root) << endl;

 /* balanced tree? */
 if(isBalanced(root))
  cout << "This tree is balanced!\n";
 else
  cout << "This tree is not balanced!\n";

 /* min value of the tree*/
 if(root) 
  cout << "Min value = " << minTree(root)->data << endl;

 /* max value of the tree*/
 if(root) 
  cout << "Max value = " << maxTree(root)->data << endl;

 ch = 'B';
 found = lookUp(root,ch);
 if(found) {
  cout << "Min value of subtree " << ch << " as a root is "
    << minTree(found)->data << endl;
  cout << "Max value of subtree " << ch << " as a root is "
    << maxTree(found)->data << endl;
 }

 ch = 'B';
 found = lookUp(root,ch);
 if(found) {
  succ = succesorInOrder(found);
  if(succ)
   cout << "In Order Successor of " << ch << " is "
    << succesorInOrder(found)->data << endl;
  else 
   cout << "In Order Successor of " << ch << " is None\n";
 }

 ch = 'E';
 found = lookUp(root,ch);
 if(found) {
  succ = succesorInOrder(found);
  if(succ)
   cout << "In Order Successor of " << ch << " is "
    << succesorInOrder(found)->data << endl;
  else 
   cout << "In Order Successor of " << ch << " is None\n";
 }

 ch = 'I';
 found = lookUp(root,ch);
 if(found) {
  succ = succesorInOrder(found);
  if(succ)
   cout << "In Order Successor of " << ch << " is "
    << succesorInOrder(found)->data << endl;
  else 
   cout << "In Order Successor of " << ch << " is None\n";
 }

 ch = 'B';
 found = lookUp(root,ch);
 if(found) {
  pred = predecessorInOrder(found);
  if(pred)
   cout << "In Order Predecessor of " << ch << " is "
    << predecessorInOrder(found)->data << endl;
  else 
   cout << "In Order Predecessor of " << ch << " is None\n";
 }

 ch = 'E';
 found = lookUp(root,ch);
 if(found) {
  pred = predecessorInOrder(found);
  if(pred)
   cout << "In Order Predecessor of " << ch << " is "
    << predecessorInOrder(found)->data << endl;
  else 
   cout << "In Order Predecessor of " << ch << " is None\n";
 }

 ch = 'I';
 found = lookUp(root,ch);
 if(found) {
  pred = predecessorInOrder(found);
  if(pred)
   cout << "In Order Predecessor of " << ch << " is "
    << predecessorInOrder(found)->data << endl;
  else 
   cout << "In Order Predecessor of " << ch << " is None\n";
 }

 /* Lowest Common Ancestor */
 ch1 = 'A';
 ch2 = 'C';
 ancestor = 
  lowestCommonAncestor(root, 
   lookUp(root,ch1), lookUp(root,ch2));
 if(ancestor) 
  cout << "The lowest common ancestor of " << ch1 << " and "
  << ch2 << " is " << ancestor->data << endl;

 ch1 = 'E';
 ch2 = 'H';
 ancestor = 
  lowestCommonAncestor(root, 
   lookUp(root,ch1), lookUp(root,ch2));
 if(ancestor) 
  cout << "The lowest common ancestor of " << ch1 << " and "
  << ch2 << " is " << ancestor->data << endl;

 /* print tree in order */
 cout << "increasing sort order\n";
 printTreeInOrder(root);
 cout << endl;

 /* print tree in postorder*/
 cout << "post order \n";
 printTreePostOrder(root);
 cout << endl;

 /* print tree in preorder*/
 cout << "pre order \n";
 printTreePreOrder(root);
 cout << endl;

 /* lookUp */
 ch = 'D';
 found = lookUp(root,ch);
 if(found) 
  cout << found->data << " is in the tree\n";
 else
  cout << ch << " is not in the tree\n";

 /* lookUp */
 ch = 'M';
 found = lookUp(root,ch);
 if(found) 
  cout << found->data << " is in the tree\n";
 else
  cout << ch << " is not in the tree\n";

 /* printing all paths :
 Given a binary tree, print out all of its root-to-leaf 
 paths, one per line. Uses a recursive helper to do the work. */
 cout << "printing paths ..." << endl;
 printAllPaths(root); 

 /* find n-th maximum node */
 NthMax(root);


 /* convert the tree into an array */
 int treeSz = treeSize(root);
 int *array = new int[treeSz];
 TreeToArray(root,array);
 cout << "New array: ";
 for (int i = 0; i < treeSz; i++)
  cout << (char)array[i] << ' ';
 cout << endl;
 delete [] array;

 /* subtree */
 Tree *root2 = newTreeNode('D');
 insertTreeNode(root2,'C');  
 insertTreeNode(root2,'E');
 cout << "1-2 subtree: " << isSubTree(root, root2) << endl;

 Tree *root3 = newTreeNode('B');
 insertTreeNode(root3,'A');  
 insertTreeNode(root3,'D');
 insertTreeNode(root3,'C');  
 insertTreeNode(root3,'E');
 cout << "1-3 subtree: " << isSubTree(root, root3) << endl;

 Tree *root4 = newTreeNode('B'); 
 insertTreeNode(root4,'D');
 insertTreeNode(root4,'C');  
 insertTreeNode(root4,'E');
 cout << "1-4 subtree: " << isSubTree(root, root4) << endl;

 cout << "2-3 subtree: " << isSubTree(root2, root3) << endl;
 cout << "3-2 subtree: " << isSubTree(root3, root2) << endl;

 /* swap left and right */
 mirror(root);

 /* deleting a tree */
 clear(root);

 /* make a new tree with minimal depth */
 Tree *newRoot = createMinimalBST(charArr,9);

 /* Traversing level-order. 
 We visit every node on a level before going to a lower level. 
 This is also called Breadth-first traversal.*/
 cout << "printing with Breadth-first traversal" << endl;
 BreadthFirstTraversal(newRoot);

 return 0;
}

Artikel Terkait