查找二叉树

vmvm04

// Tree.h  Begin

class TreeNode
{
public:
  int data;
  TreeNode * lchild;
  TreeNode * rchild;
public:
  TreeNode(int Data)
  {
    data=Data;
    lchild = rchild = NULL;
  }
};

class Tree  
{
public:
  TreeNode * tree;
public:
        Tree(int Data);
        virtual ~Tree();
public:
  TreeNode * InsertTree(TreeNode * rootp,int data);
  TreeNode * DeleteTree(TreeNode * rootp,int data);
  TreeNode * FindData(TreeNode * rootp,int data);
  TreeNode * FindMax(TreeNode * rootp);
  TreeNode * FindMin(TreeNode * rootp);
public:
  void PreOrder(TreeNode * rootp);
  TreeNode * GetTree();
};


// Tree.h End

// Tree.cpp  Begin

#include "stdafx.h"
#include "Tree.h"

Tree::Tree(int Data)
{
  tree = new TreeNode(Data);
}

Tree::~Tree()
{
  
}

TreeNode * Tree::InsertTree(TreeNode * rootp,int data)
{
  if(data < rootp->data)
  {
    if(!rootp->lchild)
    {
      rootp->lchild = new TreeNode(data);
      return rootp->lchild;
    }
    return InsertTree(rootp->lchild,data);
  }
  if(data >= rootp->data)
  {
    if(!rootp->rchild)
    {
      rootp->rchild = new TreeNode(data);
      return rootp->rchild;
    }
    return InsertTree(rootp->rchild,data);
  }
  return NULL;
}

TreeNode * Tree::DeleteTree(TreeNode * rootp,int data)
{
  if(data < rootp->data)
  {
    rootp->lchild = DeleteTree(rootp->lchild,data);
  }
  if (data > rootp->data)
  {
    rootp->rchild = DeleteTree(rootp->rchild,data);
  }
  if(data == rootp->data)
  {
      if(rootp->lchild && rootp->rchild)
      {
        TreeNode * pMax = FindMax(rootp->lchild);
        rootp->data = pMax->data;
        DeleteTree(rootp->lchild,rootp->data);
      }
      else  // 保存子树地址 若都空则返回NULL
      {
        TreeNode * pTemp = rootp;   
        rootp = pTemp->lchild!=NULL ? pTemp->lchild : rootp->rchild;
        delete[] pTemp;
      }
  }
  return rootp;
}

TreeNode * Tree::FindData(TreeNode * rootp,int data)
{
  if(!rootp)return NULL;
  if(data == rootp->data)return rootp;
  TreeNode * pFind = FindData(rootp->lchild,data);
  if(pFind) return pFind;
  return FindData(rootp->rchild,data);
}

TreeNode * Tree::FindMax(TreeNode * rootp)
{
  if(!rootp)return NULL;
  if(!rootp->rchild)return rootp;
  return FindMax(rootp->rchild);
}

TreeNode * Tree::FindMin(TreeNode * rootp)
{
  if(!rootp)return NULL;
  if(!rootp->lchild)return rootp;
  return FindMin(rootp->lchild);
}

void Tree::PreOrder(TreeNode * rootp)
{
  if(!rootp)return ;
  printf("%d ",rootp->data);
  PreOrder(rootp->lchild);
  PreOrder(rootp->rchild);
}

TreeNode * Tree::GetTree()
{
  return tree;
}


// Tree.cpp End

// Main.cpp Begin

#include "stdafx.h"
#include "Tree.h"

int main(int argc, char* argv[])
{
        Tree * tree = new Tree(50);
  TreeNode * treenode = tree->GetTree();
  tree->InsertTree(treenode,20);
  tree->InsertTree(treenode,70);
  tree->InsertTree(treenode,60);
  tree->InsertTree(treenode,65);
  tree->InsertTree(treenode,63);
  tree->InsertTree(treenode,80);
  tree->PreOrder(treenode);
  printf("\r\n");
  tree->DeleteTree(treenode,70);
  tree->PreOrder(treenode);
  printf("\r\n");
  return 0;
}

// Main.cpp End

[ 本帖最后由 vmvm04 于 2009-9-4 02:41 编辑 ]