btree2.c

用VC++

#include "BTree.h"
#include <stdlib.h>



BTree::BTree()
{
  root=NULL;
}

BTree::~BTree()
{
  DestructTree(root);
}

void BTree::DestructTree(node* r)
{
  if (r!=NULL)
    {
      DestructTree(r->left); DestructTree(r->right);
      delete r;
    }
}

void BTree::Insert(int elem)
{
  InsertInTree(elem, root);
}

void BTree::InsertInTree(int x, node *&p)
{

  if (p==NULL) // leaf, create new node
    {
      p=new node; 
      p->val=x; p->left=NULL; p->right=NULL; 
    }
  else if (p->val>x)
    {
      InsertInTree(x, p->left);
    }
  else if (p->val<x)
    {
      InsertInTree(x, p->right);  
    }
  else
    {
    // element already in tree, do nothing
    }
}

void BTree::Delete(int elem)
{
  DeleteFromTree(elem, root);
}





void BTree::Del(node *&r, node *&q)
{
  if (r->right!=NULL)
    {
      Del(r->right, q);
    }
  else
    {
      q->val=r->val; q=r; r=r->left; 
    }
}

void BTree::DeleteFromTree(int x, node *&p)
{
  node *q;
  
  if (p==NULL) {} // key not found!
  else if (p->val>x)
    {
      DeleteFromTree(x, p->left);
    }
  else if (p->val<x)
    {
      DeleteFromTree(x, p->right);

    }
  else  //p->val==x; remove
    {
      q=p;
      if (q->right==NULL)
	{
	  p=q->left; 
	}
      else if (q->left==NULL)
	{
	  p=q->right; 
	}
      else
	{
	  Del(q->left, q);
	}
      delete q;
    }
}
bool BTree::Find(int z)
{
  return FindInTree(z, root);
}

bool BTree::FindInTree(int z, node *&p)
{
  while (p != NULL)
      if (z < p->val)
	  p = p->left;
      else
	if (z > p->val)
	    p = p->right;
      else
	return true;
      
  return false;
}

int BTree::Max(const int a, const int b)
{
  if(a < b)
    return b;
  else
    return a;
}

int BTree::Height()
{
  HeightInTree(root);
}

int BTree::HeightInTree(const node *T)
{
  if (T == NULL)
    return -1;
  else 
    return 1 + Max(HeightInTree(T->left), HeightInTree(T->right));
}
      
int BTree::Size(const node*T)
{
  if (T == NULL)
    return 0;
  else 
    return 1 + Size(T->left) + Size(T->right);
}

int BTree::Leaves(const node *T)
{
  if (T == NULL)
    return 1;
  else
    return Leaves(T->left) + Leaves(T->right);
}
      
double BTree::AvDepth()
{
  return Size(root)/Leaves(root);
}


void BTree::PrintInTree(node *&T)
{
  if (T != NULL)
    {
      cout << T->val<< endl;
      PrintInTree(T->left);
      PrintInTree(T->right);
    }
}

void BTree::Print()
{
  PrintInTree(root);
}