從大到小插入都是正常的
但是從小到大輸入四個之內正常
超過四個就崩潰了
程式原始碼
#include<iostream>
using namespace std;
class TreeNode{
public:
int value;
TreeNode*Ltree;
TreeNode*Rtree;
TreeNode(int info){value=https://bbs.csdn.net/topics/info;Ltree=NULL;Rtree=NULL;}
};
class BFtree{
private:
TreeNode*root;
int getHeight(TreeNode*p);
void insertNode(TreeNode* p,int info);
void Lrotata(TreeNode* p);
void Rrotata(TreeNode* p);
void BFtreeclear(TreeNode*p);
int getBF(TreeNode*p);
void Firstprintf(TreeNode*p);
void middleprintf(TreeNode*p);
TreeNode* findparent(TreeNode*p);
public:
BFtree();
~BFtree();
void insertNode(int info);
void firstprintf();
void middleprintf();
};
BFtree::BFtree() //建構式
{
root=NULL;
}
BFtree::~BFtree()//解構式
{
if(root==NULL);
return;
BFtreeclear(root);
}
void BFtree::BFtreeclear(TreeNode*p)//清空樹節點 被解構式呼叫
{
if(p!=NULL)
{
BFtreeclear(p->Ltree);
BFtreeclear(p->Rtree);
delete p;
}
}
int BFtree::getHeight(TreeNode*p)//獲取節點高度
{
int HL,HR,MAXH;
if(p!=NULL)
{
HL=getHeight(p->Ltree);
HR=getHeight(p->Rtree);
MAXH=HL>HR?HL:HR;
return MAXH+1;
}
else
return 0;
}
void BFtree::insertNode(int info)//插入節點
{
if(root==NULL)
root=new TreeNode(info);
else
insertNode(root,info);
}
TreeNode* BFtree::findparent(TreeNode*p)//查找父節點
{ TreeNode*parent=root;
if(p==root)
return NULL;
while(parent->Ltree!=p&&parent->Rtree!=NULL)
{
if(parent->value>p->value)
parent=parent->Ltree;
else
parent=parent->Rtree;
}
return parent;
}
int BFtree::getBF(TreeNode*p)//回傳節點的左右孩子高度差即平衡因子
{
return getHeight(p->Ltree)-getHeight(p->Rtree);
}
void BFtree::Lrotata(TreeNode*p)//左旋轉
{
TreeNode*temp=p->Rtree;
p->Rtree=temp->Ltree;
temp->Ltree=p;
if(p==root)
root=temp;
else //將該子樹的父節點指向他的右孩子
{
TreeNode *parent=findparent(p);
if(parent->Ltree==p)
parent->Ltree=temp;
else
parent->Rtree=temp;
}
}
void BFtree::Rrotata(TreeNode*p)//右旋轉
{
TreeNode*temp=p->Ltree;
p->Ltree=temp->Rtree;
temp->Rtree=p;
if(p==root)
root=temp;
else //將子樹的父節點指向的左孩子
{
TreeNode *parent=findparent(p);
if(parent->Ltree==p)
parent->Ltree=temp;
else
parent->Rtree=temp;
}
}
void BFtree::insertNode(TreeNode*p,int info)
{
if(p->value>info)
{
if(p->Ltree==NULL)
p->Ltree=new TreeNode(info);
else
{
insertNode(p->Ltree,info);
if(getBF(p)==2) //如果平衡因子等于2 要做旋轉調整
{
if(getBF(p->Ltree)==1)//如果左子樹平衡因子等于1 說明是右旋轉
Rrotata(p);
else if(getBF(p->Ltree)==-1)//等于-1 是左右旋轉
{
Lrotata(p->Ltree);
Rrotata(p);
}
}
}
}
else
{
if(p->Rtree==NULL)
p->Rtree=new TreeNode(info);
else
{
insertNode(p->Rtree,info);
if(getBF(p)==-2) //同上要做調整
{
if(getBF(p->Rtree)==-1)//左旋轉判定
Lrotata(p);
else if(getBF(p->Rtree)==1)//右左旋轉判定
{
Rrotata(p->Rtree);
Lrotata(p);
}
}
}
}
}
void BFtree::firstprintf()//先序遍歷
{
if(root==NULL)
{
cout<<"該樹為空"<<endl;
return;
}
Firstprintf(root);
cout<<endl;
}
void BFtree::Firstprintf(TreeNode*p)//呼叫先序遍歷
{
if(p!=NULL)
{
cout<<p->value<<' ';
Firstprintf(p->Ltree);
Firstprintf(p->Rtree);
}
}
void BFtree::middleprintf()//呼叫中序遍歷
{
if(root==NULL)
{
cout<<"該樹為空"<<endl;
return;
}
middleprintf(root);
cout<<endl;
}
void BFtree::middleprintf(TreeNode*p)//中序遍歷
{
if(p!=NULL)
{
middleprintf(p->Ltree);
cout<<p->value<<' ';
middleprintf(p->Rtree);
}
}
int main(){
BFtree a;
a.insertNode(1);
a.insertNode(2);
a.insertNode(3);
a.insertNode(4);
a.insertNode(5);
//a.insertNode(6);
cout<<"該樹的先序遍歷順序是:";
a.firstprintf();
cout<<"該樹的中序遍歷順序是:";
a.middleprintf();
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/238137.html
標籤：新手樂園
上一篇：關于平衡二叉樹的旋轉演算法疑問