Javaのデータ構造(3)----強力なツリー
単純なソートツリー
汎用的なソートツリー(ソートされるため、ノードは比較可能である必要がありますが、具体的な比較ルールは自分で決めます)
package com.wz.util.tree;
import java.util.ArrayList;
import java.util.Iterator;
/**
*
*
* @author NumbCoder
*
*/
//
class BinaryNode {
private int data;
BinaryNode lChild;
BinaryNode rChild;
BinaryNode(int t) {
setData(t);
lChild = null;
rChild = null;
}
//
public boolean isLeaf() {
if (lChild == null && rChild == null)
return true;
else
return false;
}
public void setData(int data) {
this.data = data;
}
public int getData() {
return data;
}
}
//
public class BinaryTree {
private BinaryNode root;
BinaryTree(BinaryNode root) {
this.root = root;
root.lChild = null;
root.rChild = null;
}
//
public void insert(BinaryNode n) {
//
if (root == null)
root = n;
else {
BinaryNode current = root;
BinaryNode parentNode;
boolean flag = true;
while (flag) {
parentNode = current;
if (n.getData() > current.getData()) {
//
current = current.rChild;
if (current == null) {
parentNode.rChild = n;
flag = false;
}
} else if (n.getData() < current.getData()) {
current = current.lChild;
//
if (current == null) {
parentNode.lChild = n;
flag = false;
}
}
}
}
}
// ArrayList
public void creatBinaryTree(BinaryNode root, ArrayList<BinaryNode> aList) {
Iterator<BinaryNode> it = aList.iterator();
while (it.hasNext()) {
insert(it.next());
}
}
//
public void preOrder(BinaryNode t) {
if (t != null) {
System.out.println(t.getData());
preOrder(t.lChild);
preOrder(t.rChild);
}
}
//
public void inOrder(BinaryNode t) {
if (t != null) {
inOrder(t.lChild);
System.out.println(t.getData());
inOrder(t.rChild);
}
}
//
public void postOrder(BinaryNode t) {
if (t != null) {
postOrder(t.lChild);
postOrder(t.rChild);
System.out.println(t.getData());
}
}
}
汎用的なソートツリー(ソートされるため、ノードは比較可能である必要がありますが、具体的な比較ルールは自分で決めます)
package com.wz.util;
import java.util.ArrayList;
import java.util.Iterator;
/**
*
*
* @author NumbCoder
*
*/
class BinaryNode<T> implements Comparable<T> {
private T data;
BinaryNode<T> lChild;
BinaryNode<T> rChild;
BinaryNode(T t) {
setData(t);
lChild = null;
rChild = null;
}
/**
* T 、 n -1、0 1
* compareTo
*/
@Override
public int compareTo(T t) {
return 0;
}
public void setData(T data) {
this.data = data;
}
public T getData() {
return data;
}
//
public boolean isLeaf() {
if (lChild == null && rChild == null)
return true;
else
return false;
}
}
//
public class BinaryTree<T> {
private BinaryNode<T> root;
BinaryTree(BinaryNode<T> root) {
this.root = root;
root.lChild = null;
root.rChild = null;
}
//
public void insert(BinaryNode<T> n) {
//
if (root == null)
root = n;
else {
BinaryNode<T> current = root;
BinaryNode<T> parentNode;
boolean flag = true;
while (flag) {
parentNode = current;
if (n.compareTo(current.getData()) == 1) {
//
current = current.rChild;
if (current == null) {
parentNode.rChild = n;
flag = false;
}
} else if( n.compareTo(current.getData()) == -1){
current = current.lChild;
//
if (current == null) {
parentNode.lChild = n;
flag = false;
}
}
}
}
}
//
public void creatBinaryTree(BinaryNode<T> root,
ArrayList<BinaryNode<T>> aList) {
Iterator<BinaryNode<T>> it = aList.iterator();
while (it.hasNext()) {
insert(it.next());
}
}
//
private void preOrder(BinaryNode<T> t, ArrayList<T> list) {
if (t != null) {
list.add(t.getData());
preOrder(t.lChild, list);
preOrder(t.rChild, list);
}
}
public Iterator<T> itPreOrder() {
ArrayList<T> list = new ArrayList<T>();
preOrder(root, list);
return list.iterator();
}
//
private void inOrder(BinaryNode<T> t, ArrayList<T> list) {
if (t != null) {
inOrder(t.lChild, list);
list.add(t.getData());
inOrder(t.rChild, list);
}
}
public Iterator<T> itInOrder() {
ArrayList<T> list = new ArrayList<T>();
inOrder(root, list);
return list.iterator();
}
//
private void postOrder(BinaryNode<T> t, ArrayList<T> list) {
if (t != null) {
postOrder(t.lChild, list);
postOrder(t.rChild, list);
list.add(t.getData());
}
}
public Iterator<T> itPostOrder() {
ArrayList<T> list = new ArrayList<T>();
postOrder(root, list);
return list.iterator();
}
}