[Home]  [Edit this page]  [Recent Changes]  [Special Pages]  [Help] 

---

BinaryTree

---

(Computer science) Binary Tree

A binary tree can be thought of as a branching linked list. Diagramatically, a binary tree is a tree in which any node with have zero, one or two branches (and never more than two). In terms of its implementation, it is a structure that consists of data and two pointers to a left and right branch. Generally, it is sorted so that all items on the left branch are less than all items on the right, or vice versa. Items can quickly be inserted in order, and items can be quickly found.

Traversal Of Binary Trees

Binary trees can be traversed in three distinct ways:-

• InOrder - Look at the left node/subtree, then the node, then the right node/subtree. In a binary tree sorted so that all items on the left branch are less than all items on the right, then an InOrder transversal will give an ordered output of the data.
• PreOrder - Look at the root node first, then the left node/subtree, then the right node/subtree.
• PostOrder - Look at the left node/subtree first, then the right node/subtree, then the root node.

C++ Example

Following shows constructing a tree, with an InOrder traversal.

include <iostream>


struct node
{
  int data;
  node *left;
  node *right;
  node( int data_p )
    : data(data_p),
    left(0),
    right(0)
  {
    //Empty constructor
  }
};
node *head=0;
void addNode( int data )
{
  node *cur = head;
  if( !head )
  {
    head = new node( data );
    return;
  }
    
  while( 1 )
  {
    if( data > cur->data )
    {
      if(!cur->right)
      {
        cur=cur->right;
      } 
      else 
      {
        cur->right=new node(data);
        return;
      }
    } 
    else 
    {
      if(!cur->left)
      {
        cur=cur->left;
      } 
      else 
      {
        cur->left=new node(data);
        return;
      }
    }
  }
}
void traverse(const node * const cur)
{
  if(!cur) return;
  traverse( cur->left );
  std::cout << cur->data;
  traverse( cur->right );
}
void deleteTree(node *cur)
{
  if( cur->left  ) deleteTree( cur->left  );
  if( cur->right ) deleteTree( cur->right );
  delete cur;
}
int main()
{
  addNode( 10 );
  addNode( 5 );
  addNode( 3 );
  addNode( 8 );
  addNode( 54 );
  addNode( 12 );
  traverseTree( head );
  deleteTree( head );
}

[Edit this page]  [Page history]  [What links here]  [Discuss this topic]  [Printer Friendly]