树操作

/* ************************************************************************
 *       Filename:  tree.h
 *    Description: 
 *        Version:  1.0
 *        Created:  09/04/2010 11:57:20 AM
 *       Revision:  none
 *       Compiler:  gcc
 *         Author:  chengbin_liu,
 *        Company: 
 * ************************************************************************/

#ifndef _TREE_H_
#define _TREE_H_
#include
#include
#include

class Node
{
 public:
  int data;
  Node *parent;
  Node *left;
  Node *right;
 public:
  Node():data(-1),parent(NULL),left(NULL),right(NULL){};
  Node(int num):data(num),parent(NULL),left(NULL),right(NULL){};
};

class Tree
{
 public:
  Tree(int num[], int len);
  void insertNode(int data);
  void insertNode1(int data);
  Node *searchNode(int data);
  void deleteNode(int data);
  void inorderTree();
  void preorderTree();
  void postorderTree();
 private:
  void insertNode(Node *current, int data);
  Node *searchNode(Node *current, int data);
  void deleteNode(Node *current);
  void inorderTree(Node *current);
  void preorderTree(Node *current);
  void postorderTree(Node *current);
 private:
  Node *root;
};
#endif

//================================================================

 

/* ************************************************************************
 *       Filename:  tree.cpp
 *    Description: 
 *        Version:  1.0
 *        Created:  09/04/2010 11:57:30 AM
 *       Revision:  none
 *       Compiler:  gcc
 *         Author:  chengbin_liu,
 *        Company: 
 * ************************************************************************/
#include "tree.h"
#include
using namespace std;
//==============================================
Tree::Tree(int num[], int len)
{
 root=new Node(num[0]);
 for(int i=1;i {
  insertNode(num[i]);
 }
}
//================================================
void Tree::insertNode(int data)
{
 if(root != NULL)
 {
  insertNode(root,data);
 }
}
//=================================================
void Tree::insertNode(Node *current,int data)
{
 if(data < current->data)
 {
  if(current->left==NULL)
  {
  current->left=new Node(data);
  current->left->parent=current;
  }
  else
   insertNode(current->left,data);
 }
 else
 if(data > current->data)
 {
  if(current->right==NULL)
  {
   current->right=new Node(data);
   current->right->parent=current;
  }
  else
   insertNode(current->right,data);
 }

 return;
}
//============================================================
void Tree::insertNode1(int data)
{
 Node *p,*par;
 Node *newNode=new Node(data);
 p=par=root;
 while(p != NULL)
 {
  par=p;
  if(data > p->data)
   p=p->right;
  else
  if(data < p->data)
   p=p->left;
  else
  if(data == p->data)
  {
   delete newNode;
   return;
  }
 }
 newNode->parent=par;
 if(par->data > newNode->data)
  par->left=newNode;
 else
  par->right=newNode;
}
//===============================================================
Node* Tree::searchNode(int data)
{

}
//==============================================================
Node* Tree::searchNode(Node *current,int data)
{
 if(data < current->data)
 {
  if(current->left==NULL)
   return NULL;
  return searchNode(current->left,data);
 }
 else
 if(data > current->data)
 {
  if(current->right==NULL)
   return NULL;
  return searchNode(current->right,data);
 }
 return current;
}
//===============================================================
//void Tree::deleteNode(int data)
//{
// Node *current=NULL;
// current=searchNode(data);
// if(current !=NULL)
// {
//  deleteNode(current);
// }
//}
//===============================================================
//void Tree::deleteNode(Node *current)
//{
// if(current->left !=NULL)
//  deleteNode(current->left);
// if(current->right !=NULL)
//  deleteNode(current->right);
// if(current->parent==NULL)
// {
//  delete current;
//  root=NULL;
//  return;
// }
// if(current->parent->data >current->data)
//  current->parent->left=NULL;
// else
//  current->parent->right=NULL;
// delete current;
//}
//=================================================================
void Tree::inorderTree()
{
 if(root==NULL)
  return ;
 inorderTree(root);
}
void Tree::inorderTree(Node *current)
{
 if(current != NULL)
 {
  inorderTree(current->left);
  cout<data<<" ";
  inorderTree(current->right);
 }
}
//=================================================================
void Tree::preorderTree()
{
 if(root==NULL)
  return ;
 preorderTree(root);
}
void Tree::preorderTree(Node *current)
{
 if(current != NULL)
 {
  cout<data<<" ";
  preorderTree(current->left);
  preorderTree(current->right);
 }
}
//=================================================================
void Tree::postorderTree()
{
 if(root==NULL)
  return ;
 postorderTree(root);
}
void Tree::postorderTree(Node *current)
{
 if(current != NULL)
 {
  postorderTree(current->left);
  postorderTree(current->right);
  cout<data<<" ";
 }
}
//=================================================================