数据结构总结之三—动态查找表

1.前言

提到动态的话，就要想到链表了，所以这一次主要是总结，在链表上如何实现查找。

2.二叉排序树

2.1什么是二叉排序树

若树的左子树不为空，那么左子树上所有节点的值均小它的根节点的值。若他的右子树不为空，那么右子树上所有节点的值，均大于他的根节点的值。这个定义，感觉上其实是跟堆基本上没有差别，可以学完二叉排序树之后再去学下堆。

2.2二叉排序树中的查找

pnode search(Bittree T, int key) 
{
	if(!T)
        return ERROR;
    if (key == T->data);
	return T;
	else if (key > T->data)
		search(T->rchild, key);//根据二叉排序树的特性
								//右子树节点的值要大于根节点的值
								//所以比根节点大师，要到右子树中进行搜索
	else if (key < T->data)
		search(T->lchild, key);
	return ERROR;
}

2.3二叉排序树的插入和删除

二叉排序树的结构不是一次生成的，而是在查找过程中，如果发现不存在于二叉排序树中，则进行插入操作，那么仿照上面的搜索算法，我们可以采用下面的方法来实现二叉树的插入

struct node
{
	int data;
	struct node* lchild;
	struct node* rchild;
}node,*pnode;

pnode  search(pnode T, int key,pnode p,pnode &f) 
{
	if (!T) 
	{
		f = p;
		return NULL;
	}
	if (key == T.data) 
	{
		return T;
	}
	else if(key>T.data)
	{
		search(T->rchild, key,T,f);
	}
	else if(key<T.data)
	{
		seach(T->lchild, key,T,f);
	}
}

pnode insert(Bittree T,int key)
{
	pnode p, f;
	if (!search(T, key,p,f)) 
	{
		pnode pnew = (pnode)malloc(sizeof(node));
		pnew->data = key;
		pnew->lchild = NULL;
		pnew->rchild = NULL;
		if (key > f->data) 
		{
			f->rchild = pnew;
		}
		else 
		{
			f->lchild = pnew;
		}
		return true;
	}
	return false;
}

2.3二叉排序树的删除操作

将一个节点从二叉排序树中删除，总共有三种情况

1.被删除节点为叶子节点，左右子树为空，那么直接删除即可

2.被删除节点只有左子树，或者右子树那么直接令，子树成为其前继节点的子树即可。

3.被删除节点既有左子树，又有右子树的情况

1.2的实现，都比较简单，我们主要来看第三种情况的具体实现。先进行分析。

设想：直接让左子树的节点，接到上一个节点，右子树节点成为左子树的右节点。**但是！**可能会出现，左子树的右节点也不为空，这个时候你要怎么办呢？

所以上面的设想是不靠谱的，是极不科学的。当我们建立好二叉排序树之后，我们可以按照二叉树的中序遍历来得到一个有序序列。我们只需要保证删除完节点后二叉排序的树中序遍历得到的有序序列变化不大即可。但实现起来较为麻烦我们采用另一种方法。将被删除节点的右子树接在左子树最右边的右子树上，被删除的节点用被删除节点的左子树替代

#include <stdio.h>
#include <stdlib.h>
typedef struct node 
{
	int data;
	struct node* lchild;
	struct node* rchild;
}node,*pnode;

void delete_T(pnode &p,pnode &fp) 
{
	pnode q = NULL;
	pnode s;
	pnode t=NULL;
	bool is_left=false;
	if(fp->lchild==p)
	{
		is_left=true;
	}
	if (!p->lchild) 
	{
		q = p;
		p = p->rchild;
		if(is_left)
		fp->lchild=p;
		else
		fp->rchild=p;
		free(q);
	}
	else if(!p->rchild)
	{
		q = p;
		p = p->lchild;
		if(is_left)
		fp->lchild=p;
		else
		fp->rchild=p;
		free(q);
	}
	else
	{
		q = p;
		s = q->lchild;
		while(s)
		{
			t = s;
			s = s->rchild;
		}
		t->rchild = p->rchild;
		q = q->lchild;
		free(p);
	}
	return;
}
pnode search(pnode T, int key, pnode p, pnode &f,pnode &father_of_pnew)
{
	if (!T)
	{
		f = p;
		return NULL;
	}
	if (key == T->data)
	{
		f = T;
		father_of_pnew=p;
		return T;
	}
	else if (key > T->data)
	{
		search(T->rchild, key, T, f,father_of_pnew);
	}
	else if (key < T->data)
	{
		search(T->lchild, key, T, f,father_of_pnew);
	}
}

bool insert(pnode T, int key)
{
	pnode p = NULL;
	pnode f = NULL;
	pnode pf=NULL;
	if (!search(T, key, p, f,pf))
	{
		pnode pnew = (pnode)malloc(sizeof(node));
		pnew->data = key;
		pnew->lchild = NULL;
		pnew->rchild = NULL;
		if (key > f->data)
		{
			f->rchild = pnew;
		}
		else
		{
			f->lchild = pnew;
		}
		return true;
	}
	return false;
}

void init(pnode &T)
{
	int n;
	int number;
	scanf(\"%d\", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf(\"%d\", &number);
		if (i == 1)
			T->data = number;
		else
			insert(T, number);
	}
}

void visit(pnode T)
{
	if (!T)
	return;
	visit(T->lchild);
	printf(\"%d\", T->data);
	visit(T->rchild);
}


int main() 
{
	pnode T;
	pnode father_of_pnew;
	pnode s=NULL;
	T = (pnode)malloc(sizeof(node));
	T->lchild = NULL;
	T->rchild = NULL;
	init(T);
	visit(T);
	pnode pnew;
	search(T, 17,s,pnew,father_of_pnew);
	delete_T(pnew,father_of_pnew);
	puts(\"\");
	visit(T);
	return 0;
}

完整代码如上，另外需要注意的是，千万不要按照书上的那个删除节点来写，卡了半天，orz.删除节点的正确操作时，找到父亲节点，然后让父亲节点指向被删节点的下一个节点，再free被删除的节点。千万！千万！千万！不要按照课本上的去实现！！！