Cây nhị phân - Binary Tree

tihocvb

Xin chia sẻ với các bạn code mình sưu tầm, được cài đặt bằng C++

Bật/Tắt số dòng | Mở rộng/Thu gọn | Chọn tất cả

 
    //
//  ============================================================
//
//          BinaryTree
//
//  ============================================================
//
//
//   Copyright (C) 1992,1993,1994,1995,1996
//
//                Professor Kenneth I. Joy
//                Computer Science Department
//                University of California
//                Davis, CA  95616
//
//   Permission is granted to use at your own risk and
//   distribute this software in source and binary forms
//   provided the above copyright notice and this paragraph
//   are preserved on all copies.  This software is provided
//   "as is" with no express or implied warranty.
//
//
//  ============================================================
//
#include <stdlib.h>
#include <math.h>
#include <stream.h>
#include <strings.h>
#include "BinaryTree.h"
#define  TRUE  1 
#define  FALSE  0
/*
   ============================================================
    CONSTRUCTOR, DESTRUCTOR
   ============================================================
*/
BinaryTree :: BinaryTree ()
   {
     _value = -100000.0 ;
     _left_child = NULL ;
     _right_child = NULL ;
   }
BinaryTree :: BinaryTree ( const double val,
     BinaryTree *left, BinaryTree *right ) 
   {
     _value = val ;
     _left_child = left ;
     _right_child = right ;
   }
BinaryTree :: BinaryTree ( const BinaryTree& t )
   {
     _value = t._value ;
     _left_child = _Copy ( t._left_child ) ;
     _right_child = _Copy ( t._right_child ) ;
   }
BinaryTree :: ~BinaryTree () 
   {
     if ( _left_child != NULL ) delete _left_child ;
     if ( _right_child != NULL ) delete _right_child ;
   }
/*
   ============================================================
    OPERATOR=
   ============================================================
*/
BinaryTree& BinaryTree :: operator= ( const BinaryTree& t )
   {
     if ( &t == this ) return ( *this ) ;
     _value = t._value ;
     _left_child = _Copy ( t._left_child ) ;
     _right_child = _Copy ( t._right_child ) ;
     return ( *this ) ;
   }
/*
   =============================================================
       OUTPUT
   =============================================================
*/
ostream& operator<< ( ostream& co, const BinaryTree& t ) 
   {
     co << " " << t._value ;
     if ( t._left_child != NULL ) 
  co << t._left_child ;
     if ( t._right_child != NULL ) 
  co << t._right_child ;
     return co ;
   }
ostream& operator<< ( ostream& co, const BinaryTree *t )
   {
     co << *t ;
     return ( co ) ;
   }
/*
   ============================================================
    COMPARISON
   ============================================================
*/
int operator== ( const BinaryTree& t1, const BinaryTree& t2 )
   {
     if ( t1.value() != t2.value() ) return ( FALSE ) ;
     if ( ( t1.left_child() == NULL ) &&
         ( t2.left_child() != NULL ) )
  return ( FALSE ) ;
     if ( ( t1.left_child() != NULL ) &&
         ( t2.left_child() == NULL ) )
  return ( FALSE ) ;
     if ( ( t1.left_child() != NULL ) &&
         ( t2.left_child() != NULL ) ) {
  if ( *(t1.left_child()) != *(t2.left_child()) ) 
    return ( FALSE ) ;
  }
     if ( ( t1.right_child() == NULL ) &&
         ( t2.right_child() != NULL ) )
  return ( FALSE ) ;
     if ( ( t1.right_child() != NULL ) &&
         ( t2.right_child() == NULL ) )
  return ( FALSE ) ;
     if ( ( t1.right_child() != NULL ) &&
         ( t2.right_child() != NULL ) ) {
  if ( *(t1.right_child()) != *(t2.right_child()) ) 
    return ( FALSE ) ;
  }
     return ( TRUE ) ;
   }
int operator!= ( const BinaryTree& t1, const BinaryTree& t2 )
   {
     return ( ! ( t1 == t2 ) ) ;
   }
/*
   ============================================================
    ADD
   ============================================================
*/
void BinaryTree :: add ( const double val )
   {
  //  First compare against the root to see 
  //    If this should be placed in the left 
  //    subtree, or the right subtree.
     if ( val < _value ) {
    if ( _left_child != NULL ) {
   //  Add to the left subtree
    _left_child -> add ( val ) ;
    }
       else {
   //  Create a new tree node as the left subtree
    BinaryTree *t = new BinaryTree ( val, NULL, NULL ) ;
    _left_child = t ;
    }
    }
  else {
    if ( _right_child != NULL ) {
   //  Add to the right subtree
    _right_child -> add ( val ) ;
    }
       else {
   //  Create a new tree node as the right subtree
    BinaryTree *t = new BinaryTree ( val, NULL, NULL ) ;
    _right_child = t ;
    }
    }
  
   }
/*
   ============================================================
    INORDER
   ============================================================
*/
void BinaryTree :: inorder () const
   {
     if ( _left_child != NULL ) _left_child -> inorder() ;
     cout << " " << _value ;
     if ( _right_child != NULL ) _right_child -> inorder() ;
   }
/*
   ============================================================
    PREORDER
   ============================================================
*/
void BinaryTree :: preorder () const
   {
     cout << " " << _value ;
     if ( _left_child != NULL ) _left_child -> preorder() ;
     if ( _right_child != NULL ) _right_child -> preorder() ;
   }
/*
   ============================================================
    POSTORDER
   ============================================================
*/
void BinaryTree :: postorder () const
   {
     if ( _left_child != NULL ) _left_child -> postorder() ;
     if ( _right_child != NULL ) _right_child -> postorder() ;
     cout << " " << _value ;
   }
/*
   ============================================================
    COPY
   ============================================================
*/
BinaryTree * _Copy ( BinaryTree * t ) 
   {
     if ( t == NULL ) return ( NULL ) ;
     BinaryTree *root = new BinaryTree 
    ( t -> value(), 
     _Copy ( t -> left_child() ),
     _Copy ( t -> right_child() ) ) ;
     return ( root ) ;
   }
 
 

Cây nhị phân - Binary Tree

Ai đang trực tuyến?