1.遍历模式
前序遍历：根->左->右（深度优先）
中序遍历：左->根->右（深度优先）
后序遍历：左->右->根（深度优先）
层次遍历：每一层从左到右(广度优先）
2.例子：
3.前序遍历的实现思想和API构建：
代码实现：
//前序遍历 //获取整个树中所有的键 public QueuepreTraversal(){ Queue keys =new Queue (); preTraversal(root,keys); return keys; } //获取指定树x的所有键，并放到key队列中 private void preTraversal(Node x,Queue keys){ //安全性验证 if(x==null){ return; } //把x节点的key放到keys中 keys.InQueue(x.key); //递归遍历x节点的左子树 if(x.left!=null){ preTraversal(x.left,keys); } //递归遍历x节点的右子树 if(x.right!=null){ preTraversal(x.right,keys); } }
4.中序遍历的实现思想和API构建：
代码实现：
//中序遍历 //使用中序遍历来获取树中所有的键 public QueuemidTraversal(){ Queue keys =new Queue (); midTraversal(root,keys); return keys; } //使用中序遍历来获取指定树x中的所有键，并存放到keys中 private void midTraversal(Node x,Queue keys){ //安全性校验 if(x==null){ return; } //先递归，把左子树中所有的键放到keys中 if(x.left!=null){ midTraversal(x.left,keys); } //把当前节点的键放到keys中 keys.InQueue(x.key); //再递归，把右子树中的键放到keys中 if(x.right!=null){ midTraversal(x.right,keys); } }
5.后序遍历的实现思想和API构建：
代码实现：
//后序遍历 //使用后序遍历来获取树中所有的键 public QueuebackTraversal(){ Queue keys =new Queue (); backTraversal(root,keys); return keys; } //使用后序遍历来获取指定树x中的所有键，并存储到keys队列中 private void backTraversal(Node x,Queue keys){ //安全性校验 if(x==null){ return; } //先递归，把左子树的键全部放到keys中 if(x.left!=null){ backTraversal(x.left,keys); } //再递归把右子树中的键全部放到keys中 if(x.right!=null){ backTraversal(x.right,keys); } //最后把x节点的键放到keys中 keys.InQueue(x.key); }
6.层次遍历的实现思想和API构建：
代码实现：
//层次遍历 //使用层次遍历获取整个树中所有的键 public QueuelayerTraversal(){ //定义两个队列，分别存储树中的键和树中的节点 Queue keys =new Queue (); Queue nodes =new Queue (); //默认往队列中放入根节点 nodes.InQueue(root); //循环弹出节点,循环结束的条件是节点为空了，没有节点了 while(!nodes.isEmpty()){ //1.从队列中弹出一个节点，把key放入到keys中 Node n=nodes.OutQueue(); keys.InQueue(n.key); //2.判断当前节点还有没有左子节点，如果有，则放入到nodes中 if(n.left!=null){ nodes.InQueue(n.left); } //3.判断当前节点还有没有右子节点，如果有，则放入到nodes中 if(n.right!=null){ nodes.InQueue(n.right); } } return keys; }
程序测试结果：
源代码：
package Tree;
import Queue.Queue;
public class binaryTreeTraversalTest {
public static void main(String[] args) {
//创建树
binaryTree tree =new binaryTree();
tree.put("E","蜘蛛侠");
tree.put("B","蝙蝠侠");
tree.put("G","钢铁侠");
tree.put("A","绿巨人");
tree.put("D","美国队长");
tree.put("F","黑豹");
tree.put("H","战争机器");
tree.put("C","战争机器");
//前序遍历
//把键值全部存储到队列keys中
Queue keys =tree.preTraversal();
//根据keys的键，再去调用树中的get方法来获得value
System.out.print("前序遍历：");
for(String str:keys){
String value=tree.get(str);
System.out.print("["+str+"--"+value+"]"+"-->");
}
System.out.println("n--------------------------------------------");
//中序遍历
System.out.print("中序遍历:");
Queue keys2 =tree.midTraversal();
for(String str:keys2){
String value=tree.get(str);
System.out.print("["+str+"--"+value+"]"+"-->");
}
System.out.println("n--------------------------------------------");
//后序遍历
System.out.print("后序遍历:");
Queue keys3 =tree.backTraversal();
for(String str:keys3){
String value=tree.get(str);
System.out.print("["+str+"--"+value+"]"+"-->");
}
System.out.println("n--------------------------------------------");
//层次遍历
System.out.print("层次遍历:");
Queue keys4 =tree.layerTraversal();
for(String str:keys4){
String value=tree.get(str);
System.out.print("["+str+"--"+value+"]"+"-->");
}
System.out.println("n--------------------------------------------");
}
}
运行结果：
关于树的所有代码打包：
package Tree; import Queue.Queue; public class binaryTree,value > { //记录根节点 private Node root; //记录元素个数 private int N=0; //构造方法，初始化二叉树 public binaryTree(key key,value value,Node left,Node right) { // TODO Auto-generated constructor stub this.root=new Node(key, value, left, right); this.N=1; } public binaryTree() { // TODO Auto-generated constructor stub } private class Node{ //存储键 public key key; //存储值 public value value; //存储左节点 public Node left; //存储右节点 public Node right; //构造方法 public Node(key key,value value,Node left,Node right) { // TODO Auto-generated constructor stub this.key=key; this.value=value; this.left=left; this.right=right; } } //获取元素个数 public int size(){ return N; } //向树中添加元素,key-value public void put(key key,value value){ root=put(root,key,value); } //向指定的树x中添加key-value，并返回添加元素后新的树 private Node put(Node x,key key,value value){ //如果x子树为空，则把新节点当作根节点使用 if(x==null){ N++;//元素个数+1 return new Node(key, value, null, null); //直接创建一个根节点并返回 } int result=key.compareTo(x.key); //如果x子树不为空，比较key的值，比当前节点小就往左放，比当前节点大就往右放 if(result>0){ //递归调用put直到找到根节点右侧合适的位置 x.right=put(x.right,key,value); }else if(result<0){ //递归调用put直到找到根节点左侧合适的位置 x.left=put(x.left,key,value); }else{ //等于当前节点就替换value即可 x.value=value; } return x; } //查询树中指定的值的value public value get(key key){ return get(root,key); } //从指定的树x中，查找对应键的value值 public value get(Node x,key key){ //子树x为null， if(x==null){ return null; } //子树x不为null //创建result存储key值的比较结果 int result=key.compareTo(x.key); //如果key值大于当前节点的key，则往右找 if(result>0){ return get(x.right,key); } //如果key值小于当前节点的key则往左找 else if(result<0){ return get(x.left,key); } //key等于当前节点的key则返回结果 else{ return x.value; } } //删除树中key对应的value public void delete(key key){ delete(root,key); } //删除指定树中key对应的value值，并返回删除后的新树 public Node delete(Node x,key key){ //x树为空 if(x==null){ return null; } //x树不为空 //创建result存储比较结果 int result=key.compareTo(x.key); //如果result小于0则继续向左找 if(result<0){ x.left=delete(x.left,key); } //如果result>0则继续向右找 else if(result>0){ x.right=delete(x.right,key); } //如果result等于零，则找到该节点，完成删除即可 else{ //元素个数-1 N--; //一进来就是元素个数-1，避免出现bug，因为能进入到else里面来表面必定要删除一个元素 //首先得找到一个合适的节点来替换当前要删除的节点 //把目标节点定位右子树的最小节点 //第一步，如果左子树或右子树为空的情况 if(x.right==null){ return x.left; } if(x.left==null){ return x.right; } //如果左子树和右子树都不为空的话，就要遍历寻找右子树的最小节点 //创建一个最小节点变量，默认为让它等于当前节点的右子树节点 Node minNode=x.right; //通过遍历来找到最小的节点 //顺着右子树的左边往下找，找到右子树最左边的叶子节点即可 while(minNode.left!=null){ minNode=minNode.left; } //将这个最小的节点先删除掉，然后再拿去替换真正要删除的节点 //先找到最小节点的父节点，方法是如果一个节点的左节点的左节点为空的话就是 Node n=x.right; while(n.left!=null){ if(n.left.left==null){ n.left=null; //删除完成 }else{ //变换n节点即可 n=n.left; } } //真正的删除x节点 //1.让x节点的左子树成为minNode的左子树 minNode.left=x.left; //2.让x节点的右子树成为minNode的右子树 minNode.right=x.right; //3.让x节点的父节点成为minNode的父节点 x=minNode; } return x; } //查找整个树中的最小键 public key minKey(){ return minKey(root).key; } //在指定树x中找到最小键所在的节点 public Node minKey(Node x){ //需要判断x还有没有左子树，如果有，则继续向左找，如果没有，则x就是最小键所在的节点 if(x.left!=null){ return minKey(x.left); }else{ return x; } } //查找整个树中的最大键 public key maxKey(){ return maxKey(root).key; } //在指定树x中找到最小键所在的节点 public Node maxKey(Node x){ //需要判断x还有没有右子树，如果有，则继续向右找，如果没有，则x就是最大键所在的节点 if(x.right!=null){ return maxKey(x.right); }else{ return x; } } //前序遍历 //获取整个树中所有的键 public Queue preTraversal(){ Queue keys =new Queue (); preTraversal(root,keys); return keys; } //获取指定树x的所有键，并放到key队列中 private void preTraversal(Node x,Queue keys){ //安全性验证 if(x==null){ return; } //把x节点的key放到keys中 keys.InQueue(x.key); //递归遍历x节点的左子树 if(x.left!=null){ preTraversal(x.left,keys); } //递归遍历x节点的右子树 if(x.right!=null){ preTraversal(x.right,keys); } } //中序遍历 //使用中序遍历来获取树中所有的键 public Queue midTraversal(){ Queue keys =new Queue (); midTraversal(root,keys); return keys; } //使用中序遍历来获取指定树x中的所有键，并存放到keys中 private void midTraversal(Node x,Queue keys){ //安全性校验 if(x==null){ return; } //先递归，把左子树中所有的键放到keys中 if(x.left!=null){ midTraversal(x.left,keys); } //把当前节点的键放到keys中 keys.InQueue(x.key); //再递归，把右子树中的键放到keys中 if(x.right!=null){ midTraversal(x.right,keys); } } //后序遍历 //使用后序遍历来获取树中所有的键 public Queue backTraversal(){ Queue keys =new Queue (); backTraversal(root,keys); return keys; } //使用后序遍历来获取指定树x中的所有键，并存储到keys队列中 private void backTraversal(Node x,Queue keys){ //安全性校验 if(x==null){ return; } //先递归，把左子树的键全部放到keys中 if(x.left!=null){ backTraversal(x.left,keys); } //再递归把右子树中的键全部放到keys中 if(x.right!=null){ backTraversal(x.right,keys); } //最后把x节点的键放到keys中 keys.InQueue(x.key); } //层次遍历 //使用层次遍历获取整个树中所有的键 public Queue layerTraversal(){ //定义两个队列，分别存储树中的键和树中的节点 Queue keys =new Queue (); Queue nodes =new Queue (); //默认往队列中放入根节点 nodes.InQueue(root); //循环弹出节点,循环结束的条件是节点为空了，没有节点了 while(!nodes.isEmpty()){ //1.从队列中弹出一个节点，把key放入到keys中 Node n=nodes.OutQueue(); keys.InQueue(n.key); //2.判断当前节点还有没有左子节点，如果有，则放入到nodes中 if(n.left!=null){ nodes.InQueue(n.left); } //3.判断当前节点还有没有右子节点，如果有，则放入到nodes中 if(n.right!=null){ nodes.InQueue(n.right); } } return keys; } }
