介绍
二进制 搜索树（BST）是基于节点的二进制树数据结构，具有以下属性：
使用代码
< pre style="margin: 0px; padding: 8px 0px 6px; max-width: 100%; box-sizing: border-box; word-wrap: break-word !important; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: 0.544px; orphans: 2; text-indent: 0px; text-transform: none ; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background : rgb(27, 25, 24); border-radius: 0px; overflow-y: auto; color: rgb(80, 97, 109); text-align: start; font-size: 10px; line-height : 12px; font-family: consolas, menlo, courier, monospace, "Microsoft Yahei" !important; border-width: 1px !important; border-style: solid !important; border-color: rgb(226, 226, 226) !important;">
1. `public class BNode {`
3. `public BNode leftBNode, rightBNode; // the nodes`
4. `public AnyClass anyClass; //the AnyClass objext`
6. `public BNode(AnyClass anyClass ) {// constructor `
7. `this.anyClass= anyClass;`
8. `this.leftBNode = null;`
9. `this.rightBNode = null;`
10. `}`
12. `public void show() {`
13. `//calls the show method of the AnyClass`
14. `System.out.print(anyClass.show());`
15. `}`
16. `}`
</pre>
<pre style="margin: 0px; padding: 8px 0px 6px; max-width: 100%; box-sizing: border-box; word-wrap: break-word !important; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: 0.544px; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background: rgb(27, 25, 24); border-radius: 0px; overflow-y: auto; color: rgb(80, 97, 109); text-align: start; font-size: 10px; line-height: 12px; font-family: consolas, menlo, courier, monospace, "Microsoft Yahei" !important; border-width: 1px !important; border-style: solid !important; border-color: rgb(226, 226, 226) !important;">
1. `public class BinTree {`
2. `BNode theBTRootNode;`
4. `public BinTree() // constructor`
5. `{`
6. `theBTRootNode = null;`
7. `}`
9. `// ------------------ Addition of the node to the BST-------------------`
10. `protected BNode insertAB(BNode theRootNode, BNode myNewNode) {`
11. `if (theRootNode == null) {`
12. `theRootNode = myNewNode;`
13. `//checks if the username is smaller than`
14. `//the root object, if smaller appends to the left`
15. `} else if (myNewNode.anyClass.surname.compareTo(`
16. `theRootNode.anyClass.surname) < 0) {`
17. `theRootNode.leftBNode = insertAB(theRootNode.leftBNode, myNewNode);`
18. `} else {`
19. `// else if bigger appends to the right`
20. `theRootNode.rightBNode =`
21. `insertAB(theRootNode.rightBNode, myNewNode);`
22. `}`
23. `return theRootNode;`
24. `}`
26. `public void insertBST(AnyClass anyClass) {`
27. `BNode anyClassBTNode = new BNode(anyClass);`
28. `//calls insert above`
29. `theBTRootNode = insertAB(theBTRootNode, anyClassBTNode);`
30. `}`
32. `// ------------------ InOrder traversal-------------------`
33. `protected void inorder(BNode theRootNode) {`
34. `if (theRootNode != null) {`
35. `inorder(theRootNode.leftBNode);`
36. `theRootNode.show();`
37. `inorder(theRootNode.rightBNode);`
38. `}`
39. `}`
41. `//calls the method to do in order`
42. `public void inorderBST() {`
43. `inorder(theBTRootNode);`
44. `}`
46. `// ----- Search for key name and returns ref.`
47. `// to BNode or null if not found--------`
48. `protected BNode search(BNode theRootNode, String keyName) {`
49. `//if the root is null returns null`
50. `if (theRootNode == null) {`
51. `return null;`
52. `} else {`
53. `//checks if they are equal`
54. `if (keyName.compareTo(theRootNode.anyClass.surname) == 0) {`
55. `return theRootNode;`
56. `//checks id the key is smaller than the current`
57. `//record if smaller traverses to the left`
58. `} else if (keyName.compareTo(theRootNode.anyClass.surname) < 0) {`
59. `return search(theRootNode.leftBNode, keyName);`
60. `} else {`
61. `// if bigger traverses to the left`
62. `return search(theRootNode.rightBNode, keyName);`
63. `}`
64. `}`
65. `}`
67. `//returns null if no result else returns`
68. `//the AnyClass object matched with the keyName`
69. `public AnyClass searchBST(String keyName) {`
70. `BNode temp = search(theBTRootNode, keyName);`
71. `if (temp == null) {`
72. `//noresults found`
73. `return null;`
74. `} else {`
75. `//result found`
76. `return temp.anyClass;`
77. `}`
78. `}`
79. `}`
</pre>
兴趣点
<pre style="margin: 0px; padding: 8px 0px 6px; max-width: 100%; box-sizing: border-box; word-wrap: break-word !important; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: 0.544px; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; background: rgb(27, 25, 24); border-radius: 0px; overflow-y: auto; color: rgb(80, 97, 109); text-align: start; font-size: 10px; line-height: 12px; font-family: consolas, menlo, courier, monospace, "Microsoft Yahei" !important; border-width: 1px !important; border-style: solid !important; border-color: rgb(226, 226, 226) !important;">
1. `public void populateBinTree(List theList) {`
2. `//clearing the root as not to append,`
3. `//if you want to append just remove the below line`
4. `theBTRootNode = null;`
5. `//keeps looping untill reaches the end of the list`
6. `for(int i = 0;i < theList.size();i++)`
7. `Node temporaryNode = null;`
8. `//inserts in the BST`
9. `insertBST((AnyClass)theList.get(i));`
10. `//goes to the next element`
11. `}`
12. `}`
</pre>
