`
yanlijun250
  • 浏览: 745543 次
文章分类
社区版块
存档分类
最新评论

算法之二叉查找树

 
阅读更多
  1. packagecom.eshore.sweetop.dataframe;
  2. importjava.util.Random;
  3. importcom.eshore.sweetop.data.KeyData;
  4. importcom.eshore.sweetop.data.Node;
  5. /*
  6. *bintree
  7. */
  8. publicclassBintree{
  9. privateNoderoot;
  10. publicvoidinsert(Nodenode){
  11. Nodey=null;
  12. Nodex=root;
  13. while(x!=null){
  14. y=x;
  15. if(node.getData().getKey()<x.getData().getKey()){
  16. x=x.getLeft();
  17. }else{
  18. x=x.getRight();
  19. }
  20. }
  21. node.setParent(y);
  22. if(y==null){
  23. root=node;
  24. }elseif(node.getData().getKey()<y.getData().getKey()){
  25. y.setLeft(node);
  26. }else{
  27. y.setRight(node);
  28. }
  29. }
  30. publicNodegetRoot(){
  31. returnroot;
  32. }
  33. publicvoidwalk(){
  34. walk(root);
  35. }
  36. privatevoidwalk(Nodenode){
  37. if(node!=null){
  38. walk(node.getLeft());
  39. System.out.println(node.getData());
  40. walk(node.getRight());
  41. }
  42. }
  43. publicNodesearch(intk){
  44. Nodenode=root;
  45. while(node!=null&&k!=node.getData().getKey()){
  46. if(k<node.getData().getKey()){
  47. node=node.getLeft();
  48. }else{
  49. node=node.getRight();
  50. }
  51. }
  52. returnnode;
  53. }
  54. publicNodemin(Nodenode){
  55. while(node.getLeft()!=null){
  56. node=node.getLeft();
  57. }
  58. returnnode;
  59. }
  60. publicNodemin(){
  61. returnmin(root);
  62. }
  63. publicNodemax(Nodenode){
  64. while(node.getRight()!=null){
  65. node=node.getRight();
  66. }
  67. returnnode;
  68. }
  69. publicNodemax(){
  70. returnmax(root);
  71. }
  72. publicNodesuccessor(Nodenode){
  73. if(node.getRight()!=null){
  74. returnmin(node.getRight());
  75. }
  76. Nodey=node.getParent();
  77. while(y!=null&&node==y.getRight()){
  78. y=y.getParent();
  79. }
  80. returny;
  81. }
  82. publicvoiddelete(Nodenode){
  83. Nodetempy,tempx;
  84. if(node.getLeft()==null||node.getRight()==null){
  85. tempy=node;
  86. }else{
  87. tempy=successor(node);
  88. }
  89. if(tempy.getLeft()!=null){
  90. tempx=tempy.getLeft();
  91. }else{
  92. tempx=tempy.getRight();
  93. }
  94. if(tempx!=null){
  95. tempx.setParent(tempy.getParent());
  96. }
  97. if(tempy.getParent()==null){
  98. root=tempx;
  99. }elseif(tempy==tempy.getParent().getLeft()){
  100. tempy.getParent().setLeft(tempx);
  101. }else{
  102. tempy.getParent().setRight(tempx);
  103. }
  104. if(tempy!=node){
  105. node.setData(tempy.getData());
  106. }
  107. }
  108. publicstaticvoidmain(String[]args){
  109. Bintreebt=newBintree();
  110. Randomrd=newRandom(47);
  111. Nodenode=null;
  112. for(inti=0;i<5;i++){
  113. node=newNode();
  114. node.setData(newKeyData(rd.nextInt(22)+1));
  115. bt.insert(node);
  116. }
  117. bt.walk();
  118. System.out.println(bt.search(9).getData());
  119. System.out.println("Min:"+bt.min().getData());
  120. System.out.println("Max:"+bt.max().getData());
  121. bt.delete(bt.search(22));
  122. bt.walk();
  123. }
  124. }
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics