Go语言视频零基础入门到精通

javalearner

1. 一、节点类
2. import java.io.*;
   
3. import java.util.*;            // for Stack class
   
4. class Node
   
5.    {
   
6.    public int iData;           // data item (key)
   
7.    public double dData;       // data item
   
8.    public Node leftChild;    // this node"s left child
9.    public Node rightChild;   // this node"s right child
   
10.    public void displayNode()  // display ourself
    
11.       {
    
12.       System.out.print("{");
    
13.       System.out.print(iData);
    
14.       System.out.print(", ");
    
15.       System.out.print(dData);
    
16.       System.out.print("} ");
    
17.       }
    
18.    }  // end class Node
    

复制代码

   
  
  二、二叉搜索树

1. 
   
2. class Tree
   
3.    {
   
4.    private Node root;             // first node of tree
   
5. // -------------------------------------------------------------
   
6.    public Tree()                  // constructor
   
7.       { root = null; }            // no nodes in tree yet
   
8. // -------------------------------------------------------------
   
9.    public Node find(int key)      // find node with given key
   
10.       {                           // (assumes non-empty tree)
    
11.       Node current = root;               // start at root
    
12.       while(current.iData != key)        // while no match,
    
13.          {
    
14.          if(key < current.iData)         // go left?
    
15.             current = current.leftChild;
    
16.          else                            // or go right?
    
17.             current = current.rightChild;
    
18.          if(current == null)             // if no child,
    
19.             return null;                 // didn"t find it
    
20.          }
    
21.       return current;                    // found it
    
22.       }  // end find()
    
23. // -------------------------------------------------------------
    
24.    public void insert(int id, double dd)
    
25.       {
    
26.       Node newNode = new Node();    // make new node
    
27.       newNode.iData = id;           // insert data
    
28.       newNode.dData = dd;
    
29.       if(root==null)                // no node in root
    
30.          root = newNode;
    
31.       else                          // root occupied
    
32.          {
    
33.          Node current = root;       // start at root
    
34.          Node parent;
    
35.          while(true)                // (exits internally)
    
36.             {
    
37.             parent = current;
    
38.             if(id < current.iData)  // go left?
    
39.                {
    
40.                current = current.leftChild;
    
41.                if(current == null)  // if end of the line,
    
42.                   {                 // insert on left
    
43.                   parent.leftChild = newNode;
    
44.                   return;
    
45.                   }
    
46.                }  // end if go left
    
47.             else                    // or go right?
    
48.                {
    
49.                current = current.rightChild;
    
50.                if(current == null)  // if end of the line
    
51.                   {                 // insert on right
    
52.                   parent.rightChild = newNode;
    
53.                   return;
    
54.                   }
    
55.                }  // end else go right
    
56.             }  // end while
    
57.          }  // end else not root
    
58.       }  // end insert()
    
59. // -------------------------------------------------------------
    
60.    public boolean delete(int key) // delete node with given key
    
61.       {                           // (assumes non-empty list)
    
62.       Node current = root;
    
63.       Node parent = root;
    
64.       boolean isLeftChild = true;
    
65.       while(current.iData != key)        // search for node
    
66.          {
    
67.          parent = current;
    
68.          if(key < current.iData)         // go left?
    
69.             {
    
70.             isLeftChild = true;
    
71.             current = current.leftChild;
    
72.             }
    
73.          else                            // or go right?
    
74.             {
    
75.             isLeftChild = false;
    
76.             current = current.rightChild;
    
77.             }
    
78.          if(current == null)             // end of the line,
    
79.             return false;                // didn"t find it
    
80.          }  // end while
    
81.       // found node to delete
    
82.       // if no children, simply delete it
    
83.       if(current.leftChild==null &&
    
84.                                    current.rightChild==null)
    
85.          {
    
86.          if(current == root)             // if root,
    
87.             root = null;                 // tree is empty
    
88.          else if(isLeftChild)
    
89.             parent.leftChild = null;     // disconnect
    
90.          else                            // from parent
    
91.             parent.rightChild = null;
    
92.          }
    
93.       // if no right child, replace with left subtree
    
94.       else if(current.rightChild==null)
    
95.          if(current == root)
    
96.             root = current.leftChild;
    
97.          else if(isLeftChild)
    
98.             parent.leftChild = current.leftChild;
    
99.          else
    
100.             parent.rightChild = current.leftChild;
     
101.       // if no left child, replace with right subtree
     
102.       else if(current.leftChild==null)
     
103.          if(current == root)
     
104.             root = current.rightChild;
     
105.          else if(isLeftChild)
     
106.             parent.leftChild = current.rightChild;
     
107.          else
     
108.             parent.rightChild = current.rightChild;
     
109.       else  // two children, so replace with inorder successor
     
110.          {
     
111.          // get successor of node to delete (current)
     
112.          Node successor = getSuccessor(current);
     
113.          // connect parent of current to successor instead
     
114.          if(current == root)
     
115.             root = successor;
     
116.          else if(isLeftChild)
     
117.             parent.leftChild = successor;
     
118.          else
     
119.             parent.rightChild = successor;
     
120.          // connect successor to current"s left child
     
121.          successor.leftChild = current.leftChild;
     
122.          }  // end else two children
     
123.       // (successor cannot have a left child)
     
124.       return true;                                // success
     
125.       }  // end delete()
     
126. // -------------------------------------------------------------
     
127.    // returns node with next-highest value after delNode
     
128.    // goes to right child, then right child"s left descendents
     
129.    private Node getSuccessor(Node delNode)
     
130.       {
     
131.       Node successorParent = delNode;
     
132.       Node successor = delNode;
     
133.       Node current = delNode.rightChild;   // go to right child
     
134.       while(current != null)               // until no more
     
135.          {                                 // left children,
     
136.          successorParent = successor;
     
137.          successor = current;
     
138.          current = current.leftChild;      // go to left child
     
139.          }
     
140.                                            // if successor not
     
141.       if(successor != delNode.rightChild)  // right child,
     
142.          {                                 // make connections
     
143.          successorParent.leftChild = successor.rightChild;
     
144.          successor.rightChild = delNode.rightChild;
     
145.          }
     
146.       return successor;
     
147.       }
     
148. // -------------------------------------------------------------
     
149.    public void traverse(int traverseType)
     
150.       {
     
151.       switch(traverseType)
     
152.          {
     
153.          case 1: System.out.print("
154. Preorder traversal: ");
     
155.                  preOrder(root);
     
156.                  break;
     
157.          case 2: System.out.print("
158. Inorder traversal:  ");
     
159.                  inOrder(root);
     
160.                  break;
     
161.          case 3: System.out.print("
162. Postorder traversal: ");
     
163.                  postOrder(root);
     
164.                  break;
     
165.          }
     
166.       System.out.println();
     
167.       }
     
168. // -------------------------------------------------------------
     
169.    private void preOrder(Node localRoot)
     
170.       {
     
171.       if(localRoot != null)
     
172.          {
     
173.          System.out.print(localRoot.iData + " ");
     
174.          preOrder(localRoot.leftChild);
     
175.          preOrder(localRoot.rightChild);
     
176.          }
     
177.       }
     
178. // -------------------------------------------------------------
     
179.    private void inOrder(Node localRoot)
     
180.       {
     
181.       if(localRoot != null)
     
182.          {
     
183.          inOrder(localRoot.leftChild);
     
184.          System.out.print(localRoot.iData + " ");
     
185.          inOrder(localRoot.rightChild);
     
186.          }
     
187.       }
     
188. // -------------------------------------------------------------
     
189.    private void postOrder(Node localRoot)
     
190.       {
     
191.       if(localRoot != null)
     
192.          {
     
193.          postOrder(localRoot.leftChild);
     
194.          postOrder(localRoot.rightChild);
     
195.          System.out.print(localRoot.iData + " ");
     
196.          }
     
197.       }
     
198. // -------------------------------------------------------------
     
199.    public void displayTree()
     
200.       {
     
201.       Stack globalStack = new Stack();
     
202.       globalStack.push(root);
     
203.       int nBlanks = 32;
     
204.       boolean isRowEmpty = false;
     
205.       System.out.println(
     
206.       "......................................................");
     
207.       while(isRowEmpty==false)
     
208.          {
     
209.          Stack localStack = new Stack();
     
210.          isRowEmpty = true;
     
211.          for(int j=0; j< nBlanks; j++)
     
212.             System.out.print(" ");
     
213.          while(globalStack.isEmpty()==false)
     
214.             {
     
215.             Node temp = (Node)globalStack.pop();
     
216.             if(temp != null)
     
217.                {
     
218.                System.out.print(temp.iData);
     
219.                localStack.push(temp.leftChild);
     
220.                localStack.push(temp.rightChild);
     
221.                if(temp.leftChild != null ||
     
222.                                    temp.rightChild != null)
     
223.                   isRowEmpty = false;
     
224.                }
     
225.             else
     
226.                {
     
227.                System.out.print("--");
     
228.                localStack.push(null);
     
229.                localStack.push(null);
     
230.                }
     
231.             for(int j=0; j< nBlanks*2-2; j++)
     
232.                System.out.print(" ");
     
233.             }  // end while globalStack not empty
     
234.          System.out.println();
     
235.          nBlanks /= 2;
     
236.          while(localStack.isEmpty()==false)
     
237.             globalStack.push( localStack.pop() );
     
238.          }  // end while isRowEmpty is false
     
239.       System.out.println(
     
240.       "......................................................");
     
241.       }  // end displayTree()
     
242. // -------------------------------------------------------------
     
243.    }  // end class Tree
     
244. ////////////////////////////////////////////////////////////////
     
245. class TreeApp
     
246.    {
     
247.    public static void main(String[] args) throws IOException
     
248.       {
     
249.       int value;
     
250.       Tree theTree = new Tree();
     
251.       theTree.insert(50, 1.5);
     
252.       theTree.insert(25, 1.2);
     
253.       theTree.insert(75, 1.7);
     
254.       theTree.insert(12, 1.5);
     
255.       theTree.insert(37, 1.2);
     
256.       theTree.insert(43, 1.7);
     
257.       theTree.insert(30, 1.5);
     
258.       theTree.insert(33, 1.2);
     
259.       theTree.insert(87, 1.7);
     
260.       theTree.insert(93, 1.5);
     
261.       theTree.insert(97, 1.5);
     
262.       while(true)
     
263.          {
     
264.          System.out.print("Enter first letter of show, ");
     
265.          System.out.print("insert, find, delete, or traverse: ");
     
266.          int choice = getChar();
     
267.          switch(choice)
     
268.             {
     
269.             case "s":
     
270.                theTree.displayTree();
     
271.                break;
     
272.             case "i":
     
273.                System.out.print("Enter value to insert: ");
     
274.                value = getInt();
     
275.                theTree.insert(value, value + 0.9);
     
276.                break;
     
277.             case "f":
     
278.                System.out.print("Enter value to find: ");
     
279.                value = getInt();
     
280.                Node found = theTree.find(value);
     
281.                if(found != null)
     
282.                   {
     
283.                   System.out.print("Found: ");
     
284.                   found.displayNode();
     
285.                   System.out.print("
286. ");
     
287.                   }
     
288.                else
     
289.                   System.out.print("Could not find ");
     
290.                   System.out.print(value + "
291. ");
     
292.                break;
     
293.             case "d":
     
294.                System.out.print("Enter value to delete: ");
     
295.                value = getInt();
     
296.                boolean didDelete = theTree.delete(value);
     
297.                if(didDelete)
     
298.                   System.out.print("Deleted " + value + "
299. ");
     
300.                else
     
301.                   System.out.print("Could not delete ");
     
302.                   System.out.print(value + "
303. ");
     
304.                break;
     
305.             case "t":
     
306.                System.out.print("Enter type 1, 2 or 3: ");
     
307.                value = getInt();
     
308.                theTree.traverse(value);
     
309.                break;
     
310.             default:
     
311.                System.out.print("Invalid entry
312. ");
     
313.             }  // end switch
     
314.          }  // end while
     
315.       }  // end main()
     
316. // -------------------------------------------------------------
     
317.    public static String getString() throws IOException
     
318.       {
     
319.       InputStreamReader isr = new InputStreamReader(System.in);
     
320.       BufferedReader br = new BufferedReader(isr);
     
321.       String s = br.readLine();
     
322.       return s;
     
323.       }
     
324. // -------------------------------------------------------------
     
325.    public static char getChar() throws IOException
     
326.       {
     
327.       String s = getString();
     
328.       return s.charAt(0);
     
329.       }
     
330. //-------------------------------------------------------------
     
331.    public static int getInt() throws IOException
     
332.       {
     
333.       String s = getString();
     
334.       return Integer.parseInt(s);
     
335.       }
     
336. // -------------------------------------------------------------
     
337.    }  // end class TreeApp
     
338. ////////////////////////////////////////////////////////////////
     

复制代码

三、运行

1. C:java>java  TreeApp
   
2. Enter first letter of show, insert, find, delete, or traverse: s
   
3. ......................................................
   
4.                                 50
   
5.                 25                              75
   
6.         12              37              --              87
   
7.     --      --      30      43      --      --      --      93
   
8.   --  --  --  --  --  33  --  --  --  --  --  --  --  --  --  97
   
9. ......................................................
   
10. Enter first letter of show, insert, find, delete, or traverse: t
    
11. Enter type 1, 2 or 3: 1
    
12. Preorder traversal: 50 25 12 37 30 33 43 75 87 93 97
    
13. Enter first letter of show, insert, find, delete, or traverse: d
    
14. Enter value to delete: 87
    
15. Deleted 87
    
16. 97Enter first letter of show, insert, find, delete, or traverse: s
    
17. ......................................................
    
18.                                 50
    
19.                 25                              75
    
20.         12              37              --              93
    
21.     --      --      30      43      --      --      --      97
    
22.   --  --  --  --  --  33  --  --  --  --  --  --  --  --  --  --
    
23. ......................................................
    
24. Enter first letter of show, insert, find, delete, or traverse:
    

复制代码

  
  
   
   

     
   

     
   
  
  
  

  










源码下载：http://file.javaxxz.com/2014/10/29/235928234.zip