ツリーの非再帰的および再帰的ループおよび階層的ループ
4487 ワード
ツリーの再帰的遍歴
非再帰的遍歴方式はスタックを用いて実現できる
階層遍歴は先進的な先出しの結果となり,キューを利用して実現される.
public class BinaryTree {
public int value;
public BinaryTree left;
public BinaryTree right;
public void store(int value) {
if (value < this.value) {
if (left == null) {
left = new BinaryTree();
left.value = value;
} else {
left.store(value);
}
} else if (value > this.value) {
if (right == null) {
right = new BinaryTree();
right.value = value;
} else {
right.store(value);
}
}
}
public boolean find(int value) {
System.out.println("happen" + this.value);
if (value == this.value) {
return true;
} else if (value > this.value) {
if (right == null)
return false;
return right.find(value);
} else {
if (left == null)
return false;
return left.find(value);
}
}
public void preList() {
System.out.print(this.value + ",");
if (left != null)
left.preList();
if (right != null)
right.preList();
}
public void middleList() {
if (left != null)
left.middleList();
System.out.print(this.value + ",");
if (right != null)
right.middleList();
}
public void afterList() {
if (left != null)
left.afterList();
if (right != null)
right.afterList();
System.out.print(this.value + ",");
}
public static void main(String[] args) {
/*
* int[] data = new int[20]; for (int i = 0; i < data.length; i++) { data[i] = (int) (Math.random() * 100) + 1;
* System.out.print(data[i] + ","); }
*/
int[] data = { 7, 5, 8, 3, 6, 4, 9 };
System.out.println();
BinaryTree root = new BinaryTree();
root.value = data[0];
for (int i = 1; i < data.length; i++) {
root.store(data[i]);
}
// root.find(data[19]);
System.out.println(" ");
root.preList();
System.out.println();
System.out.println(" ");
root.middleList();
System.out.println();
System.out.println(" ");
root.afterList();
}
}
非再帰的遍歴方式はスタックを用いて実現できる
// （ ）---
public void nrPreOrderTraverse() {
Stack<Node<T>> stack = new Stack<Node<T>>();
Node<T> node = root;
stack.push(node);
while (!stack.isEmpty()) {
node = stack.pop();
System.out.println(node.getValue());
//
if (node.getRight() != null)
stack.push(node.getRight());
if (node.getLeft() != null)
stack.push(node.getLeft());
}
}
// ( )----
public void nrInOrderTraverse() {
Stack<Node<T>> stack = new Stack<Node<T>>();
Node<T> node = root;
while (node != null || !stack.isEmpty()) {
if (node != null) {
stack.push(node);
node = node.getLeft();
} else {
node = stack.pop();
System.out.print(node.getValue() + " ");
node = node.getRight();
}
}
}
// ( )
public void nrPostOrderTraverse() {
Stack<Node<T>> stack = new Stack<Node<T>>();
Node<T> node = root;
Node<T> preNode = null;//
while (node != null || !stack.isEmpty()) {
while (node != null) {
stack.push(node);
node = node.getLeft();
}
node = stack.peek();
if (node.getRight() == null || node.getRight() == preNode) {
System.out.println(node.getValue());
node = stack.pop();
preNode = node;
node = null;
} else {
node = node.getRight();
}
}
}
// ( )----
public void nrPostOrder() {
LinkedList<Node<T>> stack1 = new LinkedList<>(), stack2 = new LinkedList<>();
stack1.push(root);
while (!stack1.isEmpty()) {
Node<T> node = stack1.pop();
stack2.push(node);
if (node.getLeft() != null) {
stack1.push(node.getLeft());
}
if (node.getRight() != null) {
stack1.push(node.getRight());
}
}
while (!stack2.isEmpty()) {
Node<T> node = stack2.pop();
System.out.print(node.getValue() + " ");
}
}
階層遍歴は先進的な先出しの結果となり,キューを利用して実現される.
// -- ，FIFO
public void levelTraverse(Node<T> node) {
Queue<Node<T>> queue = new LinkedBlockingQueue<Node<T>>();
queue.add(node);
while (!queue.isEmpty()) {
Node<T> temp = queue.poll();
if (temp != null) {
System.out.print(temp.getValue());
if(temp.getLeft()!=null)
queue.add(temp.getLeft());
if(temp.getRight())
queue.add(temp.getRight());
}
}
}