【數據結構】二叉查找樹

二叉查找樹(一)之理論知識和C++實現

 

本文大部分來自skywang12345大佬的博客

http://www.cnblogs.com/skywang12345/p/3576328.html

 

概要:

這裡先對二叉樹的相關理論知識進行介紹,然後給出C++的詳細實現。

關於二叉樹的學習,需要說明的是,它並不難,不僅不難而且非常簡單。初次接觸樹的時候,我也覺得它似乎很難,而這種感覺主要來自於二叉樹有一大堆陌生的概念、性質等。當我真正實現二叉樹再回過頭來看它的相關概念的時候,發現它原來是如此的簡單!因此建議在學習二叉樹的時候,先對二叉樹的基本概念、性質有個基本了解,遇到難懂的,可以畫圖來幫助理解。在實現中我以“二叉查找樹”為例而不是二叉樹,因為二叉樹實際上沒啥大用在OI中,況且掌握了二叉查找樹,二叉樹也就自然掌握了。

 

請務必深刻理解并實踐二叉查找樹!它是後面學習AVL樹,伸展樹(splay),紅黑樹(Red Black Tree, RBT),等相關結構的基石。

 

一、樹的介紹

1.樹的定義

樹是一種這樣的數據結構:它是由n(n ≥ 1)個有限結點組成的一個具有層次關係的集合。

在計算機界內,樹是倒著生長的。

特點:

(1)每個結點有零個或多個子結點;

(2)沒有父結點的結點稱為根結點;

(3)每一個非個結點有且只有一個父結點;

(4)除了根結點以外,每個子結點可以分為多個不相交的子樹。

 

2.樹的基本術語

若一個結點有子樹,那麼該結點稱為子樹根的雙親,子樹的根是該結點的孩子,有相同雙親的結點互為兄弟。一個結點上的所有子樹上任何結點都是該結點的後裔,從根結點到某個結點的路徑上所有的結點都是該結點的祖先。

 

結點的度:結點擁有的子樹數目。

葉子:度為零的結點。

分支結點:度不為零的結點。

樹的度:樹中結點的最大的度。

 

層次:根結點的層次為1,其餘結點的層次等於該結點的雙親結點的層次加一。

樹的高度:樹中結點的最大層次。

 

二、二叉樹的介紹

1.二叉樹的定義

二叉樹是每個結點最多擁有兩個子樹的樹結構。它有五種基本形態:

2.二叉樹的性質

 

注:以下及以後的文章都按照算法導論裡面,對數lg是以二為底的,而不是以十為底。

 

性質1:二叉樹第i層上結點數最多為。

性質2:深度為k的二叉樹最多有個結點(k ≥ 1)。

性質3:包含n個結點的1二叉樹的高度至少為。

性質4:在任意一棵二叉樹中,若終端結點的個數為n0,度數為2的結點數為n2,則n0 = n2 + 1

 

2.1性質1:二叉樹第i層上結點數最多為

證明:運用歸納法:

①當i = 1時,第i層的結點數目為 = = 1。因為第1層上只有一個根結點,所有命題成立。

②假設當i > 1,第i層的結點數目為。

下面根據這個假設,推斷出“第i + 1層的結點數目為”即可。

由於二叉樹的每個結點最多有兩個孩子,顧“第i +1層上的結點數目”最多是“第i層結點數目的兩倍”。即max = 2 x 2 ^ (i – 1) = 2 ^ i。

假設成立,原命題成立。

 

2.2性質2:深度為k的二叉樹最多有(2 ^ k) – 1個結點(k ≥ 1)

證明:在具有相同深度的二叉樹中,當每一層都含有最大結點數時,其中樹中結點最多。

利用性質1可知,深度為k的二叉樹的結點數最多為:

 

 

2.3性質3:包含n個結點的1二叉樹的高度至少為lg(n + 1)。

證明:利用性質2,高度為h的二叉樹最多有,取對數有,對於包含n個結點的二叉樹的高度至少為lg(n +1)

 

2.4 性质4:在任意一棵二叉树中,若终端结点的个数为n0,度为2的结点数为n2,则n0=n2+1

