企业官网建设流程全解析

二叉树(BST)基础遍历----深度优先

很多情况下，我们可能需要像遍历数组数组一样，遍历树，从而拿出树中存储的每一个元素，由于树状结构和线性结构不一样，它没有办法从头开始依次向后遍历，所以存在如何遍历，也就是按照什么样的搜索路径进行遍历的问题。

我们把树简单的画作上图中的样子，由一个根节点、一个左子树、一个右子树组成，那么按照根节点什么时候被访问，我们可以把二叉树的遍历分为以下三种方式：

1. 前序遍历；
   先访问根结点，然后再访问左子树，最后访问右子树
2. 中序遍历；
   先访问左子树，中间访问根节点，最后访问右子树
3. 后序遍历；
   先访问左子树，再访问右子树，最后访问根节点

如果我们分别对下面的树使用三种遍历方式进行遍历，得到的结果如下：

1. 前序遍历

前序遍历的API

实现步骤：

1. 把当前结点的key放入到队列中;
2. 找到当前结点的左子树，如果不为空，递归遍历左子树
3. 找到当前结点的右子树，如果不为空，递归遍历右子树

用的jDK自带的队列 LinkedBlockingDeque

代码：

//获取整个树中所有的键publicQueue<Key>preErgodic(){Queue<Key>keys=newLinkedBlockingDeque<>();preErgodic(root,keys);returnkeys;}//获取指定树x的所有键，并放到keys队列中privatevoidpreErgodic(Nodex,Queue<Key>keys){if(x==null){return;}//把x结点的key放入到keys中keys.add(x.key);//递归遍历x结点的左子树if(x.left!=null){preErgodic(x.left,keys);}//递归遍历x结点的右子树if(x.right!=null){preErgodic(x.right,keys);}}

测试

@Testpublicvoidtest01(){//创建树对象BinaryTree<String,String>tree=newBinaryTree<>();//往树中添加数据tree.put("E","5");tree.put("B","2");tree.put("G","7");tree.put("A","1");tree.put("D","4");tree.put("F","6");tree.put("H","8");tree.put("C","3");//遍历Queue<String>keys=tree.preErgodic();for(Stringkey:keys){Stringvalue=tree.get(key);System.out.println(key+"----"+value);}}

2.中序遍历

中序遍历是按照Key从小到大遍历,最为重要

中序遍历的API：

实现步骤：

1. 找到当前结点的左子树，如果不为空，递归遍历左子树
2. 把当前结点的key放入到队列中;
3. 找到当前结点的右子树，如果不为空，递归遍历右子树

代码：

//使用中序遍历获取树中所有的键publicQueue<Key>midErgodic(){Queue<Key>keys=newLinkedBlockingDeque<>();midErgodic(root,keys);returnkeys;}//使用中序遍历，获取指定树x中所有的键，并存放到key中privatevoidmidErgodic(Nodex,Queue<Key>keys){if(x==null){return;}//先递归，把左子树中的键放到keys中if(x.left!=null){midErgodic(x.left,keys);}//把当前结点x的键放到keys中keys.add(x.key);//在递归，把右子树中的键放到keys中if(x.right!=null){midErgodic(x.right,keys);}}

测试:

@Testpublicvoidtest02(){//创建树对象BinaryTree<String,String>tree=newBinaryTree<>();//往树中添加数据tree.put("E","5");tree.put("B","2");tree.put("G","7");tree.put("A","1");tree.put("D","4");tree.put("F","6");tree.put("H","8");tree.put("C","3");//遍历Queue<String>keys=tree.midErgodic();for(Stringkey:keys){Stringvalue=tree.get(key);System.out.println(key+"----"+value);}}

3. 后序遍历

遍历的API：

实现步骤：

1. 找到当前结点的左子树，如果不为空，递归遍历左子树
2. 找到当前结点的右子树，如果不为空，递归遍历右子树
3. 把当前结点的key放入到队列中;

代码：

//使用后序遍历，把整个树中所有的键返回publicQueue<Key>afterErgodic(){Queue<Key>keys=newLinkedBlockingDeque<>();afterErgodic(root,keys);returnkeys;}//使用后序遍历，把指定树x中所有的键放入到keys中privatevoidafterErgodic(Nodex,Queue<Key>keys){if(x==null){return;}//通过递归把左子树中所有的键放入到keys中if(x.left!=null){afterErgodic(x.left,keys);}//通过递归把右子树中所有的键放入到keys中if(x.right!=null){afterErgodic(x.right,keys);}//把x结点的键放入到keys中keys.add(x.key);}

测试:

@Testpublicvoidtest03(){//创建树对象BinaryTree<String,String>tree=newBinaryTree<>();//往树中添加数据tree.put("E","5");tree.put("B","2");tree.put("G","7");tree.put("A","1");tree.put("D","4");tree.put("F","6");tree.put("H","8");tree.put("C","3");//遍历Queue<String>keys=tree.afterErgodic();for(Stringkey:keys){Stringvalue=tree.get(key);System.out.println(key+"----"+value);}}

二叉树的层序遍历----广度优先

所谓的层序遍历，就是从根节点（第一层）开始，依次向下，获取每一层所有结点的值，有二叉树如下

那么层序遍历的结果是：EBGADFHC

层序遍历的API：

实现步骤：

1. 创建队列，存储每一层的结点；
2. 使用循环从队列中弹出一个结点：
3. 获取当前结点的key；
4. 如果当前结点的左子结点不为空，则把左子结点放入到队列中
5. 如果当前结点的右子结点不为空，则把右子结点放入到队列中

代码实现:

//使用层序遍历，获取整个树中所有的键publicQueue<Key>layerErgodic(){//定义两个队列，分别存储树中的键和树中的结点Queue<Key>keys=newLinkedBlockingDeque<>();Queue<Node>nodes=newLinkedBlockingDeque<>();//默认，往队列中放入根结点nodes.add(root);while(!nodes.isEmpty()){//从队列中弹出一个结点，把key放入到keys中Noden=nodes.poll();keys.add(n.key);//判断当前结点还有没有左子结点，如果有，则放入到nodes中if(n.left!=null){nodes.add(n.left);}//判断当前结点还有没有右子结点，如果有，则放入到nodes中if(n.right!=null){nodes.add(n.right);}}returnkeys;}

测试:

@Testpublicvoidtest01(){//创建树对象BinaryTree<String,String>tree=newBinaryTree<>();//往树中添加数据tree.put("E","5");tree.put("B","2");tree.put("G","7");tree.put("A","1");tree.put("D","4");tree.put("F","6");tree.put("H","8");tree.put("C","3");//遍历Queue<String>keys=tree.layerErgodic();for(Stringkey:keys){Stringvalue=tree.get(key);System.out.println(key+"----"+value);}}