日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問(wèn)題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
【數(shù)據(jù)結(jié)構(gòu)】二分搜索樹詳解

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

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

凌海網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)公司！從網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、APP開發(fā)、響應(yīng)式網(wǎng)站設(shè)計(jì)等網(wǎng)站項(xiàng)目制作，到程序開發(fā)，運(yùn)營(yíng)維護(hù)。創(chuàng)新互聯(lián)公司從2013年成立到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來(lái)保證我們的工作的順利進(jìn)行。專注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)公司。

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

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

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

比如說(shuō)電腦中的文件夾，我們需要找到一個(gè)特定的文件，需要到某個(gè)文件夾下去找這個(gè)文件，計(jì)算機(jī)的文件存儲(chǔ)的結(jié)構(gòu)來(lái)源于生活。再比如說(shuō)圖書館，我們知道圖書館里面有 歷史類、數(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)類聲明如下:

 
 
 
 
    
  
  
  
  
  1. public class BST> { 
    2. 
  
  
  
  
  2.  
    3. 
  
  
  
  
  3. private class Node{ 
    4. 
  
  
  
  
  4.  
    5. 
  
  
  
  
  5. public E e; 
    6. 
  
  
  
  
  6.  
    7. 
  
  
  
  
  7. public Node left,right; 
    8. 
  
  
  
  
  8.  
    9. 
  
  
  
  
  9. public Node(E e){ 
    10. 
  
  
  
  
  10.  
    11. 
  
  
  
  
  11. this.e = e; 
    12. 
  
  
  
  
  12.  
    13. 
  
  
  
  
  13. left = null; 
    14. 
  
  
  
  
  14.  
    15. 
  
  
  
  
  15. right = null; 
    16. 
  
  
  
  
  16.  
    17. 
  
  
  
  
  17. } 
    18. 
  
  
  
  
  18.  
    19. 
  
  
  
  
  19. } 
    20. 
  
  
  
  
  20.  
    21. 
  
  
  
  
  21. //節(jié)點(diǎn) 
    22. 
  
  
  
  
  22.  
    23. 
  
  
  
  
  23. private Node root; 
    24. 
  
  
  
  
  24.  
    25. 
  
  
  
  
  25. // 樹容量 
    26. 
  
  
  
  
  26.  
    27. 
  
  
  
  
  27. private int size; 
    28. 
  
  
  
  
  28.  
    29. 
  
  
  
  
  29. public BST(){ 
    30. 
  
  
  
  
  30.  
    31. 
  
  
  
  
  31. root = null; 
    32. 
  
  
  
  
  32.  
    33. 
  
  
  
  
  33. size = 0; 
    34. 
  
  
  
  
  34.  
    35. 
  
  
  
  
  35. } 
    36. 
  
  
  
  
  36.  
    37. 
  
  
  
  
  37. public int size(){ 
    38. 
  
  
  
  
  38.  
    39. 
  
  
  
  
  39. return size; 
    40. 
  
  
  
  
  40.  
    41. 
  
  
  
  
  41. } 
    42. 
  
  
  
  
  42.  
    43. 
  
  
  
  
  43. public boolean isEmpty(){ 
    44. 
  
  
  
  
  44.  
    45. 
  
  
  
  
  45. return size == 0; 
    46. 
  
  
  
  
  46.  
    47. 
  
  
  
  
  47. } 
    48. 
  
  
  
  
  48.  
    49. 
  
  
  
  
  49. } 
    50.

4.1 添加元素

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

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

 
 
 
 
    
  
  
  
  
  1. //向二分搜索樹添加新的元素e 
    2. 
  
  
  
  
  2.  
    3. 
  
  
  
  
  3. public void add(E e){ 
    4. 
  
  
  
  
  4.  
    5. 
  
  
  
  
  5. root = add(root,e); 
    6. 
  
  
  
  
  6.  
    7. 
  
  
  
  
  7. } 
    8. 
  
  
  
  
  8.  
    9. 
  
  
  
  
  9. //向以Node為根的二分搜索樹中插入元素 E，遞歸算法 
    10. 
  
  
  
  
  10.  
    11. 
  
  
  
  
  11. //返回插入新節(jié)點(diǎn)后二分搜索樹的根 
    12. 
  
  
  
  
  12.  
    13. 
  
  
  
  
  13. private Node add(Node node,E e){ 
    14. 
  
  
  
  
  14.  
    15. 
  
  
  
  
  15. if(node == null){ 
    16. 
  
  
  
  
  16.  
    17. 
  
  
  
  
  17. size++; 
    18. 
  
  
  
  
  18.  
    19. 
  
  
  
  
  19. return new Node(e); 
    20. 
  
  
  
  
  20.  
    21. 
  
  
  
  
  21. } 
    22. 
  
  
  
  
  22.  
    23. 
  
  
  
  
  23. if(e.compareTo(node.e) < 0) 
    24. 
  
  
  
  
  24.  
    25. 
  
  
  
  
  25. node.left = add(node.left,e); 
    26. 
  
  
  
  
  26.  
    27. 
  
  
  
  
  27. else if(e.compareTo(node.e) > 0) 
    28. 
  
  
  
  
  28.  
    29. 
  
  
  
  
  29. node.right = add(node.right,e); 
    30. 
  
  
  
  
  30.  
    31. 
  
  
  
  
  31. return node; 
    32. 
  
  
  
  
  32.  
    33. 
  
  
  
  
  33. } 
    34.

