网站 › 『 编程之美 』 › 平衡二叉树

vmvm04 发表于 2009-9-5 02:27:31

平衡二叉树

// 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 发表于 2009-9-6 21:26:34

路过一下

超然 发表于 2009-9-7 11:32:49

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

查看完整版本: 平衡二叉树