树与二叉排序树的总结

1.基本概念思维导图

2.详细笔记

二叉树的结点至多（满二叉）：2^k-1(这里k为深度)

二叉排序树相关

基本操作伪代码

bool InsterBST(BSTNode*& bt, KeyType k)
{
	if(bt为空)
		插入的节点为根节点；
	else if(k == bt中存在的结点)
		return false;
	else if(k<bt->key)
		插到左子树；
	else
		插到右子树；
}

BSTNode* SearchBST(BSTNode* bt, KeyType k)//查找
{
    if(bt == NULL 或 bt->key == k)
        return bt;
    if(k<bt->key)
    	查找左子树；
    else
    	查找右子树；
}

bool deletek(BSTNode*& bt, KeyType k)
{}

void Delete(BSTNode*& p)//被删节点只有左或右子树
{
	if (p->rchild == NULL)//只有左子树
		用左孩子代替p；
	else//只有右子树
		用右孩子代替p；
}

void Delete1(BSTNode* p, BSTNode*& r)//被删的节点p左右子树都有，r指向p的左孩子
{
	if(r->rchild != NULL)
		找到最右结点;
	else
	{
		p->key = r->key;
		删除r;
	}
	
	
}

具体代码

1. 定义，构建二叉排序树

定义

typedef struct node {
	KeyType key;//关键字
	struct node* lchild, * rchild;//左、右孩子指针
}BSTNode;

构建

BSTNode* CreateBST(KeyType a[], int n)//插入
{//a[]存着n个要生成的结点的数
	BSTNode* bt = NULL;//bt初始化
	int i = 0;
	while (i < n)
	{
		InsterBST(bt, a[i]);
		//调用插入函数
		i++;
	}
	return bt;
}

2. 插入节点

bool InsterBST(BSTNode*& bt, KeyType k)
{//在二叉树中插入关键字为k的结点，若插入返回真，否则则返回假。
	if (bt == NULL)
	{//原树为空，插入的新节点为根节点
		bt = new BSTNode;
		bt->key = k; bt->lchild = bt->rchild = NULL;
		return ture;
	}
	else if (k == bt->key) return false;
	//树中有k结点了
	else if (k < bt->key) return InsterBST(bt->lchild, k);
	//k比key小，插入左子树
	else return InsterBST(bt->rchild, k);
	//k比key大，插入右子树
}

3. 查找

BSTNode* SearchBST(BSTNode* bt, KeyType k)
{//查找k元素
	if (bt == NULL || bt->key == k)
		return bt;
	if (k < bt->key)
		return SearchBST(bt->lchild, k);
	//k小于key，在左子树中查找
	else
		return SearchBST(bt->rchild, k);
	//k大于key，在右子树中查找
}  

4. 删除

删除节点为叶子节点

bool deletek(BSTNode*& bt, KeyType k)
{//在树中删除k,k在叶子结点
	if (bt == NULL)  return false;
	//没找到k或树为空，删除失败
	else
	{
		if (k == bt->key)
		{//如果key就是要找的k，直接删除
			delete(bt);
			return true;
		}
		if (k < bt->key)
			deletek(bt->lchild, k);
		//k比key小，在左子树中寻找k再删除
		else
			deletek(bt->rchild, k);
		//k比key大，在右子树中寻找k再删除
	}
	
}

删除的节点只有左或右子树

void Delete(BSTNode*& p)
{//删除节点p
	BSTNode* q;
	if (p->rchild == NULL)//只有左子树
	{
		q = p;
		p = p->lchild;
		delete q;
	}
	else if (p->lchild == NULL)//只有右子树
	{
		q = p;
		p = p->rchild;
		delete(q);
	}
	else Delete1(p, p->lchild);//左右子树都有
}

删除的节点有左右子树

void Delete1(BSTNode* p, BSTNode*& r)
{//被删的节点p左右子树都有，r只向p的左孩子
	BSTNode* q;
	if (r->rchild != NULL)
		Delete1(p, r->rchild);
	//找到p左子树的最右节点
	else
	{
		p->key = r->key;
		//用r（此时为最右节点）代替p，此时，原来的p没了
		q = r;
		r = r->lchild;
		//用r（此时为最右节点）的左孩子代替r
		delete(q);//将r删除
	}
}

最后叭一叭

树作为动态查找表的一种形式，较为高效的帮我们进行查找，除了查找方便，相对于静态查找的线表，树的修改也很方便。

第一次写博客，感觉还是可以的(●ˇ∀ˇ●)