证明:因为二叉树中所有结点的度数均不大于2,所以结点总数(记为n)=”0度结点数(n0)” + “1度结点数(n1)” + “2度结点数(n2)”。由此,得到等式一。
(等式一) n=n0+n1+n2
另一方面,0度结点没有孩子,1度结点有一个孩子,2度结点有两个孩子,故二叉树中孩子结点总数是:n1+2n2。此外,只有根不是任何结点的孩子。故二叉树中的结点总数又可表示为等式二。
(等式二) n=n1+2n2+1
由(等式一)和(等式二)计算得到:n0=n2+1。原命题得证!

3.满二叉树,完全二叉树和二叉查找树

3.1 满二叉树

定义:高度为h,并且由2h –1个结点的二叉树,被称为满二叉树。

 

3.2 完全二叉树

定义:一棵二叉树中,只有最下面两层结点的度可以小于2,并且最下一层的叶结点集中在靠左的若干位置上。这样的二叉树称为完全二叉树。


特点:叶子结点只能出现在最下层和次下层,且最下层的叶子结点集中在树的左部。显然,一棵满二叉树必定是一棵完全二叉树,而完全二叉树未必是满二叉树。

3.3 二叉查找树

定义:二叉查找树(Binary Search Tree),又被称为二叉搜索树。设x为二叉查找树中的一个结点,x节点包含关键字key,节点x的key值记为x.key。如果y是x的左子树中的一个结点,则y.key <= x.key;如果y是x的右子树的一个结点,则y.key >= x.key。

在二叉查找树中:
(01) 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
(02) 任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
(03) 任意节点的左、右子树也分别为二叉查找树。

 

三、二叉查找树的C++实现

1.节点定义

template<class T>
class BSTNode{
	public:T key;//鍵值
	public:BSTNode *left;//左孩子
	public:BSTNode *right;//右孩子
	public:BSTNode *p;//父親
	
        //構造方法
	public:BSTNode(T key){
		this -> key = key;
		left = right = p = NULL;
	}
	public:BSTNode(){
                key = 0;
		left = right = p = NULL;
	}
};

2.二叉查找樹定義

template<class T>
class BST{
	public:BSTNode<T> *root;//根結點 
	
	public:BST(){root = NULL};
	public:~BST(){};
	
	public:static void preOrder(BSTNode<T> *root);//前序遍歷 
	public:static void inOrder(BSTNode<T> *root);//中序遍歷
	public:static void postOrder(BSTNode<T> *root);//后序遍歷
	
	public:static BSTNode<T>* search(BSTNode<T> *root,T key);//查找key(遞歸實現) 
	public:static BSTNode<T>* iterativeSearch(BSTNode<T> *root,T key);//查找key(迭代實現) 
	
	public:static BSTNode<T>* minimum(BSTNode<T> *root);//最小key 
	public:static BSTNode<T>* maximum(BSTNode<T> *root);//最大key 
	
	public:static BSTNode<T>* successor(BSTNode<T> *root);//后繼結點 
	public:static BSTNode<T>* predecessor(BSTNode<T> *root);//前驅結點 
	
	public:static void insert(BSTNode<T>* &root,BSTNode<T> *z);//插入 
	
	public:static BSTNode<T>* remove(BSTNode<T>* &t,BSTNode<T> *z);//刪除 
	
	public:static void destroy(BSTNode<T>* &t);//銷毀 
};

 

3.遍歷

3.1前序遍歷

若二叉樹非空,則執行以下操作:

①訪問根結點

②前序遍歷左子樹

③前序遍歷右子樹

template<class T>
void BST<T>::preOrder(BSTNode<T> *root){
	if(root != NULL){
		std::cout << root -> key << " ";
		preOrder(root -> left);
		preOrder(root -> right); 
	}
}

3.2中序遍歷

若二叉樹非空,則執行以下操作:

①中序遍歷左子樹

②訪問根結點

③中序遍歷右子樹

template<class T>
void BST<T>::inOrder(BSTNode<T> *root){
	if(root != NULL){
		inOrder(root -> left);
		std::cout << root -> key << " ";
		inOrder(root -> right);
	}
}

3.3后序遍歷

若二叉樹非空,則執行以下操作:

①后序遍歷左子樹

②后序遍歷右子樹

③訪問根結點

template<class T>
void BST<T>::postOrder(BSTNode<T> *root){
	if(root != NULL){
		postOrder(root -> left);
		postOrder(root -> right);
		std::cout << root -> key << " ";
	}
}