4.2 查找元素

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

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

 
 
 
 
    
  
  
  
  
  1. //看二分是搜索樹中是否包含元素e 
    2. 
  
  
  
  
  2.  
    3. 
  
  
  
  
  3. public boolean contains(E e){ 
    4. 
  
  
  
  
  4.  
    5. 
  
  
  
  
  5. return contains(root,e); 
    6. 
  
  
  
  
  6.  
    7. 
  
  
  
  
  7. } 
    8. 
  
  
  
  
  8.  
    9. 
  
  
  
  
  9. //看以Node為根的二分搜索樹中是否包含元素e，遞歸算法 
    10. 
  
  
  
  
  10.  
    11. 
  
  
  
  
  11. private boolean contains(Node node,E e){ 
    12. 
  
  
  
  
  12.  
    13. 
  
  
  
  
  13. if(node == null) 
    14. 
  
  
  
  
  14.  
    15. 
  
  
  
  
  15. return false; 
    16. 
  
  
  
  
  16.  
    17. 
  
  
  
  
  17. if(e.compareTo(node.e) == 0) 
    18. 
  
  
  
  
  18.  
    19. 
  
  
  
  
  19. return true; 
    20. 
  
  
  
  
  20.  
    21. 
  
  
  
  
  21. else if(e.compareTo(node.e) < 0) 
    22. 
  
  
  
  
  22.  
    23. 
  
  
  
  
  23. return contains(node.left,e); 
    24. 
  
  
  
  
  24.  
    25. 
  
  
  
  
  25. else //e.compareTo(node.e) > 0 
    26. 
  
  
  
  
  26.  
    27. 
  
  
  
  
  27. return contains(node.right,e); 
    28. 
  
  
  
  
  28.  
    29. 
  
  
  
  
  29. } 
    30.

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)

二、 前序遍歷

 
 
 
 
    
  
  
  
  
  1. //二分搜索樹前序遍歷 
    2. 
  
  
  
  
  2.  
    3. 
  
  
  
  
  3. public void preOrder(){ 
    4. 
  
  
  
  
  4.  
    5. 
  
  
  
  
  5. preOrder(root); 
    6. 
  
  
  
  
  6.  
    7. 
  
  
  
  
  7. } 
    8. 
  
  
  
  
  8.  
    9. 
  
  
  
  
  9. //前序遍歷以Node為根的二分搜索樹，遞歸算法 
    10. 
  
  
  
  
  10.  
    11. 
  
  
  
  
  11. private void preOrder(Node node){ 
    12. 
  
  
  
  
  12.  
    13. 
  
  
  
  
  13. if(node == null) 
    14. 
  
  
  
  
  14.  
    15. 
  
  
  
  
  15. return; 
    16. 
  
  
  
  
  16.  
    17. 
  
  
  
  
  17. System.out.println(node.e); 
    18. 
  
  
  
  
  18.  
    19. 
  
  
  
  
  19. preOrder(node.left); 
    20. 
  
  
  
  
  20.  
    21. 
  
  
  
  
  21. preOrder(node.right); 
    22. 
  
  
  
  
  22.  
    23. 
  
  
  
  
  23. } 
    24. 
  
  
  
  
  24.  
    25. 
  
  
  
  
  25. public void preOrderNR(){ 
    26. 
  
  
  
  
  26.  
    27. 
  
  
  
  
  27. Stack stack = new Stack<>(); 
    28. 
  
  
  
  
  28.  
    29. 
  
  
  
  
  29. stack.push(root); 
    30. 
  
  
  
  
  30.  
    31. 
  
  
  
  
  31. while(!stack.isEmpty()){ 
    32. 
  
  
  
  
  32.  
    33. 
  
  
  
  
  33. Node cur = stack.pop(); 
    34. 
  
  
  
  
  34.  
    35. 
  
  
  
  
  35. System.out.println(cur.e); 
    36. 
  
  
  
  
  36.  
    37. 
  
  
  
  
  37. if(cur.right != null) 
    38. 
  
  
  
  
  38.  
    39. 
  
  
  
  
  39. stack.push(cur.right); 
    40. 
  
  
  
  
  40.  
    41. 
  
  
  
  
  41. if(cur.left != null) 
    42. 
  
  
  
  
  42.  
    43. 
  
  
  
  
  43. stack.push(cur.left); 
    44. 
  
  
  
  
  44.  
    45. 
  
  
  
  
  45. } 
    46. 
  
  
  
  
  46.  
    47. 
  
  
  
  
  47. } 
    48.

