学习笔记（5.9-）（每天复习前一天，一周为一阶段）

#include
#define N 100
#define WHITE 0  //表示没遍历呢
#define GRAY 1   //表示遍历过，但还得回来
#define BLACK 2	 //表示这个节点的子节点 都遍历完了

int n, M[N][N];
int color[N], d[N], f[N], tt;
	
// 用递归函数实现的深度优先搜索
// 这个是真正的深搜递归

void dfs_visit(int u)
{
	int v;
	color[u] = GRAY;
	d[u] = ++tt;
	for (v = 0; v < n; v++)
	{
		if (M[u][v] == 0)continue;
		if (color[v] == WHITE)
			dfs_visit(v);//直接遍历这个节点
	}
	color[u] = BLACK;
	f[u] = ++tt;
}

void dfs() {
	int u;
	for (u = 0; u < n; u++)
		color[u] = WHITE;
	tt = 0;
	// 这个遍历，是保证所有节点，都走到。防止出现未联通的节点
	for (u = 0; u < n; u++)
	{
		if (color[u] == WHITE)
			dfs_visit(u);
	}
	for (u = 0; u < n; u++)
	{
		printf("%d %d %dn", u + 1, d[u], f[u]);
	}
}

int main()
{
	int u, v, k, i, j;

	scanf("%d", &n);

	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
			M[i][j] = 0;
	}

	for (i = 0; i < n; i++)
	{
		scanf("%d %d", &u, &k);
		u--;
		for (j = 0; j < k; j++)
		{
			scanf("%d", &v);
			v--;
			M[u][v] = 1;
		}
	}
	dfs();
	return 0;
}

在这里说一下删除操作

1. 找到要删除的点
2. 判断当前点 是否 有 左子树（因为右子树，一定是删除点的左子树了，然后删除点的左子树，插入到右子树的根的左）

# include
# include

typedef int DataType;


typedef struct node {
	DataType data;
	struct node* lchild, * rchild;
}BSTNode, * BSTree;


void InsertBST(BSTree* bst, DataType data) {
	BSTree s;
	if (*bst == NULL) {
		s = (BSTree)malloc(sizeof(BSTNode));
		s->data = data;
		s->lchild = NULL;
		s->rchild = NULL;
		*bst = s;
	}
	else if (data < (*bst)->data)
		InsertBST(&((*bst)->lchild), data);		//将s插入左子树
	else if (data >= (*bst)->data)
		InsertBST(&((*bst)->rchild), data);		//将s插入左子树
}


void CreatBST(BSTree* bst) {
	DataType data;
	*bst = NULL;
	scanf("%d", &data);
	while (data != 0) {
		InsertBST(bst, data);
		scanf("%d", &data);
	}
}


void InOrder(BSTree bst) {
	if (bst != NULL) {
		InOrder(bst->lchild);
		printf("%d ", bst->data);
		InOrder(bst->rchild);
	}
}


BSTree SearchBST_recursion(BSTree bst, DataType data) {
	if (bst == NULL)
		return NULL;
	else if (bst->data == data) {
		printf("%d", bst->data);
		return bst;
	}
	else if (bst->data > data)
		return SearchBST_recursion(bst->lchild, data);	//在左子树继续查找
	else
		return SearchBST_recursion(bst->rchild, data);	//在右子树继续查找
}


BSTree SearchBST(BSTree bst, DataType data) {
	BSTree q;
	q = bst;
	while (q) {
		if (q->data == data) {
			printf("%d", q->data);
			return q;
		}
		if (q->data > data)
			q = q->lchild;						//查找左子树
		else
			q = q->rchild;						//查找右子树
	}
	return NULL;								//查找失败
}


void DelBST(BSTree bst, DataType data) {
	BSTNode* p, * f, * s, * q;
	p = bst;
	f = NULL;
	while (p) {									//查找值为data的待删除结点	
		if (p->data == data)
			break;
		f = p;									//f指向p结点的双亲结点
		if (p->data > data)
			p = p->lchild;						//查找左子树
		else
			p = p->rchild;						//查找右子树
	}
	if (p == NULL)
		return bst;
	if (p->lchild == NULL) {				//若待删除结点p无左子树
		if (f == NULL)							//若p为原二叉排序树的根
			bst = p->rchild;
		else if (f->lchild == p)				//若p为f的左孩子
			f->lchild = p->rchild;
		else									//若p为f的右孩子
			f->rchild = p->rchild;
		free(p);
	}
	else {									//若待删除结点p有左子树
		q = p;
		s = p->lchild;
		while (s->rchild) {						//在p的左子树中查找最右下结点
			q = s;
			s = s->rchild;
		}
		if (q == p)								//结点s无右子树
			q->lchild = s->lchild;
		else
			q->rchild = s->lchild;
		p->data = s->data;
		free(s);
	}
	return bst;
}

int main() {
	BSTree bst;
	CreatBST(&bst);
	printf("中序遍历输出：");
	InOrder(bst);
	printf("n递归查找结果：");
	SearchBST_recursion(bst, 12);
	printf("n非递归查找结果：");
	SearchBST(bst, 12);
	DelBST(bst, 24);
	printf("n删除值为24的结点后中序遍历输出：");
	InOrder(bst);
	return 0;
}