4.查找

查找就類似於二分查找,因為二叉查找樹的性質

4.1遞歸版本

template<class T>
BSTNode<T>* BST<T>::search(BSTNode<T> *x,T key){
	if(x == NULL || x -> key = key){
		return x;
	}
	
	if(key < x -> key){
		return search(x -> left,key);
	}else{
		return search(x -> right,key);
	}
}

4.2迭代版本

template<class T>
BSTNode<T>* BST<T>::iterativeSearch(BSTNode<T> *x,T key){
	while(x != NULL && key -> key != key){
		if(key < x -> key){
			x = x -> left;
		}else{
			x = x -> right;
		}
	}
	return x;
}

5.最值

5.1最大值

最右便是最大

template<class T>
BSTNode<T>* BST<T>::maximum(BSTNode<T> *root){
	if(root == NULL){
		return NULL;
	}
	
	while(root -> right != NULL){
		root = root -> right;
	}
	return root;
}

5.2最小值

最左便是最小

template<class T>
BSTNode<T>* BST<T>::minimum(BSTNode<T> *root){
	if(root == NULL){
		return NULL;
	}
	
	while(root -> left != NULL){
		root = root -> left;
	}
	return root;
}

6.前驅和后繼

6.1前驅

是該結點左子樹的最大結點

template<class T>
BSTNode<T>* BST<T>::predecessor(BSTNode<T> *root){
	if(root -> left != NULL){//如果x有左孩子,則x的前驅為以左孩子為根的子樹的最大結點 
		return maximum(root -> left);
	}
	
	BSTNode<T> * y = root -> p;//如果x沒有左孩子,則x有兩種可能 
	while(y != NULL && root == y -> left){//(1)x是一個右孩子,則其前驅為它的父結點 
		root = y;//(2)x是一個左孩子,則查找x的最低父結點,並且該父結點得有右孩子 
		y = y -> p;
	}
	return y;
}

6.2後繼

是該結點右子樹的最小結點

template<class T>
BSTNode<T>* BST<T>::successor(BSTNode<T> *root){
	if(root -> right != NULL){//如果x有右孩子,則x的後繼為以右孩子為根的子樹的最小結點 
		return minimum(root -> right);
	}
	
	BSTNode<T> *y = root -> p;//如果x沒有右孩子,則x有兩種可能 
	while(y != NULL && root == y -> right){//(1)x是一個左孩子,則其後繼為它的父結點 
		root = y;//(2)x是一個右孩子,則查找x的最低父結點,並且該父結點得有左孩子 
		y = y -> p;
	}
	return y;
}

7.插入

template<class T>
void BST<T>::insert(BSTNode<T>* &root,BSTNode<T> *z){
	BSTNode<T> *y = NULL;
	BSTNode<T> *x = root;
	
	while(x != NULL){//查找z的插入位置 
		y = x;
		if(z -> key < x -> key){
			x = x -> left;
		}else{
			x = x -> right;
		}
	}
	
	z -> p = y;//調指針插入 
	if(y == NULL){
		root = z;
	}else if(z -> key < y -> key){
		y -> left = z;
	}else{
		y -> right = z;
	}
}

8.刪除

template<class T>
void BST<T>::remove(BSTNode<T>* &root,BSTNode<T> *z){
	BSTNode<T> *x = NULL;
	BSTNode<T> *y = NULL;
	
	if(z -> left == NULL || z -> right == NULL){
		y = z;
	}else{
		y = successor(z);
	}
	
	if(y -> left != NULL){
		x = y -> left;
	}else{
		x = y -> right;
	}
	
	if(x != NULL){
		x -> p = y -> p;
	}
	
	if(y -> p == NULL){
		root = x;
	}else if(y == y -> p -> left){
		y -> p -> left = x;
	}else{
		y -> p -> right = x;
	}
	
	if(y != z){
		z -> key = y -> key;
	}
	
	delete y;
}

9.銷毀

template<class T>
void BST<T>::destroy(BSTNode<T>* &root){
	if(root == NULL){
		return;
	}
	
	if(root -> left != NULL){
		return destroy(root -> left);
	}
	if(root -> right != NULL){
		return destroy(root -> right);
	}
	
	delete root;
	root = NULL;
}