生活随笔
收集整理的這篇文章主要介紹了
java实现树
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
java實現樹，采用鏈式存儲，父節點記錄子節點的存儲位置。
首先定義一個用于存儲子節點位置的節點類
[java]?view plaincopy
package?my.tree.link;?? ?? public?class?SubNode?{?? ????private?int?location;?? ????private?SubNode?next;?? ?????? ????public?SubNode(){?? ????????this.location?=?0;?? ????????this.next?=?null;?? ????}?? ????public?SubNode(int?location){?? ????????this.location?=?location;?? ????????this.next?=?null;?? ????}?? ?????? ????public?SubNode(int?location,?SubNode?next){?? ????????this.location?=?location;?? ????????this.next?=?next;?? ????}?? ?????? ????public?void?setLocation(int?location){?? ????????this.location?=?location;?? ????}?? ?????? ????public?int?getLocation(){?? ????????return?this.location;?? ????}?? ?????? ????public?void?setNext(SubNode?next){?? ????????this.next?=?next;?? ????}?? ?????? ????public?SubNode?getNext(){?? ????????return?this.next;?? ????}?? }??
然后定義一個用于存儲節點信息的節點類
[java]?view plaincopy
package?my.tree.link;?? ?? public?class?Node<T>?{?? ????private?T?data;?? ????private?SubNode?son;?? ?????? ????public?Node(){?? ?????????? ????}?? ?????? ????public?Node(T?data){?? ????????this.data?=?data;?? ????????this.son?=?null;?? ????}?? ?????? ????public?Node(T?data,?SubNode?son){?? ????????this.data?=?data;?? ????????this.son?=?son;?? ????}?? ?????? ????public?void?setData(T?data){?? ????????this.data?=?data;?? ????}?? ?????? ????public?T?getData(){?? ????????return?this.data;?? ????}?? ?????? ????public?void?setSon(SubNode?son){?? ????????this.son?=?son;?? ????}?? ?????? ????public?SubNode?getSon(){?? ????????return?this.son;?? ????}?? ?????? ????@Override?? ????public?String?toString(){?? ????????return?"節點："?+?this.data;?? ????}?? }??
編寫鏈式存儲的樹類，這里采用遞歸求解樹的深度(貌似有問題，在求樹的深度是，很迷糊)
[java]?view plaincopy
package?my.tree.link;?? ?? import?java.util.LinkedList;?? import?java.util.List;?? ?? public?class?MyLinkTree<T>?{?? ????private?final?int?DEFAUL_SIZE?=?10;?? ????private?int?size;?? ????private?int?count;?? ?? ????private?Node<T>[]?nodes;?? ?? ????@SuppressWarnings("unchecked")?? ????public?MyLinkTree()?{?? ????????this.size?=?this.DEFAUL_SIZE;?? ????????this.nodes?=?new?Node[this.size];?? ????????this.count?=?0;?? ????}?? ?? ????@SuppressWarnings("unchecked")?? ????public?MyLinkTree(int?size)?{?? ????????this.size?=?size;?? ????????this.nodes?=?new?Node[this.size];?? ????????this.count?=?0;?? ????}?? ?? ????public?MyLinkTree(T?data)?{?? ????????this();?? ????????Node<T>?node?=?new?Node<T>(data);?? ????????this.nodes[0]?=?node;?? ????????this.count++;?? ????}?? ?? ????public?MyLinkTree(Node<T>?root)?{?? ????????this();?? ????????this.nodes[0]?=?root;?? ????????this.count++;?? ????}?? ?? ????public?void?add(Node<T>?node,?Node<T>?parent)?{?? ????????SubNode?son?=?new?SubNode();?? ????????for?(int?i?=?0;?i?<?this.size;?i++)?{?? ????????????if?(this.nodes[i]?==?null)?{?? ????????????????this.nodes[i]?=?node;?? ????????????????son.setLocation(i);?? ????????????????break;?? ????????????}?? ????????}?? ?? ?????????? ????????SubNode?next?=?parent.getSon();?? ????????if?(next?!=?null)?{?? ????????????while?(next.getNext()?!=?null)?{?? ????????????????next?=?next.getNext();?? ????????????}?? ????????????next.setNext(son);?? ????????}?else?{?? ????????????parent.setSon(son);?? ????????}?? ?? ????????this.count++;?? ????}?? ?? ????public?int?size()?{?? ????????return?this.count;?? ????}?? ?? ????public?Node<T>?getRoot()?{?? ????????return?this.nodes[0];?? ????}?? ?? ?????? ????public?List<Node<T>>?getSon(Node<T>?parent)?{?? ????????List<Node<T>>?list?=?new?LinkedList<Node<T>>();?? ????????SubNode?son?=?parent.getSon();?? ????????while?(son?!=?null)?{?? ????????????list.add(this.nodes[son.getLocation()]);?? ????????????son?=?son.getNext();?? ????????}?? ????????return?list;?? ????}?? ?? ?????? ????public?int?getDepth(Node<T>?node)?{?? ????????SubNode?son?=?node.getSon();?? ????????if(son?==?null){?? ????????????return?1;?? ????????}else{?? ????????????int?max?=?0;?? ????????????while(son?!=?null){?? ????????????????int?temp?=?this.getDepth(this.nodes[son.getLocation()]);?? ????????????????max?=?temp?>?max???temp?:?max;?? ????????????????son?=?son.getNext();?? ????????????}?? ?????????????? ????????????return?max+1;?? ????????}?? ????}?? ?? ????public?int?deep()?{?? ????????int?max?=?0;?? ????????for?(int?i?=?0;?i?<?this.count;?i++)?{?? ????????????int?temp?=?this.getDepth(this.nodes[i]);?? ????????????max?=?max?>?temp???max?:?temp;?? ????????}?? ????????return?max;?? ????}?? }??
最后編寫一個測試端，用來測試功能是否基本實現
[java]?view plaincopy
package?my.tree.link;?? ?? public?class?MyLinkTreeClient?{?? ????public?static?void?main(String[]?args)?{?? ????????Node<string>?root?=?new?Node<string>("A");?? ????????Node<string>?b?=?new?Node<string>("B");?? ????????Node<string>?c?=?new?Node<string>("C");?? ????????Node<string>?d?=?new?Node<string>("D");?? ????????Node<string>?e?=?new?Node<string>("E");?? ????????Node<string>?f?=?new?Node<string>("F");?? ????????Node<string>?g?=?new?Node<string>("G");?? ????????Node<string>?h?=?new?Node<string>("H");?? ????????MyLinkTree<string>?tree?=?new?MyLinkTree<string>(root);?? ????????tree.add(b,?root);?? ?? ?? ?? ?? ?? ?? ?? ????????System.out.println(tree.deep());?? ?? ????}?? }
實現一顆樹，采用數組的存儲方式，將樹中的節點用Node類表示，方便與操作。
首先，整棵樹的數組結構如下表所示，根節點的無父節點，用“-1”表示。
| index | Data | parent |
| 0 | A | -1 |
| 1 | B | 0 |
| 2 | C | 0 |
| 3 | D | 0 |
| 4 | E | 1 |
| 5 | F | 1 |
| 6 | G | 5 |
其次，定義一個節點Node類，用來存儲每個節點的內容
[java]?view plaincopy
package?my.tree;?? ?? public?class?Node<T>?{?? ????private?T?data;?? ????private?int?parent;?? ?????? ????public?Node(){?? ????}?? ?????? ????public?Node(T?data){?? ????????this.data?=?data;?? ????}?? ?????? ????public?Node(T?data,int?parent){?? ????????this.data?=?data;?? ????????this.parent?=?parent;?? ????}?? ?????? ????public?void?setData(T?data){?? ????????this.data?=?data;?? ????}?? ?????? ????public?T?getData(){?? ????????return?this.data;?? ????}?? ?????? ????public?void?setParent(int?parent){?? ????????this.parent?=?parent;?? ????}?? ?????? ????public?int?getParent(){?? ????????return?this.parent;?? ????}?? }??
開始實現樹，提供基本的插入節點、獲取所有節點、獲取樹的深度操作（著重）這些將數組大小設置為2，主要是考慮數組能否自動擴容;
[java]?view plaincopy
package?my.tree;?? ?? import?java.util.ArrayList;?? import?java.util.Arrays;?? import?java.util.List;?? ?? public?class?MyTree<T>?{?? ????private?final?int?DEFAULT_SIZE?=?2;?? ????private?int?size;?? ????private?int?count;?? ????private?Object[]?nodes;?? ?? ????public?MyTree()?{?? ????????this.size?=?this.DEFAULT_SIZE;?? ????????this.nodes?=?new?Object[this.size];?? ????????this.count?=?0;?? ????}?? ?? ????public?MyTree(Node<T>?root)?{?? ????????this();?? ????????this.count?=?1;?? ????????this.nodes[0]?=?root;?? ????}?? ?? ????public?MyTree(Node<T>?root,?int?size)?{?? ????????this.size?=?size;?? ????????this.nodes?=?new?Object[this.size];?? ????????this.count?=?1;?? ????????this.nodes[0]?=?root;?? ????}?? ?? ?????? ????public?void?add(Node<T>?node)?{?? ????????for?(int?i?=?0;?i?<?this.size;?i++)?{?? ????????????if?(this.nodes[i]?==?null)?{?? ????????????????nodes[i]?=?node;?? ????????????????break;?? ????????????}?? ????????}?? ????????this.count++;?? ????}?? ?? ????public?void?check(){?? ????????if(this.count?>=?this.size){?? ????????????this.enlarge();?? ????????}?? ????}?? ?????? ????public?void?add(Node<T>?node,?Node<T>?parent)?{?? ????????this.check();?? ????????node.setParent(this.position(parent));?? ????????this.add(node);?? ????}?? ?? ?????? ????public?int?position(Node<T>?node)?{?? ????????for?(int?i?=?0;?i?<?this.size;?i++)?{?? ????????????if?(nodes[i]?==?node)?{?? ????????????????return?i;?? ????????????}?? ????????}?? ????????return?-1;?? ????}?? ?????? ?????? ????public?int?getSize(){?? ????????return?this.count;?? ????}?? ?????? ?????? ????@SuppressWarnings("unchecked")?? ????public?Node<T>?getRoot(){?? ????????return?(Node<T>)?this.nodes[0];?? ????}?? ?????? ?????? ????@SuppressWarnings("unchecked")?? ????public?List<Node<T>>?getAllNodes(){?? ????????List<Node<T>>?list?=?new?ArrayList<Node<T>>();?? ????????for(int?i=0;i<this.size;i++){?? ????????????if(this.nodes[i]?!=?null){?? ????????????????list.add((Node<T>)nodes[i]);?? ????????????}?? ????????}?? ????????return?list;?? ????}?? ?????? ?????? ????@SuppressWarnings("unchecked")?? ????public?int?getDepth(){?? ?????????? ????????int?max?=?1;?? ????????if(this.nodes[0]?==?null){?? ????????????return?0;?? ????????}?? ?????????? ????????for(int?i=0;i<this.count;i++){?? ????????????int?deep?=?1;?? ????????????int?location?=?((Node<T>)(this.nodes[i])).getParent();?? ????????????while(location?!=?-1?&&?this.nodes[location]?!=?null){?? ????????????????location?=?((Node<T>)(this.nodes[location])).getParent();?? ????????????????deep++;?? ????????????}?? ????????????if(max?<?deep){?? ????????????????max?=?deep;?? ????????????}?? ????????}?? ????????return?max;?? ????}?? ?????? ????public?void?enlarge(){?? ????????this.size?=?this.size?+?this.DEFAULT_SIZE;?? ????????Object[]?newNodes?=?new?Object[this.size];?? ????????newNodes?=?Arrays.copyOf(nodes,?this.size);?? ????????Arrays.fill(nodes,?null);?? ????????this.nodes?=?newNodes;?? ????????System.out.println("enlarge");?? ????}?? }??
最后，使用MyTreeClient來測試下，基本功能是否都已經實現;
[java]?view plaincopy
package?my.tree;?? ?? public?class?MyTreeClient?{?? ????public?static?void?main(String[]?args){?? ????????Node<String>?root?=?new?Node<String>("A",-1);?? ????????MyTree<String>?tree?=?new?MyTree<String>(root);?? ????????Node<String>?b?=?new?Node<String>("B");?? ????????Node<String>?c?=?new?Node<String>("C");?? ????????Node<String>?d?=?new?Node<String>("D");?? ????????Node<String>?e?=?new?Node<String>("E");?? ????????Node<String>?f?=?new?Node<String>("F");?? ????????Node<String>?g?=?new?Node<String>("G");?? ????????tree.add(b,root);?? ????????tree.add(c,root);?? ????????tree.add(d,root);?? ?????????? ????????tree.add(e,b);?? ????????tree.add(f,b);?? ????????tree.add(g,f);?? ?????????? ?????????? ????????System.out.println(tree.getSize());?? ????????System.out.println(tree.getRoot().getData());?? ????????System.out.println(tree.getAllNodes());?? ????????System.out.println(tree.getDepth());?? ????????tree.add(new?Node<String>("H"),g);?? ????????System.out.println(tree.getDepth());?? ????????tree.enlarge();?? ????}?? } ?
總結
以上是生活随笔為你收集整理的java实现树的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
