基于C++实现二叉排序树数据结构

1．定义（BSTTree）

二叉排序树或者是一棵空树，或者是具有如下特性的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于根结点的值
若它的右子树不空，则右子树上所有结点的值均大于根结点的值
它的左、右子树也都分别是二叉排序树。
注：只要有一个结点不满足就不是二叉排序树
通常，取二叉链表作为二叉排序树的存储结构

typedef struct BiTNode {
    TElemType data;
    struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;
1
2
3
4

2．二叉排序树的查找算法

若二叉排序树为空，则查找不成功
否则：
若给定值等于根结点的关键字，则查找成功
若给定值小于根结点的关键字，则继续在左子树上进行查找
若给定值大于根结点的关键字，则 继续在右子树上进行查找

Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p ) {
    // 在根指针 T 所指二叉排序树中递归地查找其
	// 关键字等于 key 的数据元素，若查找成功，
	// 则返回指针 p 所指该数据元素的结点，并返回
	// 函数值为 TRUE; 
	if (!T){
	    p = f;
		return FALSE; // 查找不成功
	}
	else if ( EQ(key, T->data.key) ){
	    p = T;  return TRUE;//查找成功
	}
	else  if ( LT(key, T->data.key) ){
		SearchBST (T->lchild, key, T, p );  // 在左子树中继续查找
    }
	else{
	    SearchBST (T->rchild, key, T, p );  // 在右子树中继续查找
	}
} // SearchBST
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3．二叉排序树的插入算法

根据动态查找表的定义，“插入”操作在查找不成功时才进行
若二叉排序树为空树，则新插入的结点为新的根结点
否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到

4．二叉排序树的删除算法

和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。
可分三种情况讨论：

• 被删除的结点是叶子结点：其双亲结点中相应指针域的值改为“空”
• 被删除的结点只有左子树或者只有右子树：其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树”
• 被删除的结点既有左子树，也有右子树：以其中序前驱（左子树的最右无右子树的结点）替代之，然后再删除该前驱结点

结论

• 一个无序序列（10，18，3，8，12，2，7，3）可以通过构造一棵二叉排序树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程
• 每次插入的新结点都是二叉排序树的叶子结点，在进行插入操作时，不必移动其它结点，仅需修改某个结点的指针由空变为非空即可。这就相当于在一个有序序列上插入一个元素而没有移动其它元素。这个特性告诉我们，对于需要经常插入和删除记录的有序表采用二叉排序树结构更为合适。

5．查找性能分析

值相同的 n 个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同
不失一般性，假设长度为 n 的序列中有 k 个关键字小于第一个关键字，则必有 n-k-1 个关键字大于第一个关键字,由它构造的二叉排序树平均查找长度是 n 和 k 的函数。