网站 › 『 编程之美 』 › 查找二叉树

vmvm04 发表于 2009-9-4 02:39:53

查找二叉树

// Tree.hBegin

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.cppBegin

#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 编辑 ]

查看完整版本: 查找二叉树