三、 中序遍歷

 
 
 
 
    
  
  
  
  
  1. //二分搜索樹的中序遍歷 
    2. 
  
  
  
  
  2.  
    3. 
  
  
  
  
  3. public void inOrder(){ 
    4. 
  
  
  
  
  4.  
    5. 
  
  
  
  
  5. inOrder(root); 
    6. 
  
  
  
  
  6.  
    7. 
  
  
  
  
  7. } 
    8. 
  
  
  
  
  8.  
    9. 
  
  
  
  
  9. //中序遍歷以Node為根的二分搜索樹，遞歸算法 
    10. 
  
  
  
  
  10.  
    11. 
  
  
  
  
  11. private void inOrder(Node node){ 
    12. 
  
  
  
  
  12.  
    13. 
  
  
  
  
  13. if(node ==null) 
    14. 
  
  
  
  
  14.  
    15. 
  
  
  
  
  15. return; 
    16. 
  
  
  
  
  16.  
    17. 
  
  
  
  
  17. inOrder(node.left); 
    18. 
  
  
  
  
  18.  
    19. 
  
  
  
  
  19. System.out.println(node.e); 
    20. 
  
  
  
  
  20.  
    21. 
  
  
  
  
  21. inOrder(node.right); 
    22. 
  
  
  
  
  22.  
    23. 
  
  
  
  
  23. } 
    24.

四、 后序遍歷

 
 
 
 
    
  
  
  
  
  1. //二分搜索樹的后序遍歷 
    2. 
  
  
  
  
  2.  
    3. 
  
  
  
  
  3. public void postOrder(){ 
    4. 
  
  
  
  
  4.  
    5. 
  
  
  
  
  5. inOrder(root); 
    6. 
  
  
  
  
  6.  
    7. 
  
  
  
  
  7. } 
    8. 
  
  
  
  
  8.  
    9. 
  
  
  
  
  9. public void levelOrder(){ 
    10. 
  
  
  
  
  10.  
    11. 
  
  
  
  
  11. Queue q = new LinkedList(); 
    12. 
  
  
  
  
  12.  
    13. 
  
  
  
  
  13. q.add(root); 
    14. 
  
  
  
  
  14.  
    15. 
  
  
  
  
  15. while (!q.isEmpty()){ 
    16. 
  
  
  
  
  16.  
    17. 
  
  
  
  
  17. Node cur = q.remove(); 
    18. 
  
  
  
  
  18.  
    19. 
  
  
  
  
  19. System.out.println(cur.e); 
    20. 
  
  
  
  
  20.  
    21. 
  
  
  
  
  21. if(cur.left != null) 
    22. 
  
  
  
  
  22.  
    23. 
  
  
  
  
  23. q.add(cur.left); 
    24. 
  
  
  
  
  24.  
    25. 
  
  
  
  
  25. if(cur.right != null) 
    26. 
  
  
  
  
  26.  
    27. 
  
  
  
  
  27. q.add(cur.right); 
    28. 
  
  
  
  
  28.  
    29. 
  
  
  
  
  29. } 
    30. 
  
  
  
  
  30.  
    31. 
  
  
  
  
  31. } 
    32. 
  
  
  
  
  32.  
    33. 
  
  
  
  
  33. //后序遍歷以Node為根的二分搜索樹，遞歸算法 
    34. 
  
  
  
  
  34.  
    35. 
  
  
  
  
  35. private void postOrder(Node node){ 
    36. 
  
  
  
  
  36.  
    37. 
  
  
  
  
  37. if(node ==null) 
    38. 
  
  
  
  
  38.  
    39. 
  
  
  
  
  39. return; 
    40. 
  
  
  
  
  40.  
    41. 
  
  
  
  
  41. inOrder(node.left); 
    42. 
  
  
  
  
  42.  
    43. 
  
  
  
  
  43. inOrder(node.right); 
    44. 
  
  
  
  
  44.  
    45. 
  
  
  
  
  45. System.out.println(node.e); 
    46. 
  
  
  
  
  46.  
    47. 
  
  
  
  
  47. } 
    48.

五、 理解前中后

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


分享題目：【數(shù)據(jù)結(jié)構(gòu)】二分搜索樹詳解
分享網(wǎng)址：http://m.5511xx.com/article/dpedgdi.html