平衡二叉树

vmvm04

// AvlTree.h Begin
class TreeNode
{
public:
  int data;
  TreeNode * lchild;
  TreeNode * rchild;
  int Height;
public:
  TreeNode(int Data)
  {
    data=Data;
    lchild = rchild = NULL;
    Height=-1;
  }
};

class AvlTree  
{
private:
  TreeNode * tree;
public:
  AvlTree(int Data);
  virtual ~AvlTree();
public:
  TreeNode * InsertTree(TreeNode * rootp,int Data);
public:
  TreeNode * SingleRotateWithLeft(TreeNode * rootp);
  TreeNode * SingleRotateWithRight(TreeNode * rootp);
  TreeNode * DoubleRotateWithLeft(TreeNode * rootp);
  TreeNode * DoubleRotateWithRight(TreeNode * rootp);
public:
  int HeightNode(TreeNode * rootp);
  void PreOrder(TreeNode * rootp);
  void ReleaseTree(TreeNode * rootp);
  TreeNode * GetTree();
};

// AvlTree.h End

//AvlTree.cpp Begin

#include "stdafx.h"
#include "AvlTree.h"

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

AvlTree::~AvlTree()
{
  //ReleaseTree(tree);
}

int AvlTree::HeightNode(TreeNode * rootp)
{
  if(!rootp)return -1;
  int lh=HeightNode(rootp->lchild);
  int rh=HeightNode(rootp->rchild);
  return (lh>rh?lh:rh)+1;
}

void AvlTree::PreOrder(TreeNode * rootp)
{
  if(!rootp)return ;
  cout<<rootp->data<<"("<<rootp->Height<<")"<<" ";
  PreOrder(rootp->lchild);
  PreOrder(rootp->rchild);
}

void AvlTree::ReleaseTree(TreeNode * rootp)
{
  if(!rootp->lchild && rootp->rchild)
  delete[] rootp;
  ReleaseTree(rootp->lchild);
  ReleaseTree(rootp->rchild);
}

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

TreeNode * AvlTree::InsertTree(TreeNode * rootp,int Data)
{
  if(!rootp)
  {
    rootp = new TreeNode(Data);
  }
  else
  {
    if(Data < rootp->data)
    {
      rootp->lchild = InsertTree(rootp->lchild,Data);
      if(HeightNode(rootp->lchild)-HeightNode(rootp->rchild) == 2 )
      {
        if(Data < rootp->lchild->data)
          rootp = SingleRotateWithLeft(rootp);
        else
          rootp = DoubleRotateWithLeft(rootp);
      }
    }
    else
    {
      rootp->rchild = InsertTree(rootp->rchild,Data);
      if(HeightNode(rootp->rchild) - HeightNode(rootp->lchild) == 2 )
      {
        if(Data > rootp->rchild->data)
          rootp = SingleRotateWithRight(rootp);
        else
          rootp = DoubleRotateWithRight(rootp);
      }
    }
  }
  rootp->Height = HeightNode(rootp);
  return rootp;
}

TreeNode * AvlTree::SingleRotateWithLeft(TreeNode * rootp)
{
  TreeNode * p = rootp->lchild;
  rootp->lchild = p->rchild;
  p->rchild = rootp;
  p->Height = HeightNode(p);
  rootp->Height = HeightNode(rootp);
  return p;
}

TreeNode * AvlTree::SingleRotateWithRight(TreeNode * rootp)
{
  TreeNode * p = rootp->rchild;
  rootp->rchild = p->lchild;
  p->lchild = rootp;
  p->Height = HeightNode(p);
  rootp->Height = HeightNode(rootp);
  return p;
}
TreeNode * AvlTree::DoubleRotateWithLeft(TreeNode * rootp)
{
  rootp->lchild=SingleRotateWithRight(rootp->lchild);
  return SingleRotateWithLeft(rootp);
}

TreeNode * AvlTree::DoubleRotateWithRight(TreeNode * rootp)
{
  rootp->rchild=SingleRotateWithLeft(rootp->rchild);
  return SingleRotateWithRight(rootp);
}

//AvlTree.cpp End

// Main.cpp Begin

#include "stdafx.h"
#include "AvlTree.h"

int main(int argc, char* argv[])
{
  AvlTree * tree = new AvlTree(1);
  TreeNode * rootp = tree->GetTree();
  rootp = tree->InsertTree(rootp,2);
  rootp = tree->InsertTree(rootp,3);
  rootp = tree->InsertTree(rootp,4);
  rootp = tree->InsertTree(rootp,5);
  rootp = tree->InsertTree(rootp,6);
  rootp = tree->InsertTree(rootp,7);
  tree->PreOrder(rootp);
  cout<<endl;
  int data=0;
  while(true)
  {
    cout<<"请输入追加数据：";
    cin>>data;
    if(!data)break;
    rootp = tree->InsertTree(rootp,data);
    tree->PreOrder(rootp);
    cout<<endl;
  }
  return 0;
}

// Main.cpp End

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

xusir98

路过一下

超然

删除都不做，我正需要呢。