The following source codes are used in this chapter. A binary tree is either an external node or an internal node connected to a pair of binary trees, which are called the left subtree and the right subtree of that node.

Binary Tree

1. Main function using BinTree and Stack classes

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 9: Trees

// Binary Tree
// to simplify the code using only for addition and multiplication operations
// Binary tree preorder traversal converts Polish postfix notation to prefix notation
// using Stack claas defined in "stack_list.h" in the chapter 7

#include "stack_list.h"

template<class Type>
class BinTree {
  Type data;
  BinTree<Type> *r, *l;
public:
  BinTree(Type item) : data(item), l(NULL), r(NULL) {};
  ~BinTree();
  void setr(BinTree *rp) { r = rp;}
  void setl(BinTree *lp) { l = lp;}
  BinTree* getr() { return r; }
  BinTree* getl() { return l; }
  void print() { cout << data; }
};

int main()
{
  BinTree<char> *ptree, *child;
  Stack<BinTree<char> *> stack;
  const char *postfix="abc+de**f+*";
  char c;
  int i = 0;

  cout << "Polish postfix notation: " << postfix << endl;

  while(c = *(postfix + i++)) {
    ptree = new BinTree<char>(c);
    if(c == '+' || c=='*') {
      stack.pop(child); ptree->setr(child);
      stack.pop(child); ptree->setl(child);
    }
    stack.push(ptree);
  }

  cout << "Polish prefix notation: ";
  while(!stack.empty()) {
    stack.pop(ptree); 
    ptree->print();
    if(child = ptree->getr()) stack.push(child);
    if(child = ptree->getl()) stack.push(child);
  }
  cout << endl;
}

2. Header file: stack_list.h

This header file is defined in Chapter 7. Stacks.

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 7: Stack
// Chapter 9: Trees
// Chapter 11: Advanced sorting algorithms

// Stack class using linked list
// Filename: stack_list.h