算法系列笔记3(二叉查找树)

(1)二叉查找树的性质：设x为二叉查找树的一个结点。如果y是x左子树中的一个结点，则key[y]≤key[x]。如果y是x的右子树中的一个结点。则key[x]≤key[y].

(2)二叉查找树的结点中除了key域和卫星数据外，还包括left、right和p分别指向结点的左儿子、右儿子和父节点。

(3)构造一棵二叉查找树最好情况下时间复杂度为O(nlgn)，最坏情况为O(n^2)。随机化构造一棵二叉查找树的期望时间O(nlgn)。与快排和随机化快速排序算法是做相同的比较，但是顺序不一样。可以证明随机化构造一棵二叉查找树的期望高度为O(lgn).这样我们就可以在O(lgn)时间内完成动态集合的操作了，包括minimum、maximum、search、predecessor(前驱)、successor(后继)、insert及delete。

(4)二叉查找树的中序遍历就是其排列顺序，中序遍历的时间复杂度为O(n)

下面我们将对二叉查找树的创建、中序遍历及动态集合的操作minimum、maximum、search、predecessor(前驱)、successor(后继)、insert及delete分别做介绍。

1：创建与插入

这里创建一棵二叉查找树采用了两种方法，一种是普通的递归，另外一种采用的是插入(非递归)。

代码如下：

// 创建BST
void BSTree::createBST(BSTNode *p,const int &value){
	if(p == NULL)return;
	if(p->val > value){
		if(p->left == NULL){
			p->left = new BSTNode();
			p->left->val = value;
			p->left->left = NULL;
			p->left->right = NULL;
			p->left->parent = p;
		}else{
			createBST(p->left, value);
		}
	}
	else{
		if(p->right == NULL){
			p->right = new BSTNode();
			p->right->val = value;
			p->right->left = NULL;
			p->right->right = NULL;
			p->right->parent = p;
		}else{
			createBST(p->right, value);
		}
	}
}

// 插入值
void BSTree::insertBST(BSTNode *p, const int &value){
	BSTNode *y = NULL;
	BSTNode *in = new BSTNode();
	in->left = NULL;
	in->right = NULL;
	in->val = value;
	in->parent = NULL;

	while(p != NULL){
		y = p;
		if(p->val > in->val) p = p->left;
		else p = p->right;
	}
	
	if(y == NULL)
		p = in;
	else{
		in->parent = y;
		if(y->val > in->val) y->left = in;
		else y->right = in;
	}
}<strong>
</strong>

2：中序遍历

采用递归左子树、输出结点值和递归右子树就可以了。

代码如下：

//  中序遍历BST
void BSTree::inorderBST(BSTNode *p){
	if(p == NULL) return;
	if(p->left != NULL) inorderBST(p->left);
	cout << p->val << " ";
	if(p->right != NULL) inorderBST(p->right);
}

3：minimum和maximum

最小值为最左边的结点，最大值为最右边的结点。

代码如下：

// 最大值和最小值
BSTNode* BSTree::minBST(BSTNode *p){
	while(p->left != NULL)
		p = p->left;
	return p;
}

BSTNode* BSTree::maxBST(BSTNode *p){
	while(p->right != NULL)
		p = p->right;
	return p;
}

4：查找

这里给出递归和迭代两种。

代码如下：

// 查找BST
BSTNode* BSTree::searchBST(BSTNode *p, const int &value){
	if(p == NULL || p->val == value) return p;
	if(value < p->val) return searchBST(p->left, value);
	else return searchBST(p->right, value);
}

// 迭代
BSTNode* BSTree::iterSearchBST(BSTNode *p, const int &value){
	while(p != NULL && p->val != value){
		if(value < p->val) p = p->left;
		else p = p->right;
	}
	return p;
}

5：predecessor(前驱)和successor(后继)

前驱：如果p的左子树不为空，则p的左子树的最大值即为p的前驱；否则令y为p的父节点，如果y不为空，设y为其前驱，y是p的最低祖先结点，y的右孩子也是p的祖先。

后继：如果p的右子树不为空，则p的右子树的最小值即为p的后继；否则令y为p的父节点，如果y不为空，设y为其后继，y是p的最低祖先结点，y的左孩子也是p的祖先。

代码如下：

// 后继与前驱
BSTNode* BSTree::successor(BSTNode *p){
	if(p->right != NULL) return minBST(p->right);   //  如果它的右子树不为空
	BSTNode *y = p->parent;
	while(y != NULL && y->right == p){       // 如果不为空 设y为p后继, y是p的最低祖先节点，y的左孩子也是p的祖先
		p = y;
		y = p->parent;
	}
	return y;
}

BSTNode* BSTree::predecessor(BSTNode *p){
	if(p->left != NULL) return maxBST(p->left);
	BSTNode* y = p->parent;
	while(y != NULL && y->left == p){   // 如果不为空 设y为其前驱, y是p的最低祖先节点，y的右孩子也是p的祖先   如果y->right == p 则y就是前驱
		p = y;
		y = p->left;
	}
	return y;
}

6:delete

待续….

7:销毁二叉树

代码如下：

// 销毁BST
void BSTree::destroyBST(BSTNode *p){
	if(p == NULL) return;
	if(p->left != NULL){
		destroyBST(p->left);
	}
	if(p->right != NULL){
		destroyBST(p->right);
	}
	delete p;
}

完整代码：

BSTree.h

#ifndef BSTREE
#define BSTREE
#include <iostream>
using namespace std;
class BSTNode{
public:
	BSTNode *left, *right;
	BSTNode *parent;
	int val;
	//friend class BSTree;
};

