树操作

时间：2010-09-04 来源：chengbin_liu

/* ************************************************************************
*       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 <unistd.h>
#include <stdlib.h>
#include <stdio.h> 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 <iostream>
using namespace std;
//==============================================
Tree::Tree(int num[], int len)
{
root=new Node(num[0]);
for(int i=1;i<len;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<<current->data<<" ";
  inorderTree(current->right);
}
}
//=================================================================
void Tree::preorderTree()
{
if(root==NULL)
  return ;
preorderTree(root);
}
void Tree::preorderTree(Node *current)
{
if(current != NULL)
{
  cout<<current->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<<current->data<<" ";
}
}
//=================================================================