ツリー---ツリーの構造と遍歴

本稿では,二叉木の構造と遍歴のみを紹介する.
 
ツリーのノードを作成します.

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);
    }

}

 ..