二叉排序树的删除结点删除成功了，但中序遍历时却错了，怎么回事

#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的值。

而且恕本人水平有限，题主的这段删除代码本人真心没懂，有没有高手给本人解释一下啊？

    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;
    }

引用:

Quote: 引用:
删除部分有问题，删除之后没有重置父节点的左右孩子，导致父节点指向了被delete的节点，所以遍历时会崩溃

干嘛要重置？不是只要修改孩子的值为0不就行了吗？而且delete的是另一个结点q，q的内容只是复制p而已，把q delete 对p和父节点没影响吧？

你的delete函数的前面两个if里面跟你最后的else里面的操作是不一样的。