【數(shù)據(jù)結(jié)構(gòu)】二分搜索樹(shù)詳解
一、樹(shù)結(jié)構(gòu)
樹(shù)是一種很特別的數(shù)據(jù)結(jié)構(gòu)，樹(shù)這種數(shù)據(jù)結(jié)構(gòu)叫做 “樹(shù)” 就是因?yàn)樗?長(zhǎng)得像一棵樹(shù) 。但是這棵樹(shù)畫(huà)成的圖長(zhǎng)得卻是一棵倒著的樹(shù)，根在上，葉在下。樹(shù)是圖的一種，樹(shù)和圖的區(qū)別就在于：樹(shù)是沒(méi)有環(huán)的，而圖是可以有環(huán)的。
樹(shù)狀圖是一種數(shù)據(jù)結(jié)構(gòu)，它是由n(n>=1)個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做“樹(shù)”是因?yàn)樗雌饋?lái)像一棵倒掛的樹(shù)，也就是說(shuō)它是根朝上，而葉朝下的。
二、為什么要有樹(shù)結(jié)構(gòu)
2.1 樹(shù)結(jié)構(gòu)是一種天然的組織結(jié)構(gòu)
比如說(shuō)電腦中的文件夾，我們需要找到一個(gè)特定的文件，需要到某個(gè)文件夾下去找這個(gè)文件，計(jì)算機(jī)的文件存儲(chǔ)的結(jié)構(gòu)來(lái)源于生活。再比如說(shuō)圖書(shū)館，我們知道圖書(shū)館里面有 歷史類、數(shù)理類、計(jì)算機(jī)類，我們想要找到關(guān)于java的書(shū)籍，就需要到計(jì)算機(jī)類的Java中去找到我們需要的圖書(shū)
比如公司里面的層級(jí)結(jié)構(gòu)：CEO、HR CTO等等，還有我們比較常見(jiàn)的家譜等等，都是類似于樹(shù)結(jié)構(gòu)
將數(shù)據(jù)使用樹(shù)結(jié)構(gòu)后，會(huì)更加的高效
三、二分搜索樹(shù)
3.1 特點(diǎn)
- 二分搜索樹(shù)是一個(gè)動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)
- 二分搜索樹(shù)也是一顆二叉樹(shù)(也叫多叉樹(shù))
- 二分搜索樹(shù)的每個(gè)節(jié)點(diǎn)的值都大于其左子樹(shù)的所有節(jié)點(diǎn)的值，同時(shí)每個(gè)節(jié)點(diǎn)的值都小于其右子樹(shù)的所有節(jié)點(diǎn)的值
- 存儲(chǔ)的元素必須有可比較性, Java中的話就要求二分搜索樹(shù)保存的數(shù)據(jù)類型要實(shí)現(xiàn)Comparable接口, 或者使用額外的比較器實(shí)現(xiàn)
- 每一顆子樹(shù)也是二分搜索樹(shù)
- 二分搜索樹(shù)具有唯一根節(jié)點(diǎn)，同時(shí)在二叉樹(shù)中最底下是它的葉子節(jié)點(diǎn)
- 二分搜索樹(shù)具有唯根節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)最多有兩個(gè)孩子(左邊的叫左孩子，右邊的叫右孩子)，同時(shí)每個(gè)節(jié)點(diǎn)最多有一個(gè)父親
二分搜索樹(shù)天然的具有遞歸特性
- 每個(gè)節(jié)點(diǎn)的左子樹(shù)也是二叉樹(shù)
- 每個(gè)節(jié)點(diǎn)的右子樹(shù)也是二叉樹(shù)
二叉樹(shù)不一定是滿的，一個(gè)接電腦也是二叉樹(shù)、空也是二叉樹(shù)
四、具體代碼實(shí)現(xiàn)
在進(jìn)行相關(guān)操作之前, 先定義一個(gè)支持泛型的節(jié)點(diǎn)類, 用于存儲(chǔ)二分搜索樹(shù)每個(gè)節(jié)點(diǎn)的信息, 這個(gè)類作為二分搜索樹(shù)的一個(gè)內(nèi)部類, 二分搜索樹(shù)的類聲明以及Node節(jié)點(diǎn)類聲明如下:
- public class BST> {
- private class Node{
- public E e;
- public Node left,right;
- public Node(E e){
- this.e = e;
- left = null;
- right = null;
- }
- }
- //節(jié)點(diǎn)
- private Node root;
- // 樹(shù)容量
- private int size;
- public BST(){
- root = null;
- size = 0;
- }
- public int size(){
- return size;
- }
- public boolean isEmpty(){
- return size == 0;
- }
- }
4.1 添加元素
二分搜索樹(shù)添加元素的非遞歸寫(xiě)法，和鏈表很像，由于二分搜索樹(shù)本身的遞歸特性, 所以可以很方便的使用遞歸實(shí)現(xiàn)向二分搜索樹(shù)中添加元素,
代碼實(shí)現(xiàn)：
- //向二分搜索樹(shù)添加新的元素e
- public void add(E e){
- root = add(root,e);
- }
- //向以Node為根的二分搜索樹(shù)中插入元素 E，遞歸算法
- //返回插入新節(jié)點(diǎn)后二分搜索樹(shù)的根
- private Node add(Node node,E e){
- if(node == null){
- size++;
- return new Node(e);
- }
- if(e.compareTo(node.e) < 0)
- node.left = add(node.left,e);
- else if(e.compareTo(node.e) > 0)
- node.right = add(node.right,e);
- return node;
- }
4.2 查找元素
由于二分搜索樹(shù)沒(méi)有下標(biāo), 所以針對(duì)二分搜索樹(shù)的查找操作, 我們需要定義一個(gè) contains() 方法, 查看二分搜索樹(shù)是否包含某個(gè)元素, 返回一個(gè)布爾型變量
代碼實(shí)現(xiàn)：
- //看二分是搜索樹(shù)中是否包含元素e
- public boolean contains(E e){
- return contains(root,e);
- }
- //看以Node為根的二分搜索樹(shù)中是否包含元素e，遞歸算法
- private boolean contains(Node node,E e){
- if(node == null)
- return false;
- if(e.compareTo(node.e) == 0)
- return true;
- else if(e.compareTo(node.e) < 0)
- return contains(node.left,e);
- else //e.compareTo(node.e) > 0
- return contains(node.right,e);
- }
4.3 遍歷操作
一、 什么是遍歷操作
- 遍歷操作就是把所有的節(jié)點(diǎn)都訪問(wèn)一遍
- 訪問(wèn)的原因和業(yè)務(wù)相關(guān)
- 遍歷分類
前序遍歷 : 對(duì)當(dāng)前節(jié)點(diǎn)的遍歷在對(duì)左右孩子節(jié)點(diǎn)的遍歷之前, 遍歷順序 : 當(dāng)前節(jié)點(diǎn)->左孩子->右孩子中序遍歷 : 對(duì)當(dāng)前節(jié)點(diǎn)的遍歷在對(duì)左右孩子節(jié)點(diǎn)的遍歷中間, 遍歷順序 : 左孩子->當(dāng)前節(jié)點(diǎn)->右孩子后序遍歷 : 對(duì)當(dāng)前節(jié)點(diǎn)的遍歷在對(duì)左右孩子節(jié)點(diǎn)的遍歷之后, 遍歷順序 : 左孩子->右孩子->當(dāng)前節(jié)點(diǎn)
二、 前序遍歷
- //二分搜索樹(shù)前序遍歷
- public void preOrder(){
- preOrder(root);
- }
- //前序遍歷以Node為根的二分搜索樹(shù)，遞歸算法
- private void preOrder(Node node){
- if(node == null)
- return;
- System.out.println(node.e);
- preOrder(node.left);
- preOrder(node.right);
- }
- public void preOrderNR(){
- Stack stack = new Stack<>();
- stack.push(root);
- while(!stack.isEmpty()){
- Node cur = stack.pop();
- System.out.println(cur.e);
- if(cur.right != null)
- stack.push(cur.right);
- if(cur.left != null)
- stack.push(cur.left);
- }
- }
三、 中序遍歷
- //二分搜索樹(shù)的中序遍歷
- public void inOrder(){
- inOrder(root);
- }
- //中序遍歷以Node為根的二分搜索樹(shù)，遞歸算法
- private void inOrder(Node node){
- if(node ==null)
- return;
- inOrder(node.left);
- System.out.println(node.e);
- inOrder(node.right);
- }
四、 后序遍歷
- //二分搜索樹(shù)的后序遍歷
- public void postOrder(){
- inOrder(root);
- }
- public void levelOrder(){
- Queue q = new LinkedList();
- q.add(root);
- while (!q.isEmpty()){
- Node cur = q.remove();
- System.out.println(cur.e);
- if(cur.left != null)
- q.add(cur.left);
- if(cur.right != null)
- q.add(cur.right);
- }
- }
- //后序遍歷以Node為根的二分搜索樹(shù)，遞歸算法
- private void postOrder(Node node){
- if(node ==null)
- return;
- inOrder(node.left);
- inOrder(node.right);
- System.out.println(node.e);
- }
五、 理解前中后
二分搜索樹(shù)前序非遞歸寫(xiě)法
