Xóa NODE trên cây BST

[tara95]

Code:

#include <iostream>
#include <conio.h>
using namespace std;

typedef struct tagNode
{
	int Key;
	struct tagNode *pLeft, *pRight;
} Node;

typedef Node* Tree;

void CreateTree (Tree &T)
{
	T = NULL;
}

int InsertNode (Tree &T, int x)
{
	if (T)
	{
		if (T->Key == x) return 0;
		if (T->Key > x)
			return InsertNode (T->pLeft,x);
		else
			return InsertNode (T->pRight,x);
	}
	T = new Node;
	if (T == NULL) return -1;
	T->Key = x;
	T->pLeft = NULL;
	T->pRight = NULL;
	return 1;
}

void LNR (Tree T)
{
	if (T)
	{	
		LNR (T->pLeft);
		cout << T->Key << " ";
		LNR (T->pRight);
	}
}

void SearchStandFor (Tree &p, Tree &q)
{
	if (q->pLeft)
		SearchStandFor (p,q->pLeft);
	else
	{
		p->Key = q->Key;
		p = q;
		q = q->pRight;
	}
}

int DelNode (Tree &T, int x)
{
	if (T == NULL) return 0;
	else if (T->Key > x)
		return DelNode (T->pLeft,x);
	else if (T->Key < x)
		return DelNode (T->pRight,x);
	else
	{
		Node *p = T;
		if (T->pLeft == NULL)
			T = T->pRight;
		else if (T->pRight == NULL)
			T = T->pLeft;
		else
		{
			Node *q = T->pRight;
			SearchStandFor (p,q);
		}
		delete p;
	}
}

int main ()
{
	Tree T;
	CreateTree (T);

	InsertNode (T,44);
	InsertNode (T,18);
	InsertNode (T,88);
	InsertNode (T,13);
	InsertNode (T,37);
	InsertNode (T,59);
	InsertNode (T,108);
	InsertNode (T,15);
	InsertNode (T,23);
	InsertNode (T,40);
	InsertNode (T,55);
	InsertNode (T,71);
	InsertNode (T,30);


	LNR (T);
	cout << endl;

	DelNode (T,37);
	LNR (T);

	getch ();
}

Giả sử như ở đây, mình xóa nút 37, sau đó in ra sẽ bị lỗi. Mình thử xóa 1 số nút khác, in ra vẫn bình thường. Hàm xóa nút, in cây mình thấy không sai. Mình debug thì lỗi ở chỗ in cây. Mong mọi người giải đáp thắc mắc giùm mình.

[13520747]

bạn sửa lại hàm DelNode 1 chút nha
đoạn này

else
		{
			Node *q = T->pRight;
			SearchStandFor (p,q);
		}

thành

else
		{
			SearchStandFor (p, T->pRight);
		}

chỗ này mình cũng không hiểu rõ lắm, trước đây mình chép từ trong slide ra và tham khảo một số trang mạng khác giống y như code của bạn nhưng cũng bị y chang
debug một hồi tự nhiên lóe ra ý tưởng, áp dụng vào luôn thế là được

[13520211]

sữa chổ
Node *q = T->pRight;
SearchStandFor (p,q);
thành
SearchStandFor (p,T->pRight);
trông slide sai trương hợp nếu như phần tử trái cùng của cây con phải chính là cây con phải. thì nó sẽ kéo đổi giá trị p với q. nhưng khi kéo p xuống q. thì q là một con trỏ mới mình khai báo ra. chứ không phải một con trỏ trông cây. nên nhanh con trái cảu q (nếu tồn tại) sẽ bị đứt.
dẫn đế sai.
nên phải truyền chính node cây gốc của cây con phải vào đoạn searchStandFor().
nếu hiểu rõ con trỏ sẽ thấy rõ chổ này