1，个人感觉二叉树的实现主要还是如何构造一颗二叉树。构造二叉树函数的设计方法多种多样，本例采用 addNode 方法实现。以下程序通过定义内部类来表示二叉树的结点，然后再实现了二叉树这种数据结构的一些基本操作。
2，说说以下程序的一些不足：
a，56行中的判断树是否为空时，依据根结点的数据域是否为空来判断。而使用不带参数的构造函数构造二叉树时，根结点的不空的，此时说明树已经有了根结点，但是根结点的数据却是空的，此时的树高度为1，但是不能访问树根结点，因为树根结点的数据域没有值。
3，重点讲解下二叉树遍历的几个方法：
先序遍历：将先序遍历过程中遇到的结点添加到ArrayList<TreeNode>中。根据先序遍历的递归的性质，调用addAll(Container c)方法完成遍历主要过程。
层序遍历：层序遍历需要使用队列，方法level_Traverse 中定义了ArrayDeque<TreeNode> 类型的队列。
1 package tree; 2 3 import java.util.ArrayDeque; 4 import java.util.ArrayList; 5 import java.util.List; 6 import java.util.Queue; 7 8 public class BinaryTree{ 9 //为什么要用静态内部类？静态内部类中不能访问外部类的非静态成员 10 public static class TreeNode{ 11 // E data; 12 Object data; 13 TreeNode left; 14 TreeNode right; 15 public TreeNode(){ 16 17 } 18 public TreeNode(Object data){ 19 this.data = data; 20 } 21 //构造一个新节点，该节点以left节点为其左孩子，right节点为其右孩子 22 public TreeNode(Object data, TreeNode left, TreeNode right){ 23 this.data = data; 24 this.left = left; 25 this.right = right; 26 } 27 } 28 29 private TreeNode root;//实现二叉树的类的数据域，即根结点来表示二叉树 30 31 public BinaryTree(){ 32 this.root = new TreeNode(); 33 } 34 //以指定的根元素创建一颗二叉树 35 public BinaryTree(E data){ 36 this.root = new TreeNode(data); 37 } 38 39 //为指定的结点添加子结点,为什么要有addNode方法？因为给定一系列的结点，通过调用该方法来构造成一颗树 40 public TreeNode addNode(TreeNode parent, E data, boolean isLeft){ 41 if(parent == null) 42 throw new RuntimeException("父节点为空，无法添加子结点"); 43 if(isLeft && parent.left != null) 44 throw new RuntimeException("节点已经左子节点，添加失败"); 45 if(!isLeft && parent.right != null) 46 throw new RuntimeException("节点已经有右子节点，添加失败"); 47 TreeNode newNode = new TreeNode(data); 48 if(isLeft) 49 parent.left = newNode; 50 else 51 parent.right = newNode; 52 return newNode; 53 } 54 55 public boolean empty(){ 56 return root.data == null;//根据根元素判断二叉树是否为空 57 } 58 59 public TreeNode root(){ 60 if(empty()) 61 throw new RuntimeException("树空，无法访问根结点"); 62 return root; 63 } 64 65 public E parent(TreeNode node){ 66 return null;//采用二叉树链表存储时，访问父结点需要遍历整棵二叉树，因为这里不实现 67 } 68 69 //访问指定节点的左结点，返回的是其左孩子的数据域 70 public E leftChild(TreeNode parent){ 71 if(parent == null) 72 throw new RuntimeException("空结点不能访问其左孩子"); 73 return parent.left == null ? null : (E)parent.left.data; 74 } 75 public E rightChild(TreeNode parent){ 76 if(parent == null) 77 throw new RuntimeException("空结点不能访问其右孩子"); 78 return parent.right == null ? null : (E)parent.right.data; 79 } 80 81 public int deep(){ 82 return deep(root); 83 } 84 private int deep(TreeNode node){ 85 if(node == null) 86 return 0; 87 else if(node.left == null && node.right == null) 88 return 1; 89 else{ 90 int leftDeep = deep(node.left); 91 int rightDeep = deep(node.right); 92 int max = leftDeep > rightDeep ? leftDeep : rightDeep; 93 return max + 1; 94 } 95 } 96 97 /*二叉树的先序遍历，实现思想如下：树是一种非线性结构，树中各个结点的组织方式有多种方式 98 * 先序，即是一种组织方式。它将结点的非线性变成了按照某种方式组织成的线性结构 99 */100 //返回一个list，树中结点以先序的方式存放在该list中101 public List preTraverse(){102 return preOrderTraverse(root);103 }104 private List preOrderTraverse(TreeNode node){105 List list = new ArrayList ();106 list.add(node);107 if(node.left != null)108 list.addAll(preOrderTraverse(node.left));//递归的奇妙之处109 if(node.right != null)110 list.addAll(preOrderTraverse(node.right));111 return list;112 }113 114 //中序遍历115 public List inTraverse(){116 return inOrderTraverse(root);117 }118 private List inOrderTraverse(TreeNode node){119 List list = new ArrayList ();120 if(node.left != null)121 list.addAll(inOrderTraverse(node.left));122 list.add(node);123 if(node.right != null)124 list.addAll(inOrderTraverse(node.right));125 return list;126 }127 128 //后序遍历129 public List postTraverse(){130 return post_Traverse(root);131 }132 private List post_Traverse(TreeNode node){133 List list = new ArrayList ();134 if(node.left != null)135 list.addAll(post_Traverse(node.left));136 if(node.right != null)137 list.addAll(post_Traverse(node.right));138 list.add(node);139 return list;140 }141 142 //层序遍历143 public List levelTraverse(){144 return level_Traverse(root);145 }146 private List level_Traverse(TreeNode node){147 Queue queue = new ArrayDeque ();148 List list = new ArrayList ();//按层序遍历定义的顺序将树中结点依次添加到数组列表中149 if(root != null)//先将根结点入队列150 queue.offer(root);151 while(!queue.isEmpty())//队列不空时，说明遍历还未结束152 {153 list.add(queue.peek());//将队头元素添加到数组列表中154 TreeNode p = queue.poll();//队头元素出队列155 if(p.left != null)156 queue.offer(p.left);//队头元素的左孩子入队列157 if(p.right != null)158 queue.offer(p.right);//队头元素的右孩子入队列159 }160 return list;161 }162 }
测试遍历的程序如下：
import java.util.ArrayList;import java.util.List;public class BinaryTreeTest { public static void main(String[] args) { BinaryTree bt = new BinaryTree ("根节点"); BinaryTree.TreeNode tn1 = bt.addNode(bt.root(),"第二层左子结点", true); BinaryTree.TreeNode tn2 = bt.addNode(bt.root(), "第二层右子结点", false); BinaryTree.TreeNode tn3 = bt.addNode(tn2,"第三层左子结点",true); List list1 = new ArrayList (); list1 = bt.inTraverse(); System.out.println("inorder traverse"); for(BinaryTree.TreeNode node : list1) System.out.print(node.data + " "); List list2 = new ArrayList (); list2 = bt.preTraverse(); System.out.println("\n preorder traverse"); for(BinaryTree.TreeNode node : list2) System.out.print(node.data + " "); List list3 = new ArrayList (); list3 = bt.levelTraverse(); System.out.println("\n level traverse"); for(BinaryTree.TreeNode node : list3) System.out.println(node.data + " "); }}