class BSTree{
public:
	// 初始化根节点
	BSTree(int rootVal){
		root = new BSTNode();
		root->val = rootVal;
		root->left = NULL;
		root->right = NULL;
		root->parent = NULL;
	}
	// 创建二叉查找树
	void createBST(BSTNode *p, const int &value);

	// 中序遍历 数组排序
	void inorderBST(BSTNode *p);
	void destroyBST(BSTNode *p);

	// 查找
	BSTNode* searchBST(BSTNode *p, const int &value);
	BSTNode* iterSearchBST(BSTNode *p, const int &value);

	// 最小值和最大值
	BSTNode* minBST(BSTNode *p);
	BSTNode* maxBST(BSTNode *p);

	//  后继与前驱
	BSTNode *successor(BSTNode *p);
	BSTNode *predecessor(BSTNode *p);

	// 插入值
	void insertBST(BSTNode *p, const int &value);

	BSTNode *root;
};
#endif

BSTree.cpp

#include "BSTree.h"
#include <iostream>
using namespace std;

// 创建BST
void BSTree::createBST(BSTNode *p,const int &value){
	if(p == NULL)return;
	if(p->val > value){
		if(p->left == NULL){
			p->left = new BSTNode();
			p->left->val = value;
			p->left->left = NULL;
			p->left->right = NULL;
			p->left->parent = p;
		}else{
			createBST(p->left, value);
		}
	}
	else{
		if(p->right == NULL){
			p->right = new BSTNode();
			p->right->val = value;
			p->right->left = NULL;
			p->right->right = NULL;
			p->right->parent = p;
		}else{
			createBST(p->right, value);
		}
	}
}

//  中序遍历BST
void BSTree::inorderBST(BSTNode *p){
	if(p == NULL) return;
	if(p->left != NULL) inorderBST(p->left);
	cout << p->val << " ";
	if(p->right != NULL) inorderBST(p->right);
}

// 销毁BST
void BSTree::destroyBST(BSTNode *p){
	if(p == NULL) return;
	if(p->left != NULL){
		destroyBST(p->left);
	}
	if(p->right != NULL){
		destroyBST(p->right);
	}
	delete p;
}

// 查找BST
BSTNode* BSTree::searchBST(BSTNode *p, const int &value){
	if(p == NULL || p->val == value) return p;
	if(value < p->val) return searchBST(p->left, value);
	else return searchBST(p->right, value);
}

// 迭代
BSTNode* BSTree::iterSearchBST(BSTNode *p, const int &value){
	while(p != NULL && p->val != value){
		if(value < p->val) p = p->left;
		else p = p->right;
	}
	return p;
}

// 最大值和最小值
BSTNode* BSTree::minBST(BSTNode *p){
	while(p->left != NULL)
		p = p->left;
	return p;
}

BSTNode* BSTree::maxBST(BSTNode *p){
	while(p->right != NULL)
		p = p->right;
	return p;
}

// 后继与前驱
BSTNode* BSTree::successor(BSTNode *p){
	if(p->right != NULL) return minBST(p->right);   //  如果它的右子树不为空
	BSTNode *y = p->parent;
	while(y != NULL && y->right == p){       // 如果不为空 设y为p后继, y是p的最低祖先节点，y的左孩子也是p的祖先
		p = y;
		y = p->parent;
	}
	return y;
}

BSTNode* BSTree::predecessor(BSTNode *p){
	if(p->left != NULL) return maxBST(p->left);
	BSTNode* y = p->parent;
	while(y != NULL && y->left == p){   // 如果不为空 设y为其前驱, y是p的最低祖先节点，y的右孩子也是p的祖先   如果y->right == p 则y就是前驱
		p = y;
		y = p->left;
	}
	return y;
}

// 插入值
void BSTree::insertBST(BSTNode *p, const int &value){
	BSTNode *y = NULL;
	BSTNode *in = new BSTNode();
	in->left = NULL;
	in->right = NULL;
	in->val = value;
	in->parent = NULL;

	while(p != NULL){
		y = p;
		if(p->val > in->val) p = p->left;
		else p = p->right;
	}
	
	if(y == NULL)
		p = in;
	else{
		in->parent = y;
		if(y->val > in->val) y->left = in;
		else y->right = in;
	}
}

Main.cpp

// 二叉查找树
	int a[10] = {5,4,6, 7,2,4, 1, 8, 5, 10};
	BSTree bst(a[0]);
	for(int i = 1; i < 10; i++)
		bst.insertBST(bst.root, a[i]);  // 通过插入值来构建一棵二叉查找树  
		//bst.createBST(bst.root, a[i]);  // 通过递归操作来创建一棵二叉查找树

	// 中序遍历输出
	bst.inorderBST(bst.root);
	cout << endl;

	BSTNode *s = bst.iterSearchBST(bst.root, 5);
	cout << s->val << " 左孩子: " << s->left->val << " 右孩子: " << s->right->val <<endl;

		//  查找最小值
	BSTNode *min = bst.minBST(bst.root);
	cout << "最小值为: " << min->val << endl;

	// 查找最大值
	BSTNode *max = bst.maxBST(bst.root);
	cout << "最大值为: " << max->val << endl;

	// 后继
	BSTNode *suc = bst.successor(s);
	cout << "后继: " << suc->val << endl;

	// 前驱
	BSTNode *pre = bst.predecessor(s);
	cout << "前驱: " << pre->val << endl;
	
	// 插入6
	bst.insertBST(bst.root, 6);
	cout << "插入元素后中序遍历: " << endl;
	bst.inorderBST(bst.root);
	cout << endl;
	
	bst.destroyBST(bst.root);
	return 0;

Result:

算法系列笔记3(二叉查找树)

原文：http://blog.csdn.net/lu597203933/article/details/43420409