【2月8日笔记】二叉树遍历复习&二叉搜索树&STL实现二叉搜索树

一、二叉树的递归遍历

void PreOrderTraversal(BinTree BT) {
	if (BT) {
		printf("%d", BT->Data);
		PreOrderTraversal(BT->Left);
		PreOrderTraversal(BT->Right);
	}
}
void InOrderTraversal(BinTree BT) {
	if (BT) {
		InOrderTraversal(BT->Left);
		printf("%d", BT->Data);
		InOrderTraversal(BT->Right);
	}
}
void PostOrderTraversal(BinTree BT) {
	if (BT) {
		PostOrderTraversal(BT->Left);
		PostOrderTraversal(BT->Right);
		printf("%d", BT->Data);
	}
}

二、二叉搜索树的查找操作

迭代实现：

Position IterFind(int X, BinTree BST) {
	while (BST) {
		if (X > BST->Data) {
			BST = BST->Right;
		}
		else if (X < BST->Data) {
			BST = BST->Left;
		}
		else {
			return BST;
		}
	}
	return NULL;//查找失败
}

递归实现：

Position Find(int X, BinTree BST) {
	if (!BST) {
		return NULL;
	}
	if (X > BST->Data) {
		return Find(X, BST->Right);
	}
	else if (X < BST->Data) {
		return Find(X, BST->Left);
	}
	else {
		return BST;
	}
}

插入操作：

	BinTree Insert(Element Type X,BinTree BST){
		if(!BST){
			//若原树为空，生成并返回一个结点的二叉搜索树
			BST=malloc(sizeof(struct TreeNode));
			BST->Data=X;
			BST->Left=BST->Right=NULL;
		}else{//开始找要插入元素的位置
			if(X<BST->Data)
				BST->Left=Insert(X,BST->Left);
					//递归插入左子树
			}else if(X>BST->Data)
				BST->Right=Insert(X,BST->Right);
			//else X已经存在，什么也不做
		return BST;
	}

删除操作：
1、要删除的是叶结点，直接删除，并再修改其父结点指针，置为NULL
2、要删除的结点只有一个孩子结点：将其父结点的指针指向要删除结点的孩子结点
3、要删除的结点有左、右两棵子树：
用另一结点替代被删除结点：右子树的最小元素或者左子树的最大元素

BinTree Delete(int X,BinTree BST){
		Position Tmp;
		if(!BST)printf("要删除的元素未找到");
		else if(X<BST->Data)
			BST->Left=Delete(X,BST->Left);//左子树递归删除，将新的左子树根结点的地址赋给Left
		else if(X>BST->Data)
			BST->Right=Delete(X,BST->Right);//右子树递归删除
		else{//找到要删除的结点
			if(BST->Left&&BST->Right){//被删除的结点有左右两个子结点
				Tmp=FindMin(BST->Right);//在右子树中找最小的元素填充删除结点
				BST->Data=Tmp->Data;
				BST->Right=Delete(BST->Data,BST->Right);
							//在删除结点的右子树中删除最小元素
			}else{//这种情况为被删除结点有一个或无子结点
				Tmp=BST;
				if(!BST->Left)//有右孩子或无子结点
					BST=BST->Right;
				else if(!BST->Right)
					BST=BST->Left;
				free(Tmp);
			}
		}
		return BST;
	}

三、STL中的平衡二叉树数据结构

为什么要使用平衡二叉树，而不使用普通的容器排序+二分查找呢？因为有时需要在大量增加、删除数据的同时，还要进行大量数据的查找
希望增加数据、删除数据、查找数据都能在log(n)复杂度内完成
所以可以使用”平衡二叉树“数据结构存放数据，在STL中，就是以下四种”排序容器“：
	multiset  set  multimap   map
multiset用法

multiset<T> st;

定义了一个multiset变量st，st里面存放T类型的数据，并且自动排序，开始St为空
排序规则：若a<b 为true，则a排在b前面
st.insert添加元素，st.find查找元素，st.erase删除元素
复杂度都是log(n)

multiset上的迭代器：

multiset<T>::iterator p;

	p是迭代器，相当于指针，可用于指向multiset中的元素，访问multiset中的元素要通过迭代器
	st.begin(),返回值类型是multiset<T>::iterator,是指向st头一个元素的迭代器
	St.end(),返回值类型为multiset<T>::iterator，是指向st中最后一个元素后面的迭代器
	对迭代器++，其指向容器中下一个元素，--则令其指向上一个元素

实例：

#include<iostream>
#include<cstring>
#include<set>
using namespace std;
int main(){
	multiset<int> st;
	int a[10]={1,14,12,13,7,13,21,19,8,81};
	for(int i=0;i<10;i++){
		st.insert(a[i]);
	}
	multiset<int>::iterator i;//i是迭代器，相当于指针
	for(i=st.begin();i!=st.end();i++){
		cout<<*i<<",";
	}
	cout<<endl;
			
}

其他用法：

		i=st.find(22)//查找22，返回值是迭代器类型，如果找不到，则返回st.end() 
		if(i==st.end()){
			cout<<"Not found"<<endl;
		}
		st.insert(22);
		i=st.find(22);
		if(i==st.end()){
			cout<<"Not found"<<endl;
		}else{
			cout<<"found:"<<*i<<endl;
		}
		i=st.lower_bound(13)
		//返回最靠后的迭代器it，使得[begin(),it)中的元素都在13前面
		cout<<*i<<endl;
		i=st.upper_bound(8);
		//返回最靠前的迭代器it，使得[it,end())中的元素都在8后面
		cout<<*i<<endl;
		st.erase(i);//删除迭代器i指向的元素
		for(i=st.begin();i!=st.end();i++){
			cout<<*i<<",";
		}
		return 0;