【转】二叉树

package foo;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * 创建树的文件内容，例如树<pre>
 *               A
 *           B        C
 *        D         E     
 * </pre>
 * 就是其先序序列：A B D # # # C E # # #
 * 其中第1、2个#是D的左右子节点（空），滴3个#是B的右子节点（空），第4、5个#是
 * E的左右子节点（空），第6个#是C的右子节点（空）
 * */

/**
 * 仅作演示使用 
 * */
class Tree {
    
    // 在eclipse 中创建的普通java项目，所以路径是这么写的
    private static final String filePath = "bin/foo/input.txt";

    private Node<String> root;
    
    public Tree() {
    }
    
    public Tree(Node<String> root) {
        this.root = root;
    }
    
    //创建二叉树
    public void buildTree() {
        
        Scanner scn = null;
        try {
            scn = new Scanner(new File(filePath));
        } catch (FileNotFoundException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
            return;
        }
        root = createTree(root,scn);        
    }
    
    // 先序遍历创建二叉树（递归）
    private Node<String> createTree(Node<String> node,Scanner scn) {
        
        String temp  = scn.next();
        
        if (temp.trim().equals("#")) {
            return null;
        } else {
            node = new Node<String>(temp);
            node.setLeft(createTree(node.getLeft(), scn));
            node.setRight(createTree(node.getRight(), scn));
            return node;
        }
    }
    
    
    
    //中序遍历(递归)
    public void inOrderTraverse() {
        inOrderTraverse(root);
    }
    
    public void inOrderTraverse(Node<String> node) {
        if (node != null) {
            inOrderTraverse(node.getLeft());
            System.out.println(node.getValue());
            inOrderTraverse(node.getRight());
        }
    }
    
    
    //中序遍历(非递归)
    public void nrInOrderTraverse() {
        
        Stack<Node<String>> stack = new Stack<Node<String>>();
        Node<String> node = root;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.getLeft();
            }
            node = stack.pop();
            System.out.println(node.getValue());
            node = node.getRight();
            
        }
                
    }
    //先序遍历(递归)
    public void preOrderTraverse() {
        preOrderTraverse(root);
    }
    
    public void preOrderTraverse(Node<String> node) {
        if (node != null) {
            System.out.println(node.getValue());
            preOrderTraverse(node.getLeft());
            preOrderTraverse(node.getRight());
        }
    }
    
    
    //先序遍历（非递归）
    public void nrPreOrderTraverse() {
        
        Stack<Node<String>> stack = new Stack<Node<String>>();
        Node<String> node = root;
        
        while (node != null || !stack.isEmpty()) {
            
            while (node != null) {
                System.out.println(node.getValue());
                stack.push(node);
                node = node.getLeft();
            }
            node = stack.pop();
            node = node.getRight();
        }    
    }
    
    //后序遍历(递归)
    public void postOrderTraverse() {
        postOrderTraverse(root);
    }
    
    public void postOrderTraverse(Node<String> node) {
        if (node != null) {
            postOrderTraverse(node.getLeft());
            postOrderTraverse(node.getRight());
            System.out.println(node.getValue());
        }
    }
    
    //后续遍历(非递归)
    public void nrPostOrderTraverse() {
        
        Stack<Node<String>> stack = new Stack<Node<String>>();
        Node<String> node = root;
        Node<String> 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 levelTraverse() {
        levelTraverse(root);
    }
    
    public void levelTraverse(Node<String> node) {
    
        Queue<Node<String>> queue = new LinkedBlockingQueue<Node<String>>();
        queue.add(node);
        while (!queue.isEmpty()) {
            
            Node<String> temp = queue.poll();
            if (temp != null) {
                System.out.println(temp.getValue());
                queue.add(temp.getLeft());
                queue.add(temp.getRight());
            }
                        
        }
                
    }
    
    
    
    
}



//树的节点

class Node<T> {
    
    private Node<T> left;
    private Node<T> right;
    private T value;
    
    public Node() {
    }
    public Node(Node<T> left,Node<T> right,T value) {
        this.left = left;
        this.right = right;
        this.value = value;
    }
    
    public Node(T value) {
        this(null,null,value);
    }
    public Node<T> getLeft() {
        return left;
    }
    public void setLeft(Node<T> left) {
        this.left = left;
    }
    public Node<T> getRight() {
        return right;
    }
    public void setRight(Node<T> right) {
        this.right = right;
    }
    public T getValue() {
        return value;
    }
    public void setValue(T value) {
        this.value = value;
    }
        
}


public class Main {
    
    /**
     * 二分查找
     * @param key 搜索的目标
     * */
    private static int binarySearch(int[] a, int fromIndex, int toIndex, int key) {
        int low = fromIndex;
        int high = toIndex - 1;
        int mid, midVal;
        while (low <= high) {
            mid = (low + high) >>> 1;
            midVal = a[mid];
            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }
    
    public static void swap(int[] a, int index1, int index2) {
        int temp = a[index1];
        a[index1] = a[index2];
        a[index2] = temp;
    }
    
    public static void main(String[] args) {
        Tree tree = new Tree();
        tree.buildTree();
        System.out.println("中序遍历（递归）");
        tree.inOrderTraverse();
        System.out.println("中序遍历（非递归）");
        tree.nrInOrderTraverse();
        System.out.println("后续遍历（递归）");
        tree.postOrderTraverse();
        System.out.println("后续遍历（非递归）");
        tree.nrPostOrderTraverse();
        System.out.println("先序遍历（递归）");
        tree.preOrderTraverse();
        System.out.println("先序遍历（非递归）");
        tree.nrPreOrderTraverse();
    }
}