【二叉排序树的删除】结点删除成功了，但中序遍历时却错了，咋回事
【二叉排序树的删除】结点删除成功了，但中序遍历时却错了，怎么回事？
------解决方案--------------------
p只是一个局部指针变量，其实在你的树的结构体中真正指向下面节点的是LeftChild和RightChild，但是这两个指针在你删除一个节点的时候并没有被修改，所以即便你更改了p的值，但是你没有修改LeftChild和RightChild的值，在你遍历的时候还是使用LeftChild和RightChild的值，就会指向已经被delete的无效内存空间了。距离说明：LeftChild=a,p=LeftChild；删除后a内存被释放了，p=b了，但是LeftChild还是a，而你遍历时候用的还是LeftChild的值。
#include<iostream>
using namespace std;
const int MaxLen=20;
bool flag=false;
class Node
{
public:
int key;
Node *LeftChild;
Node *RightChild;
Node():LeftChild(NULL),RightChild(NULL){}
};
class BiSoTree
{
private:
Node *Root;
int vernum;
void InOrder(Node *);
void Search_Inseart(Node *,int);
void Delete(Node *&t);
public:
BiSoTree():Root(NULL){}
void Search_Inseart1(int);
void InOrder();
};
void BiSoTree::Search_Inseart1(int key)
{
Search_Inseart(Root,key);
}
//本程序中不关心&Root、&p的值，只关心Root、p的值。
void BiSoTree::Search_Inseart(Node *p,int k) // 也可以不用传Root过去，直接在函数里使用Root,Node *p=Root;
{
Node *pre=NULL;
while(p!=NULL)
{
pre=p; // pre始终为p的父亲
if(k>p->key)
p=p->RightChild;
else if(k<p->key)
p=p->LeftChild;
else if(k==p->key)
{
Delete(p);
cout<<p<<endl; // 输出是0，可以证明结点已删除
InOrder(); // 中序遍历到55的右孩子时，输出不是0，竟然是一个地址？
cout<<endl;
return;
}
}
if(p==NULL) // p跳到根结点或者叶子结点
{
if(flag)
return;
else
{
p=new Node(); // p创建一个新的结点
p->LeftChild=NULL;
p->RightChild=NULL;
p->key=k;
if(pre==NULL)
Root=p;
else
{
if(pre->key<p->key)
pre->RightChild=p; // 让原本指向空的右孩子指向一个新的p结点
else
pre->LeftChild=p;
}
}
}
}
void BiSoTree::Delete(Node *&t) // 这个是指针的别名，如果传入的是&p，用2级指针**t的话，
*t->LeftChild为什么会报错
{
Node *q=t,*s;
if(t->LeftChild==NULL)
{
t=t->RightChild;
delete q;
}
else if(t->RightChild==NULL)
{
t=t->LeftChild;
delete q;
}
else
{
s=t->LeftChild;
while(s->RightChild)
{
q=s;
s=s->RightChild;
}
t->key=s->key;
if(q!=t)
q->RightChild=s->LeftChild;
else
q->LeftChild=s->LeftChild;
delete s;
}
}
void BiSoTree::InOrder()
{
InOrder(Root);
}
void BiSoTree::InOrder(Node *T)
{
if(T!=NULL)
{
InOrder(T->LeftChild);
cout<<T->key<<" ";
InOrder(T->RightChild);
}
}
int main()
{
BiSoTree b;
int t,n,array[MaxLen],n1,array1[MaxLen],i,j;
cin>>t;
while(t--)
{
cin>>n;
for(i=0;i<n;i++)
cin>>array[i];
cin>>n1;
for(i=0;i<n1;i++)
cin>>array1[i];
for(i=0;i<n;i++)
b.Search_Inseart1(array[i]);
b.InOrder();
cout<<endl;
flag=true;
for(i=0;i<n1;i++)
b.Search_Inseart1(array1[i]);
}
return 0;
}
Sample Input
1
6
22 33 55 66 11 44 // 建立一个二叉排序树
3 // 删除3个结点
66
22
77 // 如果结点不存在则不做改变
Sample Output
11 22 33 44 55 66
11 22 33 44 55
11 33 44 55
11 33 44 55
------解决方案--------------------
p只是一个局部指针变量，其实在你的树的结构体中真正指向下面节点的是LeftChild和RightChild，但是这两个指针在你删除一个节点的时候并没有被修改，所以即便你更改了p的值，但是你没有修改LeftChild和RightChild的值，在你遍历的时候还是使用LeftChild和RightChild的值，就会指向已经被delete的无效内存空间了。距离说明：LeftChild=a,p=LeftChild；删除后a内存被释放了，p=b了，但是LeftChild还是a，而你遍历时候用的还是LeftChild的值。