ツリー---ツリーの構造と遍歴
4337 ワード
本稿では,二叉木の構造と遍歴のみを紹介する.
ツリーのノードを作成します.
構築ツリー:
..
ツリーのノードを作成します.
public class BinaryTreeNode<T> {
public T data;
public BinaryTreeNode leftChild, rightChild;
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public BinaryTreeNode getLeftChild() {
return leftChild;
}
public void setLeftChild(BinaryTreeNode leftChild) {
this.leftChild = leftChild;
}
public BinaryTreeNode getRightChild() {
return rightChild;
}
public void setRightChild(BinaryTreeNode rightChild) {
this.rightChild = rightChild;
}
}
構築ツリー:
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;
public class BinaryTree<T> {
BinaryTreeNode<T> root;
public BinaryTree(){
}
/**
*
* @param list
*/
public void createBiTree(List<T> list){
Iterator<T> iterator = list.iterator();
while(iterator.hasNext()){
BinaryTreeNode<T> node = new BinaryTreeNode<T>();
node.setData(iterator.next());
insertTree(node);
}
}
/**
* , Child, ,
*
*
* @param node
*/
public void insertTree(BinaryTreeNode<T> node) {
if (root == null) {
root = node;
} else {
BinaryTreeNode<T> current = root;
while (true) {// ,
if (current.leftChild == null) {
current.leftChild = node;
//
return;
} else if (root.rightChild == null) {
current.rightChild = node;
return;
} else {
current = current.leftChild;
}
}
}
}
/**
* - root,left right
*
*/
public void preOrderTraverse(BinaryTreeNode node){
System.out.println(node.getData());
if(node.getLeftChild()!=null){
preOrderTraverse(node.getLeftChild());
}
if(node.getRightChild()!=null){
preOrderTraverse(node.getRightChild());
}
}
/**
* - root,left right
*
*/
public void preOrderTraverseLoop(BinaryTreeNode node){
//System.out.println(node.getData());
Stack<BinaryTreeNode> stack = new Stack<BinaryTreeNode>();
stack.push(node);
while(!stack.isEmpty()){
BinaryTreeNode biNode = stack.pop();
System.out.println(biNode.getData());
BinaryTreeNode left = biNode.leftChild;
if(left!=null){
stack.push(left);
}
BinaryTreeNode right = biNode.rightChild;
if(right!=null){
stack.push(right);
}
}
}
public static void main(String[] args) {
Integer[] ints = new Integer[]{1,3,9,8,7,6,2,98,76};
List list = new ArrayList<Integer>(ints.length);
for (int i = 0; i < ints.length; i++) {
list.add(ints[i]);
}
BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
binaryTree.createBiTree(list);
binaryTree.preOrderTraverse(binaryTree.root);
System.out.println("=========================");
binaryTree.preOrderTraverseLoop(binaryTree.root);
}
}
..