/** * 二叉树节点类 * */ class Node<T extends Comparable> { public Node(T data){ this.data=data; } T data; Node<T> left; Node<T> right; } /** * 二叉树类 */ public class BinaryTree<T extends Comparable> { /** * 根節點 */ private Node<T> root; /** * 插入一個值 * @param value */ public void insert(T value) { Node<T> node = new Node<T>(value); if (root == null) { root = node; } else { Node<T> curr = root; Node<T> parrent; while (true) { parrent = curr; if (value.compareTo(curr.data) >= 0) { curr = curr.right; if (curr == null) { parrent.right=node; return; } } else { curr = curr.left; if (curr == null) { parrent.left=node; return; } } } } } /** * 尋找一個值對應的節點 * @param value * @return */ public Node<T> find(T value) { Node<T> curr = root; while (curr.data.equals(value) == false) { if (value.compareTo(curr.data) > 0) { curr = curr.right; } else { curr = curr.left; } if (curr == null) { return null; } } return curr; } /** * 輸出 * */ public void printAll() { System.out.println("--------------先序遍历------------------"); preOrder(root); System.out.println("--------------中序遍历------------------"); inorder(root); System.out.println("--------------后序遍历------------------"); postOrder(root); } /** * 先序遍歷 * @param node */ private void preOrder(Node<T> node) { if (node != null) { System.out.println(node.data); preOrder(node.left); preOrder(node.right); } } /** * 中序遍歷 * @param node */ private void inorder(Node<T> node) { if (node != null) { inorder(node.left); System.out.println(node.data); inorder(node.right); } } /** * 后序遍歷 * @param node */ private void postOrder(Node<T> node) { if (node != null) { postOrder(node.left); postOrder(node.right); System.out.println(node.data); } } public static void main(String[] args) { Integer[] arr={31,25,47,42,50}; // 以數組2為基礎創建二叉樹 BinaryTree<Integer> tree1=new BinaryTree<Integer>(); for(Integer i:arr){ tree1.insert(i); } tree1.printAll(); String[] arr02={"Ceaser","Andy","Martin","Bill","Felex","Fowler","Green","Alice","Gates"}; // 以數組2為基礎創建二叉樹 BinaryTree<String> tree=new BinaryTree<String>(); for(String str:arr02){ tree.insert(str); } tree.printAll(); // 將在二叉樹中不存在的元素放入鏈錶 String[] arr01={"Andy","Bill","Cindy","Douglas","Felex","Green"}; List<String> ls=new ArrayList<String>(); for(String str:arr01){ if(tree.find(str)==null){ ls.add(str); } } // 輸出 System.out.println("--------------二叉樹中不存在的元素有------"); for(String str:ls){ System.out.println(str); } } }
本文转自张昺华-sky博客园博客,原文链接:http://www.cnblogs.com/xiandedanteng/p/3884976.html,如需转载请自行联系原作者