只要洗掉根節點并且根節點有左右兩個孩子 程式就崩潰 其他情況都是正常的沒BUG
下面都是正常的
洗掉左右子樹不為空的根節點就報錯了
程式原始碼
#include<iostream>
using namespace std;
class TreeNode{
public:
friend class Btree;
TreeNode(int info){value=https://bbs.csdn.net/topics/info;LTree=NULL;RTree=NULL;}
int value;
private:
TreeNode*LTree;
TreeNode*RTree;
};
class Btree{
public:
Btree();
~Btree();
void insertNode(int value);
void firstprintf();
void middleprintf();
void lastprintf();
void showsize();
void deleteValueOfTree(int k);
TreeNode* FindMinValue();
TreeNode* FindMaxValue();
TreeNode* FindValueOfTree(int k);
private:
TreeNode*root;
int Nodenumber;
void Firstprintf(TreeNode*p);
void Btreeclear(TreeNode*p);
void insertNode(TreeNode*p,int value);
void Middleprintf(TreeNode*p);
void Lastprintf(TreeNode*p);
TreeNode *FindParentofNode(TreeNode*p);
};
Btree::Btree()//建構式
{
root=NULL;
Nodenumber=0;
}
Btree::~Btree()//解構式
{
if(root==NULL)
return;
else
Btreeclear(root);
}
void Btree::Btreeclear(TreeNode*p)//洗掉所有節點
{
if(p!=NULL){
Btreeclear(p->LTree);
Btreeclear(p->RTree);
delete p;
}
}
void Btree::insertNode(int value)//呼叫插入節點
{
if(root==NULL)
{
root=new TreeNode(value);
Nodenumber++;
}
else
{
insertNode(root,value);
Nodenumber++;
}
}
void Btree::insertNode(TreeNode*p,int value)//插入節點
{
if(p->value>value)
{
if(p->LTree==NULL)
p->LTree=new TreeNode(value);
else
insertNode(p->LTree,value);
}
else if(p->value<value)
{
if(p->RTree==NULL)
p->RTree=new TreeNode(value);
else
insertNode(p->RTree,value);
}
}
void Btree::firstprintf()//呼叫先序遍歷
{ if(Nodenumber==0)
cout<<"該樹為空"<<endl;
else
{
Firstprintf(root);
cout<<endl;
}
}
void Btree::Firstprintf(TreeNode*p)//先序遍歷
{
if(p!=NULL)
{
cout<<p->value<<"->";
Firstprintf(p->LTree);
Firstprintf(p->RTree);
}
}
TreeNode*Btree::FindParentofNode(TreeNode*p)//查找節點p的父節點
{ if(p==root)
{ cout<<"查找的是根節點，沒父母"<<endl;
return NULL;
}
TreeNode*parent=root;
while(parent->LTree!=p&&parent->RTree!=p)
{
if(parent->value>p->value)
parent=parent->LTree;
else
parent=parent->RTree;
}
return parent;
}
TreeNode*Btree::FindMinValue()//查找最小值
{
TreeNode*p=root;
while(p->LTree!=NULL)
{
p=p->LTree;
}
return p;
}
TreeNode* Btree::FindMaxValue()//查找最大值
{
TreeNode*p=root;
while(p->RTree!=NULL)
{
p=p->RTree;
}
return p;
}
void Btree::showsize()//顯示節點個數
{
cout<<Nodenumber<<endl;
}
TreeNode*Btree::FindValueOfTree(int k)//查找K值 回傳指標
{
TreeNode*p=root;
while(p!=NULL&&p->value!=k)
{
if(p->value<k)
p=p->RTree;
else
p=p->LTree;
}
if(p==NULL)
{
cout<<"沒找到該值"<<endl;
return p;
}
else
{
cout<<"查找到該值"<<endl;
return p;
}
}
void::Btree::middleprintf()//呼叫中序遍歷
{
if(Nodenumber==0)
{
cout<<"該樹為空"<<endl;
return;
}
Middleprintf(root);
cout<<endl;
}
void::Btree::Middleprintf(TreeNode*p)中序遍歷
{
if(p!=NULL)
{
Middleprintf(p->LTree);
cout<<p->value<<"->";
Middleprintf(p->RTree);
}
}
void Btree::lastprintf()//后序遍歷
{
if(Nodenumber==0)
{
cout<<"該樹為空"<<endl;
return;
}
Lastprintf(root);
cout<<endl;
}
void Btree::Lastprintf(TreeNode*p)//呼叫后序遍歷
{
if(p!=NULL)
{
Lastprintf(p->LTree);
Lastprintf(p->RTree);
cout<<p->value<<"->";
}
}
void Btree::deleteValueOfTree(int k)//洗掉值為k的節點
{ TreeNode*p=FindValueOfTree(k);
if(p==NULL)
{
return;
}
TreeNode*parent=FindParentofNode(p);
if(p->LTree==NULL&&p->RTree==NULL)//如果洗掉的是葉節點的操作
{
if(p==root)//如果只有一個根節點的操作
{
delete p;
root=NULL;
Nodenumber--;
}
else if(parent->LTree==p)
{
parent->LTree=NULL;
delete p;
Nodenumber--;
}
else
{
parent->RTree=NULL;
delete p;
Nodenumber--;
}
}
else if(p->LTree!=NULL&&p->RTree!=NULL)//要洗掉的節點有兩個孩子
{
TreeNode*LeftmaxNode=p->LTree;
while(LeftmaxNode->RTree!=NULL) //找要洗掉的節點的左子樹的最大值
{
LeftmaxNode=LeftmaxNode->RTree;
}
p->value=https://bbs.csdn.net/topics/LeftmaxNode->value;//將洗掉節點的值改成該最大值
TreeNode*pos=FindParentofNode(LeftmaxNode);//找到左子樹最大值節點的父節點
if(pos->LTree==LeftmaxNode)
pos->LTree=LeftmaxNode->LTree;//將父節點指向該洗掉節點的指標改成指向洗掉節點的左子樹
else
pos->RTree=LeftmaxNode->LTree;
delete LeftmaxNode;//洗掉左子樹值最大的節點
Nodenumber--;
}
else if(p->LTree!=NULL&&p->RTree==NULL)//要洗掉的節點只有一個左孩子的操作
{
if(p==root)
{
root=p->LTree;
delete p;
Nodenumber--;
}
else if(parent->LTree==p)
{
parent->LTree=p->LTree;
delete p;
Nodenumber--;
}
else
{
parent->RTree=p->LTree;
delete p;
Nodenumber--;
}
}
else if(p->LTree==NULL&&p->RTree!=NULL) //要洗掉的節點只有一個右孩子的操作
{ if(p==root)
{
root=p->RTree;
delete p;
Nodenumber--;
}
else if(parent->LTree==p)
{
parent->LTree=p->RTree;
delete p;
Nodenumber--;
}
else
{
parent->RTree=p->RTree;
delete p;
Nodenumber--;
}
}
}
int main(){
Btree a;
a.insertNode(8);
a.insertNode(5);
a.insertNode(10);
a.insertNode(1);
a.insertNode(7);
a.insertNode(9);
a.insertNode(11);
cout<<"該樹的先序遍歷順序是:";
a.firstprintf();
cout<<"該樹的節點數是:";
a.showsize();
cout<<"該樹的節點中的最小值是：";
cout<<a.FindMinValue()->value<<endl;
cout<<"該樹的節點中的最大值是: ";
cout<<a.FindMaxValue()->value<<endl;
cout<<"該樹的中序遍歷順序是:";
a.middleprintf();
cout<<"該樹的后序遍歷順序是:";
a.lastprintf();
cout<<"要洗掉的值是8"<<endl;
a.deleteValueOfTree(8);
cout<<"洗掉該節點后的先序遍歷是:";
a.firstprintf();
return 0;
}
剛學沒多久
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/237347.html
標籤：C++ 語言
上一篇：ZCMU 1317 親和數
下一篇：ZCMU 1318 偶數求和