一、二叉排序树

二叉排序树的构造：将第一个值作为根结点，依次判断后边的值与根结点的值得关系，若插入值小于根结点的值，则该值作为根结点的左子树，若插入值大于根结点的值，则该结点作为根结点的右子树。
例：5 3 2 8 1 4 6 9 7

通过上述例子，我们不难发现：
1.若左子树为空，则左子树的值均小于根结点的值。
2.若右子树为空，则右子树的值均大于根结点的值。
3.左右子树本身也是二叉排序树。

1.二叉树结点的查找

从根结点开始，沿某个分支，逐层向下进行比较的过程，若二叉树非空，则根结点与定值比较，若定值大于根，则在右子树中查找，反之则在左子树中查找。
二叉排序树的非递归查找算法：

BSTNode *BST_Search(BiTree T,ElemType e,BSTNode *&p){
	p=NULL;		//p指向被查找结点的双亲，用于插入、删除操作中
	while(T!=NULL&&key!=T->data){
		p=T;
		if(key<T->data)
			T=T->lchild;
		else
			T=T->rchild;
	}
	return T;
}

2.二叉排序树的插入

二叉排序树的插入过程：若树为空则直接插入，否则与根结点比较，若值小于根结点，则插入到左子树，否则插入右子树，递归这个过程插入结点。通过以上过程的分析，则插入的结点一定是某个叶子结点。

int BST_insert (BiTree &T，KeyType k){
	if(T==NULL){
		T=(BiTree *)malloc(sizeof(BSTNode));
		T->key=k;
		T->lchild=NULL;
		T->rchild=NULL;
		return 1;
	}
	else if(k==T->key)     //树的根结点等于要插入的值
		return 0;
	else if(k<T->key)
		return BST_insert(T->lchild,k);
	else
		return BST_insert(T_>rchild,k);
}

二、二叉排序树的构造

1.二叉排序树构造的代码如下：

void create_BST(BiTree &T,keytype str[],int n){				//n表示总元素的个数
	T=NULL；
	int i=0;
	while(i<n){
		BST_insert(T,str[i]);
		i++;
	}
}

2.二叉排序树单个结点的删除
1)若为叶子结点则直接删除。
例如：在下图所示的树中删除结点7。

2)若只有一棵左子树或者右子树，则让被删除的结点的子结点代替父结点。
例如：在下图所示的树中删除结点8。

3)若结点只有左右两棵子树，则左右子树中找中序第一个子女填补。
例如：在下图所示的树中删除结点78。
二叉排序树的查找效率（平均查找长度）
例：求下图所示的二叉排序树的平均查找长度

平均查找长度：
ASL=(1+22+34+42+51)/10=3
二叉排序树的插入、删除操作可通过修改指针实现，无需移动结点，平均执行时间是O(log₂n)

三、平衡二叉树

考虑下图所示的二叉树：

其平均查找长度ASL=（1+2+3+4+5+6)/6=3.5
为了避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除二叉树的结点时，要保证任意结点的高度差不超过1。
平衡因子=左子树高度-右子树高度
平衡因子的值只能是1,0，-1。

1.平衡二叉树的插入

1)检查是否因插入导致不平衡
2)若不平衡先找到插入路径上离插入结点最近的不平衡因子绝对值大于1的结点A，在对以A为根的子树在保持二叉排序树特征的前提上，调整各个结点的位置关系，使之达到平衡。

LL平衡旋转（右单旋转）
插入的结点在某结点的左孩子的左子树上，且导致了该结点的不平衡

RR平衡旋转（左单旋转）
插入的结点在某结点的右孩子的右子树上，且导致了该结点的不平衡

LR平衡旋转
插入的结点在某结点的左孩子的右子树上，且导致了该结点的不平衡
1.插入节点为某结点的左孩子的右子树的左孩子

2.插入节点为某结点的左孩子的右子树的右孩子

RL平衡旋转
插入的结点在某结点的右孩子的左子树上，且导致了该结点的不平衡
1.插入节点为某结点的右孩子的左子树的左孩子

2.插入节点为右孩子的左子树的右孩子

2.霍夫曼树和霍夫曼编码

1.霍夫曼树的构造步骤：
例：现有一篇报文，报文中涉及的字母有a , b , c , d , e , f , g , h ，他们的访问频率依次为
13 , 2 , 8 , 2 3 , 11 , 7 , 9 , 6 ，请设计霍夫曼编码使得报文的长度最短（并画出霍夫曼树）。
1.将集合中的权值按照访问频率从小到大排序
2 , 6 , 7 , 8 , 9 , 11 , 13 , 23
2.选取其中权值最小的两个结点结合作为一个新结点，其权值为两个结点之和。将新结点加入到上述结点结合中并按照权值重新排序。
3.重复过程2，直至集合中结点的数目为空。
2.霍夫曼编码
从根结点开始，将路径上所有的左子树作为用1替代，右子树用1替代：

因此得到霍夫曼编码如下：
a:101
b:0010
c:011
d:11
e:100
f:010
g:000
h:0011