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

Love The Way You Lie 2022-08-06 15:03 103阅读 0赞

(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:**

![Center][]

[Center]: /images/20220806/897e9857ab6a43adb1763e623c59650a.png