[数据结构] 树和二叉树-二叉排序树(BST)

二叉排序树

二叉排序树(Binary Search Tree)又叫二叉查找树。要么是一棵空树,要么是一颗具有下列特性的二叉树:

  • 如果左子树不为空,那么左子树上所有结点关键字值都小于根节点。
  • 如果右子树不为空,那么右子树上所有结点关键字值都大于根节点。
  • 左右子树分别是一颗BST。

也就是说,BST的中序遍历一定是升序。

BST构造和插入

#include <iostream>
using namespace std;
 
// BST的结点
typedef struct node
{
	int key;
	struct node *lChild, *rChild;
}Node, *BST;
 
// 在给定的BST中插入结点,其数据域为element, 使之称为新的BST
bool BSTInsert(Node * &p, int element)
{
	if(NULL == p) // 空树
	{
		p = new Node;
		p->key = element;
		p->lChild = p->rChild = NULL;
		return true;
	}
 
	if(element == p->key) // BST中不能有相等的值
		return false;
 
	if(element < p->key)  // 递归
		return BSTInsert(p->lChild, element);
 
	return BSTInsert(p->rChild, element); // 递归
}
 
// 建立BST
void createBST(Node * &T, int a[], int n)
{
	T = NULL; 
	int i;
	for(i = 0; i < n; i++)
	{
		BSTInsert(T, a[i]);
	}
}
 
// 先序遍历
void preOrderTraverse(BST T)
{
	if(T)
	{
		cout << T->key << " ";
		preOrderTraverse(T->lChild);
		preOrderTraverse(T->rChild);
	}
}
 
// 中序遍历
void inOrderTraverse(BST T)
{
	if(T)
	{
		inOrderTraverse(T->lChild);
		cout << T->key << " ";
		inOrderTraverse(T->rChild);
	}
}
 
int main()
{
	int a[10] = {4, 5, 2, 1, 0, 9, 3, 7, 6, 8};
	int n = 10;
	BST T;
 
	// 并非所有的a[]都能构造出BST,所以,最好对createBST的返回值进行判断
	createBST(T, a, n);
 
	preOrderTraverse(T);
	cout << endl;
 
	inOrderTraverse(T);
	cout << endl;
 
	return 0;
}

BST的查找

BST BST_Search(BST root,int key)
{
    while(root != NULL && root->key != key)
    {
        if(key < root->key)
            root = root->lchild;
        else
            root = root->rchild;
    }
    return root;
}

BST的删除

BST的删除操作有三种情况:

  1. 如果被删除结点是叶子结点,可以直接删除,不会破坏BST的性质。
  2. 如果被删除结点z只有一颗左子树或一颗右子树,则让z的子树成为z父节点的子树,代替z的位置。
  3. 如果被删除结点z有两颗子树,则令z的直接后继(或直接前驱)代替z,然后从BST中删去这个直接后继(或直接前驱),这样就转换成第一或第二种情况。

例1:删除数据为16的节点,是叶子节点,可以直接删除《[数据结构] 树和二叉树-二叉排序树(BST)》

 

例2:删除数据为25的节点,它下面有唯一一个子节点35, 上移到替换之 

《[数据结构] 树和二叉树-二叉排序树(BST)》

例3:删除节点数据为5的节点,找到被删除节点右子树的最小节点(或者左子树最大结点)。需要一个临时变量successor,将11节点下面的子节点进行查询,找到右子树最小节点7,并把右子树最小节点7替换被删除节点,维持二叉树结构(8是后插进来的)。如下图 

《[数据结构] 树和二叉树-二叉排序树(BST)》

BST的查找效率分析

对于高度为h的BST,插入和删除的时间复杂度都是O(h)。但是在最坏的情况下,即构造的BST输入序列是有序的,则会形成一个倾斜的单支树,此时BST的性能显著变坏,树的高度也增加为元素个数N。

由上可知,BST查找算法的平均查找长度主要取决于树的高度。

  1. 若二叉树是一个只有左子树或右子树的单支树,平均查找长度和单链表相同,为O(n);
  2. 若树中每个结点左右子树高度大致相同时,树高为logN。则平均查找长度与logN成正比,查找的平均时间复杂度在O(logN)数量级上。
    原文作者:lixin051435
    原文地址: https://blog.csdn.net/tsfx051435adsl/article/details/100154504
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