Dvojiško drevo/Implementacija2 (Java)

Iz MaFiRaWiki

Algoritem za risanje:

Metoda dobi kot vhodni podatek dvojiško drevo. Najprej pogleda ali je drevo prazno, če je vrne rezultat 0. Če pa drevo ni prazno, najprej pogleda levo stran poddrevesa na kateremu se rekurzivno pokliče pregled leve strani poddrevesa. Poiščemo (x,y) pozicijo od vsakega vozlišča od levega poddrevesa, ter metoda na koncu vrne velikost škatlice vozlišča. Isto se naredi z desno stranjo poddrevesa. Ko metoda preračuna vse pozicije, se izriše celotno dvojiško drevo. Torej za vsako vozlišče nariše koren tega drevesa, ki jih na koncu vse skupaj poveže. Dobimo koren levega poddrevesa in koren desnega poddrevesa, katera dva poveže skupaj s korenom očeta. Preden se izriše celotno dvojiško drevo, se najprej izriše rob tega vozlišča, nato celotno vozlišče, v katerega se doda podatek(številka), ki se vstavi v to vozlišče. Naredi se novo vozlišče, ki je usmerjen k prejšnemu vozlišču. Ta dva vozlišča se med seboj povežeta. Postopek se ponavjla od lista vse do korena očeta. POZOR!!! OPIS ALGORITMA SE NE UJEMA POVSEM S PROGRAMOM !!! zadevo je potrebno urediti!!

