在前面学完6种简单排序，顺序表，链表，栈，队列，以及符号表感觉到有些洋洋得意，感觉自己很牛啥的，呵呵，那你就错了，那些只是数据结构算法的开始，皮毛而已。接下我我将为你们讲解树大板块，但在这里由于我们之前还没有接触过树这种类型的数据结构，所以我将按套路出牌，为大家讲解树的基础入门部分——二叉查找树。
原理
二叉排序树（Binary Sort Tree）或者是一棵空树；或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
二叉查找树实现 1.插入方法 put 实现思想： 1. 如果当前树中没有任何一个结点，则直接把新结点当做根结点使用 2. 如果当前树不为空，则从根结点开始： 2.1如果新结点的 key 小于当前结点的 key ，则继续找当前结点的左子结点； 2.2如果新结点的key大于当前结点的 key ，则继续找当前结点的右子结点； 2.3如果新结点的 key 等于当前结点的key，则树中已经存在这样的结点，替换该结点的value值即可查询方法 get 实现思想： 从根节点开始： 1. 如果要查询的 key 小于当前结点的 key ，则继续找当前结点的左子结点； 2.如果要查询的key 大于当前结点的 key ，则继续找当前结点的右子结点； 3.如果要查询的key 等于当前结点的 key ，则树中返回当前结点的 value 。 删除方法 delete 实现思想： 1. 找到被删除结点； 2.找到被删除结点右子树中的最小结点minNode 3.删除右子树中的最小结点 4. 让被删除结点的左子树称为最小结点 minNode 的左子树，让被删除结点的右子树称为最小结点 minNode 的右子 树 5. 让被删除结点的父节点指向最小结点 minNode
代码实现：
public class BinaryTree,Value> { // 记录根节点 private Node root; // 记录树中元素的个数 private int N; // 定义一个内部类 public class Node{ public Key key; private Value value; public Node left; public Node right; public Node(Key key,Value value,Node left,Node right) { 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,并返回添加元素后新的树 public Node put(Node x,Key key,Value value) { if(x==null) { //个数+1 N++; return new Node(key,value,null,null); } int cmp=key.compareTo(x.key); if(cmp>0) { //新结点的key大于当前结点的key，继续找当前结点的右子结点 x.right=put(x.right,key,value); }else if(cmp<0) { //新结点的key小于当前结点的key，继续找当前结点的左子结点 x.left=put(x.left,key,value); }else { //新结点的key等于当前结点的key，把当前结点的value进行替换 x.value=value; } return x; } //查询树中指定key对应的value public Value get(Key key) { return get(root,key); } //从指定的树x中，查找key对应的值 public Value get(Node x,Key key) { if(x==null) { return null; } int cmp=key.compareTo(x.key); if(cmp>0) { //如果要查询的key大于当前结点的key，则继续找当前结点的右子结点； return get(x.right,key); }else if(cmp<0){ //如果要查询的key小于当前结点的key，则继续找当前结点的左子结点 return get(x.left,key); }else { //如果要查询的key等于当前结点的key，则树中返回当前结点的value。 return x.value; } } //删除树中key对应的value public void delete(Key key) { delete(root,key); } //删除指定树x中的key对应的value，并返回删除后的新树 private Node delete(Node x,Key key) { if(x==null) { return null; } int cmp=key.compareTo(x.key); if(cmp>0) { //新结点的key大于当前结点的key，继续找当前结点的右子结点 x.right=delete(x.right,key); }else if(cmp<0){ //新结点的key小于当前结点的key，继续找当前结点的左子结点 x.left=delete(x.left,key); }else { //新结点的key等于当前结点的key,当前x就是要删除的结点 // 个数-- N--; //1.如果当前结点的右子树不存在，则直接返回当前结点的左子结点 if(x.right==null) { return x.left; } //2.如果当前结点的左子树不存在，则直接返回当前结点的右子结点 if(x.left==null) { return x.right; } //3.当前结点的左右子树都存在 //3.1找到右子树中最小的结点 Node minNode=x.right; while(minNode.left!=null) { minNode=minNode.left; } //3.2删除右子树中最小的结点 Node n=x.right; while(n.left!=null) { if(n.left.left==null) { n.left=null; }else { n=n.left; } } //3.3让被删除结点的左子树称为最小结点minNode的左子树，让被删除结点的右子树称为最小结点 minNode的右子树 minNode.left=x.left; minNode.right=x.right; //3.4让被删除结点的父节点指向最小结点minNode x=minNode; } return x; }
其它方法：
1. 查找二叉树中最小的键 在某些情况下，我们需要查找出树中存储所有元素的键的最小值，比如我们的树中存储的是学生的排名和姓名数 据，那么需要查找出排名最低是多少名？这里我们设计如下两个方法来完成： 代码：//找出整个树中最小的键
public Key min() {
if(min(root)==null) {
return null;
}
return min(root).key;
}
//找出指定树x中最小的键所在的结点
public Node min(Node x) {
if(x==null) {
return null;
}
if(x.left!=null) {
return min(x.left);
}else {
return x;
}
}
2.
查找二叉树中最大的键
在某些情况下，我们需要查找出树中存储所有元素的键的最大值，比如比如我们的树中存储的是学生的成绩和学生 的姓名，那么需要查找出最高的分数是多少？这里我们同样设计两个方法来完成：
代码：
//找出指定树x中最大键所在的结点
public Node max(Node x) {
if(x==null) {
return null;
}
if(x.right!=null) {
return max(x.right);
}else {
return x;
}
}
// 获取整个树的所有键
public Queue preErgodic(){
Queue keys=new Queue<>();
preErgodic(root,keys);
return keys;
}
3.二叉树的基础遍历
很多情况下，我们可能需要像遍历数组数组一样，遍历树，从而拿出树中存储的每一个元素，由于树状结构和线性 结构不一样，它没有办法从头开始依次向后遍历，所以存在如何遍历，也就是按照什么样的搜索路径
进行遍历的问 题。
1.前序遍历；先访问根结点，然后再访问左子树，最后访问右子树
2.
中序遍历； 先访问左子树，中间访问根节点，最后访问右子树
3.后序遍历； 先访问左子树，再访问右子树，最后访问根节点
如果我们分别对下面的树使用三种遍历方式进行遍历，得到的结果如下：
前序遍历结果：EBADCGFH
中序遍历结果：ABCDEFGH
后序遍历结果：ACDBFHGE
1.前序遍历（方法）
实现步骤： 1. 把当前结点的 key 放入到队列中 ; 2. 找到当前结点的左子树，如果不为空，递归遍历左子树 3. 找到当前结点的右子树，如果不为空，递归遍历右子树代码：
// 获取整个树的所有键 public QueuepreErgodic(){ Queue keys=new Queue<>(); preErgodic(root,keys); return keys; } // 获取指定树x的所有键，并放到队列中 private void preErgodic(Node x,Queue keys) { if(x==null) { return; } keys.enqueue(x.key); if(x.left!=null) { preErgodic(x.left,keys); } if(x.right!=null) { preErgodic(x.right,keys); } }
2.中序遍历（方法）
实现步骤： 1. 找到当前结点的左子树，如果不为空，递归遍历左子树 2. 把当前结点的 key 放入到队列中 ; 3. 找到当前结点的右子树，如果不为空，递归遍历右子树代码：
// 中序遍历获取整个树的所有键 public QueuemidErgodic(){ Queue keys=new Queue<>(); midErgodic(root,keys); return keys; } // 中序遍历获取指定树x的所有键，并放到队列中 private void midErgodic(Node x,Queue keys) { if(x==null) { return; } if(x.left!=null) { midErgodic(x.left,keys); } keys.enqueue(x.key); if(x.right!=null) { midErgodic(x.right,keys); } }
3.后序遍历（方法）
实现步骤： 1. 找到当前结点的左子树，如果不为空，递归遍历左子树 2. 找到当前结点的右子树，如果不为空，递归遍历右子树 3. 把当前结点的 key 放入到队列中 ;// 后序遍历获取整个树的所有键 public Queue3.二叉树的层序遍历（方法） 所谓的层序遍历，就是从根节点（第一层）开始，依次向下，获取每一层所有结点的值，有二叉树如下： 层序遍历的结果是： EBGADFHC 实现步骤： 1. 创建队列，存储每一层的结点； 2. 使用循环从队列中弹出一个结点： 2.1 获取当前结点的 key ； 2.2如果当前结点的左子结点不为空，则把左子结点放入到队列中 2.3 如果当前结点的右子结点不为空，则把右子结点放入到队列中afterErgodic(){ Queue keys=new Queue (); afterErgodic(root,keys); return keys; } // 后序遍历获取指定树x的所有键，并放到队列中 private void afterErgodic(Node x,Queue keys) { if(x==null) { return; } if(x.left!=null) { afterErgodic(x.left,keys); } if(x.right!=null) { afterErgodic(x.right,keys); } keys.enqueue(x.key); }
代码实现：
public QueuelayerErgodic(){ Queue keys=new Queue (); Queue nodes=new Queue (); // //往队列中放入根节点 nodes.enqueue(root); // while(!nodes.isEmpty()) { //往队列中弹出一个节点，把key放进keys中 Node n=nodes.dequeue(); keys.enqueue(n.key); //判断当前节点是否还有左子树，有的话放进nodes队列中 if(n.left!=null) { nodes.enqueue(n.left); } //判断当前节点是否还有右子树，有的话放进nodes队列中 if(n.right!=null) { nodes.enqueue(n.right); } } return keys; }
4.二叉树的最大深度问题
实现步骤： 1. 如果根结点为空，则最大深度为 0 ； 2. 计算左子树的最大深度； 3. 计算右子树的最大深度； 4. 当前树的最大深度 = 左子树的最大深度和右子树的最大深度中的较大者 +1 代码实现：public int maxDepth() {
return maxDepth(root);
}
//计算指定树x的最大深度
private int maxDepth(Node x) {
//1.如果根结点为空，则最大深度为0；
if(x==null) {
return 0;
}
int max=0;
int maxL=0;
int maxR=0;
//2.计算左子树的最大深度；
if(x.left!=null) {
maxL=maxDepth(x.left);
}
//3.计算右子树的最大深度；
if(x.right!=null) {
maxR=maxDepth(x.right);
}
//4.当前树的最大深度=左子树的最大深度和右子树的最大深度中的较大者+1
max=maxL>maxR?maxL+1:maxR+1;
return max;
}
5.折纸问题
需求：
请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折
1
次，压出折痕后展开。此时 折痕是凹下去的，即折 痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2
次，压出折痕后展开，此时有三条折痕，从上 到下依次是下折痕、下折痕和上折痕。
给定一 个输入参数
N
，代表纸条都从下边向上方连续对折
N
次，请从上到下打印所有折痕的方向 例如：
N=1
时，打 印： down
；
N=2
时，打印：
down down up
分析：
我们把对折后的纸张翻过来，让粉色朝下，这时把第一次对折产生的折痕看做是根结点，那第二次对折产生的下折 痕就是该结点的左子结点，而第二次对折产生的上折痕就是该结点的右子结点，这样我们就可以使用树型数据结构 来描述对折后产生的折痕。
这棵树有这样的特点：
1.
根结点为下折痕；
2.
每一个结点的左子结点为下折痕；
3.
每一个结点的右子结点为上折痕；
实现步骤：
1.
定义结点类
2.
构建深度为
N
的折痕树；
3.
使用中序遍历，打印出树中所有结点的内容；
构建深度为
N
的折痕树：
1.
第一次对折，只有一条折痕，创建根结点；
2.
如果不是第一次对折，则使用队列保存根结点；
3.
循环遍历队列：
3.1从队列中拿出一个结点；
3.2如果这个结点的左子结点不为空，则把这个左子结点添加到队列中；
3.3如果这个结点的右子结点不为空，则把这个右子结点添加到队列中；
3.4
判断当前结点的左子结点和右子结点都不为空，如果是，则需要为当前结点创建一个值为
down
的左子结点，一 个值为up
的右子结点。
代码实现：
public class PagerFoldingTest {
public static void main(String[] args) {
//构建折痕树
Node tree=createTree(2);
//遍历折痕树，并打印
printTree(tree);
}
//构建深度为N的折痕树；
private static Node createTree(int N){
Node tree=null;
for(int i=0;i queue=new Queue();
queue.enqueue(tree);
//3.循环遍历队列：
while(!queue.isEmpty()) {
//3.1从队列中拿出一个结点；
Node tmp=queue.dequeue();
//3.2如果这个结点的左子结点不为空，则把这个左子结点添加到队列中；
if(tmp.left!=null) {
queue.enqueue(tmp.left);
}
//3.3如果这个结点的右子结点不为空，则把这个右子结点添加到队列中；
if(tmp.right!=null) {
queue.enqueue(tmp.right);
}
//3.4判断当前结点的左子结点和右子结点都不为空，如果是，则需要为当前结点创建一个 值为down的左子结点，一个值为up的右子结点。
if(tmp.left==null&&tmp.right==null) {
tmp.left=new Node("down",null,null);
tmp.right=new Node("up",null,null);
}
}
}
return tree;
}
//使用中序遍历，打印出树中所有结点的内容；
private static void printTree(Node tree) {
if(tree==null) {
return;
}
if(tree.left!=null) {
printTree(tree.left);
}
System.out.print(tree.item+"t");
if(tree.right!=null) {
printTree(tree.right);
}
}
private static class Node{
T item;
Node left;
Node right;
public Node(T item,Node left,Node right) {
this.item=item;
this.left=left;
this.right=right;
}
}
}
