什么是二分搜索樹

這篇文章主要介紹“什么是二分搜索樹”，在日常操作中，相信很多人在什么是二分搜索樹問題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”什么是二分搜索樹”的疑惑有所幫助！接下來，請(qǐng)跟著小編一起來學(xué)習(xí)吧！

一、樹結(jié)構(gòu)

樹是一種很特別的數(shù)據(jù)結(jié)構(gòu)，樹這種數(shù)據(jù)結(jié)構(gòu)叫做 “樹” 就是因?yàn)樗?長得像一棵樹  。但是這棵樹畫成的圖長得卻是一棵倒著的樹，根在上，葉在下。樹是圖的一種，樹和圖的區(qū)別就在于：樹是沒有環(huán)的，而圖是可以有環(huán)的。

樹狀圖是一種數(shù)據(jù)結(jié)構(gòu)，它是由n(n>=1)個(gè)有限節(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做“樹”是因?yàn)樗雌饋硐褚豢玫箳斓臉?，也就是說它是根朝上，而葉朝下的。

二、為什么要有樹結(jié)構(gòu)

2.1 樹結(jié)構(gòu)是一種天然的組織結(jié)構(gòu)

比如說電腦中的文件夾，我們需要找到一個(gè)特定的文件，需要到某個(gè)文件夾下去找這個(gè)文件，計(jì)算機(jī)的文件存儲(chǔ)的結(jié)構(gòu)來源于生活。再比如說圖書館，我們知道圖書館里面有  歷史類、數(shù)理類、計(jì)算機(jī)類，我們想要找到關(guān)于java的書籍，就需要到計(jì)算機(jī)類的Java中去找到我們需要的圖書

比如公司里面的層級(jí)結(jié)構(gòu)：CEO、HR CTO等等，還有我們比較常見的家譜等等，都是類似于樹結(jié)構(gòu)

將數(shù)據(jù)使用樹結(jié)構(gòu)后，會(huì)更加的高效

三、二分搜索樹

3.1 特點(diǎn)

• 二分搜索樹是一個(gè)動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)

• 二分搜索樹也是一顆二叉樹(也叫多叉樹)

• 二分搜索樹的每個(gè)節(jié)點(diǎn)的值都大于其左子樹的所有節(jié)點(diǎn)的值，同時(shí)每個(gè)節(jié)點(diǎn)的值都小于其右子樹的所有節(jié)點(diǎn)的值

• 存儲(chǔ)的元素必須有可比較性, Java中的話就要求二分搜索樹保存的數(shù)據(jù)類型要實(shí)現(xiàn)Comparable接口, 或者使用額外的比較器實(shí)現(xiàn)

• 每一顆子樹也是二分搜索樹

• 二分搜索樹具有唯一根節(jié)點(diǎn)，同時(shí)在二叉樹中最底下是它的葉子節(jié)點(diǎn)

• 二分搜索樹具有唯根節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)最多有兩個(gè)孩子(左邊的叫左孩子，右邊的叫右孩子)，同時(shí)每個(gè)節(jié)點(diǎn)最多有一個(gè)父親

二分搜索樹天然的具有遞歸特性

• 每個(gè)節(jié)點(diǎn)的左子樹也是二叉樹

• 每個(gè)節(jié)點(diǎn)的右子樹也是二叉樹

二叉樹不一定是滿的，一個(gè)接電腦也是二叉樹、空也是二叉樹

四、具體代碼實(shí)現(xiàn)

在進(jìn)行相關(guān)操作之前, 先定義一個(gè)支持泛型的節(jié)點(diǎn)類, 用于存儲(chǔ)二分搜索樹每個(gè)節(jié)點(diǎn)的信息, 這個(gè)類作為二分搜索樹的一個(gè)內(nèi)部類,  二分搜索樹的類聲明以及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;  // 樹容量  private int size;  public BST(){  root = null;  size = 0;  }  public int size(){  return size;  }  public boolean isEmpty(){  return size == 0;  }  }

4.1 添加元素

二分搜索樹添加元素的非遞歸寫法，和鏈表很像，由于二分搜索樹本身的遞歸特性, 所以可以很方便的使用遞歸實(shí)現(xiàn)向二分搜索樹中添加元素,

代碼實(shí)現(xiàn)：

//向二分搜索樹添加新的元素e  public void add(E e){  root = add(root,e);  }  //向以Node為根的二分搜索樹中插入元素 E，遞歸算法  //返回插入新節(jié)點(diǎn)后二分搜索樹的根  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 查找元素

由于二分搜索樹沒有下標(biāo), 所以針對(duì)二分搜索樹的查找操作, 我們需要定義一個(gè) contains() 方法, 查看二分搜索樹是否包含某個(gè)元素,  返回一個(gè)布爾型變量

代碼實(shí)現(xiàn)：

//看二分是搜索樹中是否包含元素e  public boolean contains(E e){  return contains(root,e);  }  //看以Node為根的二分搜索樹中是否包含元素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)都訪問一遍

• 訪問的原因和業(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)

二、 前序遍歷

//二分搜索樹前序遍歷  public void preOrder(){  preOrder(root);  }  //前序遍歷以Node為根的二分搜索樹，遞歸算法  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);  }  }

三、 中序遍歷

//二分搜索樹的中序遍歷  public void inOrder(){  inOrder(root);  }  //中序遍歷以Node為根的二分搜索樹，遞歸算法  private void inOrder(Node node){  if(node ==null)  return;  inOrder(node.left);  System.out.println(node.e);  inOrder(node.right);  }

四、 后序遍歷

//二分搜索樹的后序遍歷  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為根的二分搜索樹，遞歸算法  private void postOrder(Node node){  if(node ==null)  return;  inOrder(node.left);  inOrder(node.right);  System.out.println(node.e);  }

五、 理解前中后

二分搜索樹前序非遞歸寫法

到此，關(guān)于“什么是二分搜索樹”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！