Program za risanje dvojiškega drevesa:

  1. import java.util.*;
  2. import java.awt.*;
  3. import java.applet.*;
  4.  
  5. class node {
  6. int key; // podatek
  7. node left; // levi sin
  8. node right; // desni sin
  9. node parent; // oce
  10. float x, y; // (x,y) lokacija v oknu
  11. float incx, incy; // lokacija (x,y) v poddrevesu
  12. }
  13. public class dvojisko_drevo extends Applet {
  14. node root; // koren drevesa
  15.  
  16. int num_edges; // nariše robove
  17. float edges[][] = new float[100][4];
  18.  
  19. // Nastavitve, ki vplivajo na izgled:
  20.  
  21. Font f = new Font( "TimesRoman", Font.PLAIN, 14 );
  22. FontMetrics fm = getFontMetrics( f );
  23.  
  24. final Color LineColor = Color.black;
  25. final Color HighlightColor = Color.orange;
  26. final Color NodeColor = Color.orange;
  27. final int NODE_WIDTH = 40; // širina vozlišča
  28. final int NODE_HEIGHT = 40; // višina vozlišča
  29.  
  30. //konstruktor
  31. public void init() {
  32. // prebere parametre(podatke o devesu) in naredi drevo
  33. parse_parameters();
  34. // pogleda drevo in prepačuna pozicije vozlišč
  35. position_tree( root, 0, 0 );
  36. }
  37.  
  38. public void paint( Graphics g ) {
  39.  
  40. draw_tree( root, g );
  41. }
  42.  
  43. void parse_parameters() {
  44. String keys;
  45. // prebere podatek
  46. keys = getParameter( "keys" );
  47. if (keys != null) {
  48. while (t.hasMoreTokens())
  49. insert( Integer.parseInt(t.nextToken()) );
  50. }
  51. }
  52. //poišče (x,y) pozicijo od vsakega vozlišča od drevesa, ter vrne višino škatlice
  53. int position_tree( node root, int upper, int left ) {
  54. int l_width, r_width;
  55.  
  56. if (root == null)
  57. return 0;
  58. //rekurzivno pogledamo levo stran
  59. l_width = position_tree( root.left, upper + NODE_HEIGHT, left );
  60.  
  61. root.x = left + l_width + NODE_WIDTH/2;
  62. root.y = upper + NODE_HEIGHT/2;
  63. //rekurzivno pogledamo desno stran
  64. r_width = position_tree( root.right, upper + NODE_HEIGHT, left + l_width + NODE_WIDTH );
  65.  
  66. return l_width + NODE_WIDTH + r_width;
  67. }
  68. //narišemo drevo: za vsako vozlišče, narišemo koren tega drevesa, nakoncu koren levega
  69. // in desnega poddrevesa povežemo s korenom očeta
  70. void draw_tree( node root, Graphics g ) {
  71. if (root == null)
  72. return;
  73.  
  74. draw_tree( root.left, g );
  75. draw_tree( root.right, g );
  76.  
  77. if (root.parent != null)
  78. draw_parent_edge( root, g );
  79.  
  80. draw_node( root, g );
  81. }
  82. //narišemo rob tega vozlišča
  83. void draw_parent_edge( node n, Graphics g ) {
  84.  
  85. g.setColor( LineColor );
  86. g.drawLine( (int) n.x, (int) n.y, (int) n.parent.x, (int) n.parent.y );
  87.  
  88. }
  89. //narišemo vozlišče
  90. void draw_node( node n, Graphics g ) {
  91. String key = Integer.toString( n.key );
  92. int width = fm.stringWidth( key );
  93. int height = fm.getAscent(); // samo stevilke, so Descent = 0
  94.  
  95. // napolnimo vozlišče krogca
  96. g.setColor( NodeColor );
  97. g.fillOval( (int) n.x - NODE_WIDTH/2, (int) n.y - NODE_HEIGHT/2,
  98. NODE_WIDTH, NODE_HEIGHT );
  99. // skiciramo krog in narišemo/vpišemo podatek
  100. g.setColor( LineColor );
  101. g.drawOval( (int) n.x - NODE_WIDTH/2, (int) n.y - NODE_HEIGHT/2,
  102. NODE_WIDTH, NODE_HEIGHT );
  103. // in narišemo/vpišemo podatek
  104. g.drawString( key, (int) n.x - width/2, (int) n.y - height/2 + fm.getAscent() - 1 );
  105.  
  106. }
  107. //vozliše vstavimo v drevo
  108. void insert( int k ) {
  109. node x, y, new_node;
  110.  
  111. y = null;
  112. x = root;
  113. // y zasleduje x, potegnemo drevo do x, ki je ničelen
  114.  
  115. while (x != null) {
  116. y = x;
  117. if (k == x.key)
  118. return;
  119. else if (k < x.key)
  120. x = x.left;
  121. else
  122. x = x.right;
  123. }
  124. // naredimo novo vozlišče
  125. new_node = new node();
  126.  
  127. new_node.key = k;
  128. new_node.parent = y;
  129. new_node.left = null;
  130. new_node.right = null;
  131.  
  132. // usmerimo vozlišče drevesa k novemu vozlišču
  133. if (y == null)
  134. root = new_node;
  135. else
  136. if (k < y.key)
  137. y.left = new_node;
  138. else
  139. y.right = new_node;
  140. }
  141. }
  142. </java-simple>
  143.  
  144.  
  145. ===Program dvojisko_drevo pokličemo s html značko, ki pa je naslednja:===
  146.  
    <HTML>
    <HEAD>
    <TITLE>dvojisko_drevo</TITLE>
    </HEAD>
    <BODY>
    <APPLET width="350" height="350" CODE="dvojisko_drevo.class" CODEBASE=".">
        <PARAM NAME="keys"    VALUE="1">
    </APPLET>
    <APPLET width="350" height="350" CODE="dvojisko_drevo.class" CODEBASE=".">
        <PARAM NAME="keys"    VALUE="2 1 3">
    </APPLET>
    <APPLET width="350" height="350" CODE="dvojisko_drevo.class" CODEBASE=".">
        <PARAM NAME="keys"    VALUE="1 2">
    
    </APPLET>
    <APPLET width="350" height="350" CODE="dvojisko_drevo.class" CODEBASE=".">
        <PARAM NAME="keys"    VALUE="2 1 4 3">
    </APPLET>
    <APPLET width="350" height="350" CODE="dvojisko_drevo.class" CODEBASE=".">
        <PARAM NAME="keys"    VALUE="2 1 10 4 3 8 7 9">
    </APPLET
    </BODY>
    </HTML>
    
Osebna orodja